CENTRO FEDERAL DE EDUCAÇÃO
TECNOLÓGICA DE MINAS GERAIS
Diretoria de Pesquisa e Pós-Graduação
Programa de Mestrado em Modelagem
Matemática e Computacional
HEURÍSTICAS PARA O
PROBLEMA DA CADEIA DE
CARACTERES MAIS PRÓXIMA
Dissertação de Mestrado, submetida ao Programa
de Pós-Graduação em Modelagem Matemática e
Computacional, como parte dos requisitos exigidos
para a obtenção do título de Mestre em Modelagem Matemática e Computacional.
Aluno: Marcelo Henrique Ribeiro de Almeida
Orientador: Prof. Dr. Sérgio Ricardo de Souza
Belo Horizonte - MG
Agosto de 2013
Almeida, Marcelo Henrique Ribeiro de
L732c
Heurísticas para o Problema da Cadeia de Caracteres mais
Próxima / Marcelo Henrique Ribeiro de Almeida. - 2013.
60f.
Dissertação de mestrado apresentada ao Programa de PósGraduação em Modelagem Matemática e Computacional.
Orientador: Sérgio Ricardo de Souza
Dissertação (mestrado) - Centro Federal de Educação
Tecnológica de Minas Gerais
1. Cadeia de caracteres - Modelos matemáticos - Teses. 2.
Busca Gulosa Iterada - Teses. 3. Algoritmo Genético Baseado em
Chaves Aleatórias Tendencioso - Teses. 4. Distância de Hamming
- Teses. 5. Heurística - Teses. I. Souza, Sérgio Ricardo de. II.
Centro Federal de Educação Tecnológica de Minas Gerais. III. Título.
CDD: 519.4
Elaboração da Ficha catalográfica pela Biblioteca Campus II / CEFET-MG
Agradecimento
Agradeço ao Pai do céu pelas bênçãos, saúde, alegrias e oportunidades que me
possibilitaram alcançar mais uma das etapas de minha vida. Agradeço a minha
família pelo amor e carinho e principalmente a minha avó Celina (in memóriam)
por todo seu amor. Agradeço também por conhecer pessoas maravilhosas nesta
jornada, que me acrescentaram um crescimento humano e espiritual.
E peço a Deus que abençoe: o professor Dr. Sérgio pela oportunidade concedida,
a qual foi fundamental para concretização desse sonho; o meu amigo Daniel pelo incentivo; aos funcionários e professores do CEFET-MG Campus II pela dedicação em
manter uma ótima estrutura educacional e a minha namorada Kianne pelo companheirismo e compreensão pela minha falta de tempo, que foram dedicadas ao nosso
futuro.
iii
Não venci todas as vezes que lutei. Mas perdi todas as vezes que deixei
de lutar.
Rui Barbosa
iv
Resumo
Esta dissertação de mestrado propõe o desenvolvimento de métodos heurísticos para o Problema da Cadeia de Caracteres mais Próxima (PCCP). O PCCP
tem, como objetivo, encontrar uma sequência t mais próxima possível de todas as
seqüências de um conjunto dado, usando, como métrica, a distância de Hamming.
A distância de Hamming dH (s, t) entre duas seqüências s e t de igual comprimento
é dado pelo número de posições nas quais elas diferem. O PCCP possui várias aplicações, em especial, na área da Bioinformática e na Teoria de Códigos. Classificado
como um problema de complexidade NP-Difícil, vários algoritmos de aproximação
e metaheurísticas têm sido propostas para encontrar soluções ótimas e com tempos
de processamentos aceitáveis. Neste trabalho, um novo algoritmo é proposto, baseado no framework do Algoritmo Genético Biased Random-Key Genetic Algorithm
(BRKGA) e será comparado com o algoritmo Iterated Greedy Search (IGS).
PALAVRAS-CHAVE: Problema da Cadeia de Caracteres mais Próxima, distância de Hamming, Iterated Greedy Search, Biased Random-Key Genetic Algorithm,
Metaheurísticas, Otimização.
v
Abstract
This dissertation proposes the development of heuristic methods for the Closest
String Problem (CSP). The CSP aims to find a string t as close as possible of all
the strings of a given set, using as metrics the Hamming distance. The Hamming
distance dH (s, t) between two strings s and t of equal length is given by the number
of positions in which they differ. The CSP has several applications, in special, in the
area of Bioinformatics and in Coding Theory. Classified as a problem of complexity
NP-Hard, several approximation algorithms and metaheuristics have been proposed
to find optimal solutions with acceptable processing times. In this work, a new
algorithm is proposed, based on the framework of the Biased Random-Key Genetic
Algorithm (BRKGA) and it will be compared with the Iterated Greedy Search
algorithm (IGS).
Keywords: Closest String Problem, Hamming distance, Iterated Greedy Search,
Biased Random-Key Genetic Algorithm, Metaheuristics, Optimization.
vi
Lista de Abreviaturas e Siglas
AG Algoritmo Genético
BI do inglês - Best Improvement
BRKGA do inglês - Biased Random Key Genetic Algorithm
BRP do inglês - Bandwidth Reduction Problem
CSP do inglês - Closest String Problem
DBCGA do inglês - Data-Based Coding Genetic Algorithm
DFA do inglês - Distance First Algorithm
DNA Ácido Desoxirribonucléico
DSSP do inglês - Distinguishing String Selection Problem
DSSS do inglês - Distinguishing Substring Selection
EPTAS do inglês - Efficient Polynomial-Time Approximation Scheme
RNA Ácido Ribonucléico
FFMSP do inglês - Far From Most String Problem
FI do inglês - First Improvement
FSP do inglês - Farthest String Problem
IGS do inglês - Iterated Greedy Search
ILP do inglês - Integer Linear Program
ILS do inglês - Iterated Local Search
IP do inglês - Integer-Programming
GRASP do inglês - Greedy Randomized Adaptative Search Procedure
LCS do inglês - Longest Common Subsequence
LCR Lista de Candidatos Restrita
LDDA do inglês - Largest distance decreasing algorithm
vii
LP do inglês - Linear Programming
PCCP Problema da Cadeia de Caracteres Mais Próxima
PTAS do inglês - Polinomial Time Approximation Schemes
PTGS do inglês - Post-Transcriptional Gene Silencing
RKGA do inglês - Random-Key Genetic Algorithm
SA do inglês - Simulated Annealing
VNS do inglês - Variable Neighborhood Search
viii
Sumário
1 Introdução
1.1 Bioinformática . . . . . . .
1.2 DNA . . . . . . . . . . . .
1.3 RNA e Síntese Protéica . . .
1.4 Organização da Dissertação
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
2
4
6
8
2 Uma Revisão Bibliográfica
9
2.1 Revisão bibliográfica do Problema da Cadeia de Caracteres mais Próxima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Análise da Revisão Bibliográfica sobre PCCP . . . . . . . . . . . . . 16
3 Caracterização do Problema
3.1 Alguns problemas de comparação e seleção de cadeias . . .
3.2 Closest String Problem (CSP) . . . . . . . . . . . . . . . .
3.3 Farthest String Problem(FSP) . . . . . . . . . . . . . . . .
3.4 Far From Most String Problem(FFMSP) . . . . . . . . . .
3.5 Outros problemas relacionados . . . . . . . . . . . . . . . .
3.5.1 Closest Substring Problem . . . . . . . . . . . . . .
3.5.2 Farthest Substring Problem . . . . . . . . . . . . .
3.5.3 Close to Most String Problem . . . . . . . . . . . .
3.5.4 Distinguishing String Selection Problem (DSSP) . .
3.6 Problema da Cadeia de Caracteres mais Próxima (PCCP)
4 Metodologia de Pesquisa
4.1 Visão Geral . . . . . . . . . . . . . . . . . . .
4.2 Algoritmo MultiStart . . . . . . . . . . . . . .
4.3 Greedy Randomized Adaptive Search Procedure
4.4 Iterated Local Search – ILS . . . . . . . . . . .
4.5 Iterated Greedy Search . . . . . . . . . . . . .
4.6 Heurística IGS-PCCP . . . . . . . . . . . . .
4.7 Algoritmos Genéticos . . . . . . . . . . . . . .
4.8 Random-Key Genetic Algorithm . . . . . . . .
4.9 Biased Random-Key Genetic Algorithm . . . .
4.10 Heurística BRKGA-PCCP . . . . . . . . . . .
ix
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
19
20
21
22
23
23
23
24
24
25
.
.
.
.
.
.
.
.
.
.
28
28
28
30
32
33
34
36
38
40
42
5 Experimentos Computacionais
5.1 Instâncias de Teste . . . . . . . . . . . . . . . . . . . .
5.2 Ajustes para a Perturbação k da Heurística IGS-PCCP
5.3 Ajustes para a População da Heurística BRKGA-PCCP
5.4 Comparação entre as heurísticas . . . . . . . . . . . . .
5.5 Comparação entre as heurísticas BRKGA-PCCP e PI .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
44
44
45
46
46
50
6 Considerações Finais
57
Referências
59
x
Lista de Tabelas
1.1
1.2
Aminoácidos de ocorrência natural em proteínas . . . . . . . . . . . .
O código genético (RNAm) . . . . . . . . . . . . . . . . . . . . . . .
2.1
Resultados da literatura. . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
Resultados da perturbação do IGS-PCCP para k = 3%, 10% e 20% .
Resultados da perturbação do IGS-PCCP para k = 30%, 40% e 50% .
Resultados da perturbação do IGS-PCCP para k = 60% e 70% . . . .
Resultados da perturbação do IGS-PCCP para Ω = {20} . . . . . . .
Resultados da perturbação do IGS-PCCP para Ω = {30} . . . . . . .
Resultados das diferentes populações do BRKGA-PCCP . . . . . . .
Resultados das diferentes populações do BRKGA-PCCP para Ω = {20}
Resultados das diferentes populações do BRKGA-PCCP para Ω = {30}
Comparação entre BRKGA-PCCP e IGS-PCCP . . . . . . . . . . . .
Comparação entre BRKGA-PCCP e IGS-PCCP para Ω = {20, 30} . .
Comparação entre BRKGA-PCCP e PI . . . . . . . . . . . . . . . . .
xi
6
8
47
48
49
50
51
52
52
53
54
55
56
Lista de Figuras
1.1
Modelo de fita e bastão de dupla hélice do DNA . . . . . . . . . . . .
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
4.12
Pseudocódigo MultiStart. . . . . . . . . . .
Pseudocódigo da Fase-Construtiva GRASP.
Pseudocódigo da Busca Local GRASP. . . .
Pseudocódigo do Iterated Local Search (ILS).
Ótimos locais IGS . . . . . . . . . . . . . . .
Pseudocódigo da heurística IGS-PCCP. . . .
Estrutura de geração do RKGA . . . . . . .
Geração do RKGA . . . . . . . . . . . . . .
Fim do processo de geração RKGA . . . . .
Crossover BRKGA . . . . . . . . . . . . . .
Transição entre gerações sucessivas (Noronha
Pseudocódigo BRKGA-PCCP . . . . . . . .
xii
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
et al., 2011).
. . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
29
31
31
33
34
35
38
39
39
41
42
43
Capítulo 1
Introdução
Em se tratando de Biologia Molecular, pode-se verificar a presença de vários
problemas de otimização combinatória. Geralmente, estes problemas apresentam a
necessidade de se comparar cadeias de caracteres (ou seqüências) de DNA (Ácido
Desoxirribonucléico), RNA (Ácido Ribonucléico) ou proteínas, a fim de encontrar
determinadas características presentes em cada uma delas. Esses problemas possuem
várias aplicações, como busca de regiões conservadas em seqüências não alinhadas,
identificação de drogas genéticas, formulação de sondas genéticas, dentre outras. Por
exemplo, quando se trabalha com Genoma, ou com outra seqüência de aminoácidos,
um dos aspectos principais é como determinar as similaridades e/ ou as diferenças
que ocorrem entre duas seqüências quaisquer.
Segundo Festa (2007), desde 1986 e do surgimento do Projeto Genoma Humano
tem ocorrido um grande crescimento da investigação científica em atividades dedicadas à Biologia Molecular, como o entendimento das interações entre os diversos
sistemas de uma célula, incluindo as interações de DNA, RNA e sínteses protéicas.
Anteriormente a 1980, havia um limite claro entre competências e aplicações da
Biologia Molecular em disciplinas como genética e bioquímica. Em vez disso, nas
duas últimas décadas, as atividades de investigação em Biologia Molecular começaram a ter uma interação com disciplinas de interesses não biológicos, como a Ciência
da Computação e a Física (Festa, 2007).
Com esse interesse de outras áreas em Biologia Molecular, ocorreu um crescimento do leque de novas possibilidades de aplicações. Na Ciências da Computação,
juntamente com a Matemática, a implementação de métodos eficientes para armazenar uma enorme quantidade de dados coletados em experimentos; na Física, um
melhor estudo das moléculas e suas estruturas tridimensionais.
Pesquisadores em Biologia Molecular desenvolveram uma importante representação do DNA, em que a cadeia tridimensional pode ser escrita na forma de cadeias
de caracteres unidimensionais. Essa representação é feita por vetores, que possuem
os seus caracteres representados pelas bases que formam o DNA. Essa representação
facilitou o desenvolvimento computacional nessa área da Biologia.
Com essa nova representação dos caracteres em forma de vetores, facilitou o
surgimento de recursos computacionais para a identificação dos mesmos e sua busca
em bancos de dados.
Esta dissertação trata de um problema conhecido como Problema da Cadeia de
Caracteres mais Próxima (PCCP) – Closest String Problem, que tem como objetivo
1
1.1
Introdução
2
encontrar uma seqüência de caracteres que se aproxime ao máximo, segundo uma
métrica, de todas as seqüências de um banco de dados, que são formados pelos
mesmo caracteres e possuem a mesma dimensão. Os caracteres que compõem estas
seqüências podem ser formados pelas bases do DNA, RNA ou proteínas. Neste
problema, a idéia principal é encontrar uma seqüência centro t que se assemelhe,
ao máximo, às seqüências de um dado conjunto. Ou seja, o objetivo é minimizar a
distância máxima desta cadeia de caracteres t às demais cadeias do conjunto.
Com o objetivo de solucionar o PCCP, serão realizados testes computacionais
utilizando duas heurísticas, a saber, Iterated Greedy Search e Biased Random-Key
Genetic Algorithm. Com o intuito de ajudar pesquisadores em Biologia Molecular a
encontrarem uma seqüência de caracteres semelhante a um conjunto de seqüências
de um banco de dados, formado por seqüências com os mesmos caracteres e mesma
dimensão.
1.1
Bioinformática
Em 1953, a estrutura clássica do DNA foi desvendada no trabalho de Watson
e Crick (1953). Esse e outros trabalhos levaram pesquisadores da área à conclusão
de que o DNA era a molécula que armazenava a informação genética, respondendo
assim aos questionamentos de geneticistas e químicos a respeito da natureza química
do material genético. Uma conseqüência direta destas pesquisas foi o surgimento
de uma nova ciência, a Bioinformática, cujos estudos estavam baseados, principalmente, nos ácidos nucléicos e nas proteínas. Essa nova ciência é permeada por
diversas áreas do conhecimento, como a Engenharia de Software, a Matemática, a
Estatística, a Ciência da Computação e a Biologia Molecular (Pappalardo, 2012).
Os conhecimentos dessas áreas são combinados para processar dados biológicos ou
biomédicos.
Buscando tratar os dados, foi necessário desenvolver softwares para, por exemplo identificar genes, prever a configuração tridimensional de proteínas, identificar
inibidores de enzimas, organizar e relacionar informação biológica, simular células, agrupar proteínas homólogas, montar árvores filogenéticas, comparar múltiplas
comunidades microbianas por construção de bibliotecas genômicas, analisar experimentos de expressão gênica, dentre outras inúmeras aplicações.
A Bioinformática implica a manipulação, busca e extração de informações dos dados de seqüências do DNA, RNA ou Proteínas. O desenvolvimento de técnicas para
armazenamento e busca por seqüências de DNA gerou avanços no desenvolvimento
de softwares para computadores, com muitas aplicações, especialmente algoritmos
de busca de frases. A busca de frases ou algoritmos de coincidências procura a
ocorrência de uma seqüência de letras (ou caracteres) dentro de uma seqüência de
caracteres maior, e até seqüências que sejam distintas de um determinado grupo, o
qual foi desenvolvido para buscar seqüências específicas de nucleotídeos.
Com o desenvolvimento e as pesquisas em Bioinformática, surgiram métodos
de sequenciamento dos polímeros citados acima, principalmente do DNA. A partir do surgimento desses métodos, bilhões dessas seqüências já foram e têm sido
catalogadas e armazenadas em bancos de dados públicos. O surgimento dos seqüenciadores automáticos de DNA, a partir da segunda metade da década de 1990, elevou
1.1
Introdução
3
abruptamente a quantidade de seqüências a serem armazenadas, surgindo também
a necessidade de análise desses dados. Esse novo panorama trouxe a necessidade da
utilização de plataformas computacionais capazes de interpretar, com eficiência, os
resultados obtidos.
O trabalho de Lesk (2008) destaca os bancos de dados da Biologia Molecular,
os quais contém seqüências de ácidos nucléicos e de proteínas, estruturas e funções de macromoléculas, padrões de expressão, redes de vias metabólicas e cascatas
de regulação. Segundo o autor, o arquivamento mundial de seqüências de ácidos
nucléicos é uma parceria tríplice entre o Genbank, situado no US National Center
for Biotechnology Information (NCBI), em Bethesda, Maryland, Estados Unidos; o
EMBL Nucleotide Sequence Database, localizado no European Bioinformatics Institute (EBI), em Hinxton, no Reino Unido; e o The Center for Information Biology e
DNA Data Bank of Japan, no National Institute of Genetics, em Mishima, Japão.
Há uma troca de informações entre esses grupos diariamente. Como resultado, os
dados brutos são idênticos, embora o formato em que são armazenados e a natureza
da anotação podem variar entre eles. Esses bancos de dados organizam, arquivam
e distribuem seqüências de DNA e RNA coletados de projetos genoma, publicações científicas e depósitos de patentes. Para garantir que esses dados fundamentais
permaneçam disponíveis livremente, as revistas científicas exigem o depósito de novas seqüências de nucleotídeos em um banco de dados como uma condição para a
publicação de artigos científicos.
Já em 2002, três bancos de dados de proteínas:
• Protein Information Resource (PIR), o qual trata-se de um banco de dados
de seqüências de proteínas, que foi iniciado no National Biomedical Research
Foundation (NBRF) no início do ano de 1960, localizado na Georgetown University Medical Center em Washington, DC, Estados Unidos;
• SWISS-PROT e o TrEMBL, o Swiss Institute of Bioinformatics, localizado
em Genebra; e
• European Bioinformatics Institute (EBI)
coordenaram seus esforços para formar o consórcio UniProt. Os parceiros dessa
iniciativa compartilham os bancos de dados, mas continuam a oferecer ferramentas
separadas de acesso à recuperação de informação.
De acordo com Lesk (2008), o PIR originou-se do primeiro banco de dados de
seqüências, desenvolvido por Margaret O. Dayhoff - a pioneira da área de Bioinformática. O SWISS-PROT foi desenvolvido no Swiss Institute of Bioinformatics. O
TrEMBL contém as traduções dos genes identificados nas seqüências de DNA do
EMBL Data Library. Entradas do TrEMBL são consideradas como preliminares, e
são convertidas, após organização e anotações extensas, em entradas completas do
SWISS-PROT.
Muitos projetos de sequenciamento de genomas completos mantém bancos de dados focalizados em espécies individuais. Exemplos notáveis são o ENSEMBL (Sanger
Centre, Hinxton, Reino Unido) e os navegadores da Universidade da Califórnia, em
Santa Cruz, Estados Unidos, para o genoma humano e outras espécies.
Muitos bancos de dados secundários agrupam famílias de proteínas ou subunidades com base nas similaridades entre suas seqüências. Um banco de dados
1.2
Introdução
4
“guarda-chuva”, o Interpro, é um banco de dados de famílias de proteínas, domínios
e sítios funcionais, no qual características identificáveis encontradas em proteínas
conhecidas podem ser aplicadas em seqüências de proteínas desconhecidas. Além
disso, contém conexões para outros bancos, incluindo a classificação funcional do
Gene Ontology Consortium T M .
Considerada uma recente subdivisão da Biotecnologia, a Bioinformática representa o “casamento” da Biotecnologia com a Informática. De modo simples, Bioinformática consiste no depósito e análise de seqüências genéticas em bancos de dados
e conseqüente manipulação e análise destas seqüências com a utilização de software específicos. Portanto, essa nova área surge a partir da necessidade de aplicar
recursos computacionais no armazenamento, manipulação, interpretação e análise
dos resultados obtidos das plataformas computacionais a respeito das seqüências de
polímeros.
Segundo Prosdocimi et al. (2002), a diversidade na formação dos profissionais que
atuam nas pesquisas em Biotecnologia é um fator dificultante na comunicação entre
esses profissionais. Para resolver esta questão, surge o Bioinformata, um profissional
cuja formação permite fazer uma ponte entre a Biologia e a Informática, capaz
de conhecer os problemas biológicos reais, e apto a desenvolver uma abordagem
computacional ajustada e viável para esses problemas. Assim, o Bioinformata, além
de saber utilizar programas produzidos por outros programadores, deve também ser
capaz de produzir seus próprios programas, para lidar com problemas típicos da
Bioinformática.
1.2
DNA
Segundo da Fonseca (2003), no final do Séc. XIX, o monge augustiniano Gregor
Mendel, realizando experimentos com ervilhas, estabeleceu a existência de estruturas
biológicas denominadas genes, que seriam responsáveis pela expressão e transmissão
de características hereditárias nos indivíduos. O trabalho de Mendel deu origem
ao ramo da Biologia atualmente conhecido como Genética. Até 1944, acreditava-se
que o material genético estava contido em proteínas no interior das células, até que
Oswald Avery, Maclyn McCarty e Colin McLeod (Avery et al., 1944) demonstraram
que, na verdade, a molécula de DNA é o principal carregador do código genético dos
organismos vivos.
O ácido desoxiribonucléico, ou DNA, é uma macromolécula constituída a partir de estruturas menores, denominadas nucleotídeos. Cada nucleotídeo, por sua
vez, é formado por uma molécula de açúcar (desoxiribose), um grupo fosfato e uma
base nitrogenada que o identifica. Moléculas de DNA são cadeias longas, contendo
uma mensagem composta por um alfabeto de quatro letras, na forma {A, C, G, T },
representando as quatro bases nitrogenadas desta molécula, denominadas, respectivamente, Adenina (A), Guanina (G), Citosina (C) e Timina (T). Mesmo para
microrganismos, a mensagem é longa, tipicamente com 106 caracteres. Em 1953,
Watson e Crick (1953) deduziram a estrutura tridimensional da molécula do DNA
e, a partir de então, seu processo de replicação.
O DNA possui a forma de um helicóide duplo (ver Figura 1.1). Cada uma
das fitas helicoidais representa uma seqüência de nucleotídeos. As duas fitas são
1.3
Introdução
5
mantidas juntas através de ligações químicas conhecidas como pontes de hidrogênio,
sendo que, no caso do DNA, essas ligações obedecem a uma certa regra: as chamadas
bases púricas (A e G) dos nucleotídeos de uma fita são unidas às chamadas bases
pirimídicas (T e C) da outra fita, e vice-versa, formando os chamados pares de base.
Mais precisamente, a Adenina de uma fita sempre se emparelha com uma Timina
da outra fita, e reciprocamente, ao passo que a Guanina de uma fita sempre se
emparelha com uma Citosina da outra, e reciprocamente. Como conseqüência dessa
regra de formação, as fitas na molécula do DNA, embora não sejam idênticas, são
complementares, no sentido que uma determina a outra univocamente. Além disso,
essas fitas possuem uma orientação ditada pelo número do átomo de carbono da
molécula de açúcar na qual um nucleotídeo se liga ao outro. A orientação positiva é,
convencionalmente, denominada orientação 5′ − 3′ , indicando que um nucleotídeo se
liga ao anterior a ele na fita pelo carbono de número 5 e, ao posterior, pelo carbono
de número 3. As orientação das fitas complementares são reversas entre si.
Figura 1.1: Modelo de fita e bastão de dupla hélice do DNA. (Pasternak, 2002).
Um gene pode ser visto como um trecho ou região da molécula de DNA responsável pela codificação e expressão de alguma característica física do indivíduo, o que
corresponde, geralmente, à informação necessária para a síntese de uma determinada
proteína. De acordo com da Fonseca (2003), o DNA não é composto totalmente por
genes, muito pelo contrário, apenas entre 2% e 3% do DNA humano é constituído
por genes. Os restantes, aproximadamente 97% a 98%, do DNA, correspondem a
agrupamentos de proteínas, que não contém nenhuma informação.
As moléculas de DNA, em geral, estão dentro de um cromossomo, que é uma
estrutura que reside no interior das células (especificamente no núcleo, no caso dos
eucariontes). O número de cromossomos varia de espécie para espécie. As informações correspondentes ao DNA, de todos os cromossomos de uma determinada
espécie, compõem aquilo que se denomina o genoma da espécie. O genoma humano,
por exemplo, possui cerca de 3, 3 × 109 pb, ou seja, mais de três bilhões de pares de
base.
1.3
Introdução
1.3
6
RNA e Síntese Protéica
Proteínas são polímeros constituídos de moléculas menores (monômeros), denominadas aminoácidos, unidas entre si através das chamadas ligações peptídicas. A
implementação da informação genética ocorre inicialmente com a síntese de DNA e
proteínas. As proteínas são as moléculas responsáveis pela maior parte da estrutura
e atividade dos organismos, como tecidos, órgãos dos indivíduos e também agem
como hormônios, enzimas digestivas, etc. A principal atividade celular na qual o
DNA está envolvido é justamente a síntese protéica. Além do DNA, o ácido ribonucléico ou RNA, que é um outro tipo de ácido nucléico, também desempenha um
papel fundamental na síntese protéica.
Para que as células possam produzir suas proteínas, elas precisam de aminoácidos, que podem ser obtidos a partir da alimentação ou serem fabricados pelo próprio
organismo. Tipicamente, proteínas são compostas de 200 a 400 aminoácidos de proteínas. A Tabela 1.1 a seguir mostra os aminoácidos de ocorrência natural nas
proteínas.
Tabela 1.1: Aminoácidos de ocorrência natural em proteínas
Item
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
17
19
20
Nome
Glicina ou Glicocola
Alanina
Leucina
Valina
Isoleucina
Prolina
Fenilalanina
Serina
Treonina
Cisteina
Tirosina
Asparagina
Glutamina
Aspartato ou
Ácido aspártico
Glutamato ou
Ácido glutâmico
Arginina
Lisina
Histidina
Triptofano
Metionina
Abreviação
Gly ou Gli
Ala
Leu
Val
Ile
Pro
Phe ou Fen
Ser
Thr ou The
Cys ou Cis
Tyr ou Tir
Asn
Gln
Asp
Símbolo
G
A
L
V
I
P
F
S
T
C
Y
N
Q
D
Glu
E
Arg
Lys ou Lis
His
Trp ou Tri
Met
R
K
H
W
M
De acordo com Lesk (2008), o RNA, assim como o DNA, é constituído de nucleotídeos, sendo a Timina (T) substituída pela Uracila (U). Entretanto, ao contrário
do DNA, o RNA é formado por uma única fita e apresenta uma conformação tridimensional bem mais variada do que a dupla hélice do DNA, podendo se dividir em
três tipos:
• RNA mensageiro (RNAm): responsável por levar a informação do DNA do
núcleo até o citoplasma;
1.3
Introdução
7
• RNA transportador (RNAt): responsável por transportar os aminoácidos que
serão utilizados na formação das proteínas até os ribossomos; e
• RNA ribossômico (RNAr): faz parte da constituição dos ribossomos.
O processo de síntese de proteínas que ocorre no interior das células é formado,
essencialmente, por duas etapas, denominadas transcrição e tradução. Na transcrição, a partir de um gene, a síntese protéica se inicia com a produção de um tipo
de RNA, conhecido como RNA mensageiro ou RNAm. O processo de produção do
RNAm ocorre, a grosso modo, da seguinte forma: o aparato celular reconhece o
início de um gene a partir de alguns sinais, como seqüências específicas de nucleotídeos, que ocorrem nas chamadas regiões promotoras, que se estendem por algumas
dezenas de pares de base antes do início dos genes. Uma enzima, denominada RNA
polimerase, fixa-se ao DNA em pontos específicos da região promotora, conhecidos
como sítios de ligação, provocando uma ruptura localizada entre as suas duas fitas
constituintes. A partir de então, a RNA polimerase desliza sobre uma das fitas do
DNA gênico, no sentido 3′ − 5′ (a cada três ligações), percorrendo cada desoxiribonucleotídeo (C, G, T ou A) e fazendo com que ribonucleotídeos complementares
(respectivamente G, C, A ou U) sejam acrescentados à molécula de RNAm que,
assim, vai se formando ao longo do caminho, no sentido 5′ − 3′ . Ao final do gene,
também reconhecido pela RNA polimerase por um sinal específico, algumas dezenas
de ribonucleotídeos {A} são acrescentados ao RNAm, constituindo a chamada cauda
poli -A, e a RNA polimerase desliga-se do DNA, que é então reconstituído.
Nos seres procariontes, dentre os quais incluem-se formas de vida primitivas como
as bactérias e algas cianofíceas, o RNAm assim produzido já pode ser utilizado para
a síntese de uma determinada proteína. Já nos seres denominados eucariontes, que
são organismos pluricelulares com núcleo celular distinto, dentre os quais incluemse a maioria dos organismos superiores como as plantas e animais, os genes são
extratificados em trechos que contribuem para a síntese protéica, chamados éxons,
intercalados por trechos não codificantes, denominadas íntrons. Portanto, nos eucariontes, o RNAm recém-produzido a partir de um gene da maneira acima descrita
ainda não está completamente maduro, sendo ainda submetido a um processo denominado splicing, no qual, através da ação de um complexo de enzimas, os trechos
correspondentes aos íntrons são removidos da molécula, permanecendo apenas os
trechos codificantes.
Já na tradução, uma vez maduro, o RNAm abandona o núcleo celular, nos eucariontes, e migra para o citoplasma, que é um líquido fora do núcleo, mas no interior da
célula. De acordo com Lesk (2008), a tradução do RNAm em uma proteína é feita,
no interior de organelas celulares denominadas ribossomos, com o auxílio de um
tipo de RNA conhecido como RNA transportador (RNAt), da seguinte forma: cada
tripla ordenada de nucleotídeos consecutivos, como por exmplo {UAC}, ao longo
do RNAm, constitui aquilo que é denominado como códon. Cada códon responde
pela codificação de um determinado aminoácido, no caso do exemplo a Tirosina
(Tyr), conforme disposto na Tabela 1.2. As moléculas de RNAt são, geralmente,
pequenas, tendo cerca de 80 resíduos, e possuem uma região com grande afinidade
a um determinado códon, denominada anti-códon, e uma outra extremidade ligada
a um determinado aminoácido correspondente ao códon afim, de acordo com código
genético da Tabela 1.2. À medida em que o RNAm vai passando pelo ribossomo,
1.4
Introdução
8
um RNAt correspondente a cada um dos sucessivos códons acopla-se ao RNAm,
trazendo consigo o aminoácido equivalente ao códon em questão. Através da ação
de determinadas enzimas, esse aminoácido desprende-se do RNAt e une-se à cadeia
polipeptídica que, assim, vai sendo progressivamente formada. A tradução é finalizada assim que um stop códon é detectado, ou seja, a cada tripla ordenada de
nucleotídeos consecutivos do tipo {UAA, UGA, UAG}. Veja a Tabela 1.2.
Tabela 1.2: O código genético (RNAm)
1a posição
(extr. 5’)
U
C
A
G
2a posição (meio)
U
Phe (F)
Phe (F)
Leu (L)
Leu (L)
Leu (L)
Leu (L)
Leu (L)
Leu (L)
Ile (I)
Ile (I)
Ile (I)
Met (M)
Val (V)
Val (V)
Val (V)
Val (V)
C
Ser (S)
Ser (S)
Ser (S)
Ser (S)
Pro (P)
Pro (P)
Pro (P)
Pro (P)
Thr (T)
Thr (T)
Thr (T)
Thr (T)
Ala (A)
Ala (A)
Ala (A)
Ala (A)
A
Tyr (Y)
Tyr (Y)
STOP
STOP
His (H)
His (H)
Gln (Q)
Gln (Q)
Asn (N)
Asn (N)
Lys (K)
Lys (K)
Asp (D)
Asp (D)
Glu (E)
Glu (E)
3a posição
(extr. 3’)
G
Cys (C)
Cys (C)
STOP
Trp (W)
Arg (R)
Arg (R)
Arg (R)
Arg (R)
Ser (S)
Ser (S)
Arg (R)
Arg (R)
Gly (G)
Gly (G)
Gly (G)
Gly (G)
U
C
A
G
U
C
A
G
U
C
A
G
U
C
A
G
Repare que esse código é degenerado, uma vez que os 64 (43 ) possíveis códons
originam apenas 20 aminoácidos, sendo que cada aminoácido possui um código de
três letras e um outro código de uma letra apenas.
1.4
Organização da Dissertação
Após ter introduzido, no presente capítulo, conceitos básicos relativos as áreas
da Biologia relevantes à presente dissertação, que são de fundamental aplicação
neste trabalho, no Capítulo 2 será feito uma revisão bibliográfica, apresentando as
heurísticas mais utilizadas e problemas relacionados a sequência de caracteres e o
PCCP. No Capítulo 3, são abordados problemas relacionados ao PCCP e suas variações, com suas respectivas formulações, bem como o próprio Problema da Cadeia
de Caracteres mais Próxima, com seu conjunto de formulações e suas aplicações.
O Capítulo 4 mostra métodos heurísticos da literatura utilizados para solucionar
o PCCP e as metaheurísticas Iterated Greedy Search e Biased Random-Key Genetic Algorithm, implementadas nesta dissertação para resolvê-lo. No Capítulo 5, são
apresentadas as instâncias utilizadas para os devidos experimentos computacionais,
bem como os resultados dos testes. Por fim, as conclusões e considerações finais são
apresentadas no Capítulo 6.
Capítulo 2
Uma Revisão Bibliográfica
Neste capítulo serão descritos alguns dos trabalhos extraídos da literatura que
estão relacionados com o Problema da Cadeia de Caracteres mais Próxima (PCCP),
contendo os principais objetivos abordados, aplicações e métodos empregados para
resolver problemas de otimização em sequenciamento de cadeias de caracteres e suas
variações, como encontrar subseqüências de caracteres comuns a uma determinada
seqüência, determinar a presença de motifs em seqüências de DNA, RNA ou em
proteínas.
Para medir as similaridades ou diferenças entre duas seqüências de caracteres,
a maioria dos trabalhos citados abaixo utiliza a distância de Hamming, que é dada
pela soma das diferenças dos caracteres de mesma posição entre duas seqüências.
2.1
Revisão bibliográfica do Problema da Cadeia de
Caracteres mais Próxima
Ben-Dor et al. (1997) utiliza a palavra consenso para definir os caracteres de
uma seqüência. Utiliza Otimização Inteira para modelar o Problema da Cadeia de
Caracteres mais Próxima (PCCP) e usa um algoritmo de aproximação com base em
arredondamento randomizado, com razão de performance próxima do valor ótimo
para d, suficientemente grande, sendo d a maior distância a ser minimizada. Ele
também retrata em seu trabalho o Distinguishing String Selection Problem (DSSP).
Gasieniec et al. (1999) fornece um algoritmo de aproximação de tempo polinomial
para a solução do problema denominado Hamming Center Problem, que possui a
finalidade de encontrar uma cadeia de caracteres, construídas a partir de um alfabeto
binário, que minimize a distância de Hamming entre essa cadeia e as demais do
conjunto dado, as quais são constituídas do mesmo alfabeto e mesma dimensão.
Trabalhando com os problemas Closest String problem e Closest Substring Problem, Li et al. (2002) utiliza algoritmos de aproximação de tempo polinomial para a
solução dos problemas da seqüência mais próxima e da subseqüência mais próxima.
Algumas formulações para o problema foram baseadas no trabalho de Ben-Dor et al.
(1997), e o autor também fez uso do mesmo tipo de algoritmo utilizado no trabalho
de Gasieniec et al. (1999), para resolver o Hamming Center Problem.
Os três problemas estudados no trabalho de Deng et al. (2002) envolvem a busca
de um padrão que, com alguns erros, ocorre em um conjunto de seqüências (o Closest
9
2.1
Revisão bibliográfica do PCCP
10
String Problem), não ocorre em outro conjunto (o Farthest String Problem), ou em
ambos (o Distinguishing String Problem), e faz uso da distância de Hamming para
avaliar a proximidade entre seqüências. Segundo o autor, o seu trabalho tem diferentes tipos de objetivos e encontra aplicações em várias áreas, como a Genética, a
Correspondência de Padrões e a Teoria de Códigos. Neste trabalho é proposta, para
a solução dos problemas citados, uma formulação via algoritmos de aproximação em
tempo polinomial (Polinomial Time Approximation Schemes - PTAS).
Ecker et al. (2002) apresentou um modelo de otimização não-linear para encontrar locais de ligação a proteínas em cadeias de DNA. Foram utilizadas instâncias
de tamanho moderados, formadas pelas cadeias do DNA. Em seu trabalho, usou a
abordagem de probabilidade máxima para encontrar a melhor cadeia que se ajuste
aos dados de seqüência, maximizando a probabilidade das seqüências observadas.
Lanctot et al. (2003), além dos três problemas de seleção de cadeias que Festa
(2007) retrata em seu trabalho, aborda mais quatro problemas. São eles: Closest
Substring Problem, Farthest Substring Problem, Close to Most String Problem, Distinguishing String Selection Problem. A fim de solucionar estes problemas, o autor
propõe técnicas de relaxamento de otimização linear, algoritmos de aproximação e
um algoritmo heurístico. Para o Closest Substring Problem, foi utilizado um algo4
ritmo de aproximação com garantia de desempenho ( + ǫ), com valores pequenos
3
para ǫ > 0, bem como algumas formulações do trabalho de Ben-Dor et al. (1997)
para calcular a distância de Hamming e um método simples de relaxamento linear,
mostrando assim resultados eficientes.
O termo motifs foi relacionado no trabalho de da Fonseca (2003) para identificar
as subseqüências de caracteres, utilizando, como alfabeto, as bases nitrogenadas do
DNA. Em se tratando de Biologia Molecular Computacional, esses motifs representam, em geral, regiões altamente conservadas, isto é, pouco afetadas por mutações,
que desempenham funções biológicas específicas. Esse problema de localização de
motifs limita-se com o Problema do Casamento de Padrões e pode ser abordado
através das mesmas técnicas. O autor faz uso de algoritmos combinatórios exatos e
técnicas para encontrar as similaridades entre as seqüências baseadas na distância
de Hamming e na distância de Levenshtein, a qual é definida como o número mínimo de caracteres para substituir, inserir ou apagar, de modo a transformar uma
seqüência o mais próximo da outra.
Mauch H (2003) fez o uso de Algoritmos Genéticos com modificações, definindo
um novo algoritmo chamado GA Run, com o objetivo de solucionar problemas relacionados ao Problema da Cadeia de Caracteres mais Próxima (PCCP), tendo destaque
os problemas de sequenciamento com Post-Transcriptional Gene Silencing (PTGS)
ou RNA interference (RNAi).
No trabalho de Meneses et al. (2004) foi estudado o Problema da Cadeia de
Caracteres mais Próxima (PCCP). Os autores desenvolveram três formulações de
Otimização Inteira, mostrando que a terceira formulação, baseada nos trabalhos de
Ben-Dor et al. (1997) e Li et al. (2002), é a mais eficiente. Desenvolveram uma
heurística com o objetivo de estabelecer limites superiores para os valores ótimos
do PCCP, tornando mais rápida a aplicação do algoritmo branch-and-bound, que foi
usado com as técnicas de relaxamento da terceira formulação.
São utilizadas, três classes de instâncias, com dimensões variadas, para n =
2.1
Revisão bibliográfica do PCCP
11
{10, 15, 20, 25, 30} e m = {300, 400, 500, 600, 700, 800}, no trabalho de Meneses et al.
(2004). A primeira classe tem como alfabeto o conjunto {0, 1}; a segunda utiliza
um alfabeto de quatro caracteres; a terceira utiliza um alfabeto de 20 caracteres
(representando as seqüências de proteínas). Todas essas instâncias foram geradas
aleatoriamente, exceto 6 conjuntos de instâncias, que foram retiradas do trabalho
de McClure et al. (1994).
Os resultados computacionais se mostraram bastante interessantes, e foram comparados com a mesma formulação de Otimização Inteira, porém utilizando relaxamento linear no lugar do branch-and-bound. Para as instâncias com o alfabeto de 20
caracteres, os resultados foram mais significantes, na maioria dos casos conseguindo
alcançar soluções próximas do ótimo em menos de 1 minuto.
Quatro diferentes algoritmos heurísticos de construção e busca local para o Greedy Randomized Adaptive Search Procedures (GRASP) são apresentados por Pinto
et al. (2006). Além desses procedimentos, foram propostas duas estratégias de busca
intensiva, usando os conceitos de First Improvement (FI) e Best Improvement (BI).
A construção GRASP é a mesma para os quatro algoritmos, que se diferenciam na
busca local, uma determinística e outra aleatória, e nas estratégias de busca. O
número máximo de iterações GRASP foi de {n, 5n, 10n}, em que n é a dimensão de
cada seqüência, e os valores escolhidos para α = {0.1; 0.2; ...; 0.9}. Com o objetivo
de resolver o Problema da Cadeia de Caracteres mais Próxima (PCCP), o alfabeto
utilizado foi de 4 caracteres, com n = {300, 400, 500, 700} e m = {10, 15, 20, 25, 30}
(m é número de seqüências em cada conjunto), sendo que as instâncias testadas
foram retiradas do trabalho de Meneses et al. (2004). Cada instância foi executada cinco vezes. Destas cinco execuções foram calculadas as médias e os mínimos
das soluções xi encontradas. A partir daí, foram calculados os Gaps em relação às
soluções ótimas s∗ da seguinte forma:
P5
1
(
i=1 f (xi ))
Gapmédio = 5
− f (s∗ )
(2.1)
∗
f (s )
Gapmínimo =
min{f (xi ); i = 1, . . . , 5} − f (s∗ )
f (s∗ )
(2.2)
O termo Gap se refere à distância entre o valor procurado e os valores obtidos nos
testes. Os resultados obtidos pelos algoritmos implicaram melhorias na qualidade
das soluções, obtendo valores do Gap inferiores em relação aos encontrados por
Meneses et al. (2004).
Gramm et al. (2006) trata do problema Distinguishing Substring Selection (DSSS),
separando o conjunto de seqüências em duas partes, um conjunto de “boas” seqüências e outro de seqüências “ruins”, respeitando a métrica de Hamming. Foi apresentado um algoritmo exato de parâmetro-fixo para resolver o DSSS de forma eficiente,
baseando em algumas técnicas utilizadas por Lanctot et al. (2003) para resolver
um problema semelhante. O autor adaptou o algoritmo para a seqüência mais próxima ajudar a solucionar o DSSS. Foi mostrado que algoritmos utilizando Efficient
Polynomial-Time Approximation Scheme (EPTAS) não resultam em um boa solução para o DSSS.
Festa (2007) destaca que um dos problemas fundamentais em Biologia Molecular consiste em comparar seqüências genômicas em indivíduos de diferentes espécies,
2.1
Revisão bibliográfica do PCCP
12
determinando sua similaridade ou distância. Neste trabalho foi feita uma descrição
detalhada de problemas biológicos formulados como problemas de otimização combinatória. Uma nova heurística é proposta, com a finalidade de encontrar boas
soluções para uma classe particular desses problemas, conhecida como Far From
Most String Problem (FFMSP), dando uma ênfase especial à formulação matemática e a métodos eficientes de programação matemática, aplicados para resolvê-los.
Em seu trabalho, Festa (2007) ainda descreve outros dois problemas, o Closest String
Problem (CSP) e o Farthest String Problem (FSP).
Para solucionar o FFMSP, a autora implementou a heurística GRASP, escolhendo, de forma aleatória, os dois melhores candidatos para compor a Lista de
Candidatos Restrita (LCR). Para a busca local, o algoritmo 2-exchange, proposto
por Meneses et al. (2004), foi utilizado. As instâncias testadas foram comparadas com os resultados de Meneses et al. (2004), com n = {100, 150, 200} e m =
{300, 400, 500, 600, 800}. Os resultados obtidos com os testes foram as melhorias
das soluções ótimas acima de 10%.
Um algoritmo paralelo Multistart foi proposto por Gomes et al. (2008), para solucionar o Closest String Problem (CSP). O autor faz uso de uma heurística paralela,
combinando um algoritmo de aproximação com estratégias de busca local. O algoritmo 2-approximation, proposto no trabalho de Meneses et al. (2005), foi utilizado,
tendo algumas modificações nas estratégias de busca local, a qual usa vários processadores em uma máquina paralela. O autor ainda destaca o uso de uma matriz
de dimensão n para calcular mais rapidamente a distância de Hamming. Os testes
foram feitos com 20 processadores e comparados com um algoritmo exato, tendo o
objetivo de avaliar apenas as distâncias de Hamming encontradas e não o tempo
gasto no processamento. Algumas instâncias foram retiradas dos experimentos de
McClure et al. (1994) e do banco de dados GenBank. Uma parte das instâncias,
formadas pelo alfabeto Σ = {A, C, G, T }, era composta por 72% de seus caracteres
{C, G}. Foram realizados também testes com o alfabeto de 2, 4 e 20 caracteres.
Construindo um novo método para resolver o PCCP, Chen (2009) aplicou a
técnica Iterative Rounding, que foi empregada com sucesso no trabalho de Jain
(2001), auxiliando um algoritmo de aproximação para solucionar um problema de
redes de Steiner, considerado também um problema NP-Difícil. Utilizando uma
formulação com base em Otimização Inteira e aplicando técnicas de relaxamento
linear, o autor construiu um algoritmo mais ganancioso para solucionar o PCCP.
Os testes foram realizados com o conjunto de instâncias de McClure et al. (1994)
para um alfabeto de 4 caracteres. Os resultados foram comparados com os obtidos
pelo algoritmo Branch-and-Bound de Meneses et al. (2004). O algoritmo testado se
mostrou mais rápido com relação ao Branch-and-Bound, com soluções iguais ou em
alguns casos muito próximas.
Em um trabalho mais recente, Ma e Sun (2009) propuseram um método de
aproximação denominada Polinomial Time Approximation Schemes (PTAS), cuja
−2
complexidade é O(no(ǫ ) ). Este método, segundo os autores, é formulado para os
problemas Closest String Problem (CSP) e Closest Substring Problem, que tratam
da busca de uma seqüência ou subseqüência que seja similar, ao máximo, a uma
seqüência de um conjunto de cadeias dado. Os trabalhos que utilizam algoritmos
baseados em heurísticas, como aqueles encontrados nos estudos de Liu et al. (2005),
Mauch H (2003) e Meneses et al. (2004), não apresentam nenhuma garantia de
2.1
Revisão bibliográfica do PCCP
13
desempenho, mas, em contrapartida, os métodos de aproximação, desenvolvidos até
então, sacrificam a qualidade da solução em função da obtenção de um algoritmo
cujo tempo computacional seja polinomial. O autor desenvolveu também algoritmos
de parâmetros fixos, cuja complexidade é O(n|Σ|o(d) ), em que o raio d é o parâmetro
e Σ é o alfabeto. Como resultado, tem-se um algoritmo de tempo polinomial para
d = O(logn) e Σ de tamanho constante.
Faro e Pappalardo (2010) propuseram um novo algoritmo, chamado Ant-CSP,
com base no algoritmo Colônia de Formigas. Para avaliar o seu efeito e robustez, foi
comparado com dois outros algoritmos para o PCCP, um com base em Simulated
Annealing (SA), chamado de SA-CSP, e o outro em Algoritmo Genético (AG),
denominado GA-CSP, ambos utilizados por Liu et al. (2005) em seu trabalho. As
instâncias para os testes foram geradas aleatoriamente para um alfabeto Σ = 4, com
n = {10, 20, 30, 40, 50} e m = {10, 20, ..., 50} ∪ {100, 200, ..., 1000}. Os resultados
experimentais mostram que o algoritmo Ant-CSP proposto neste trabalho calcula
quase sempre melhores soluções e é muito mais rápido do que os algoritmos SA e
AG, independentemente do número e do comprimento de seqüências de entrada. Em
particular, para instâncias pequenas com 10 ≤ n ≤ 50, o algoritmo Ant-CSP é de 5
a 36 vezes mais rápido em relação ao GA-CSP.
Um novo método de aproximação é apresentado no trabalho de Chen et al.
(2010), denominado 3-string approach. Essa aproximação é utilizada pelos autores
para desenvolver novos algoritmos parametrizados para o PCCP. Os autores ainda
destacam uma vantagem entre esse método e aqueles desenvolvidos em trabalhos
anteriores, que utilizavam a técnica de 2-string approach (Chen (2009)). Segundo
os autores, intuitivamente esse novo método é melhor que os anteriores, pois, selecionando cuidadosamente três strings de entrada, ao invés de duas, o algoritmo
pode visitar uma porção maior da solução de saída. Segundo Chen et al. (2010), há
um ganho na complexidade dos algoritmos desenvolvidos com 3-string approach em
relação àqueles baseados em duas cadeias.
Trabalhando com dois tipos de problemas, Closest String Problem (CSP) e Closest Substring Problem (CSSP), Chimani et al. (2011) apresentou formulações em
otimização linear inteira para solucionar esses dois problemas. Para o CSSP, é
apresentada uma nova formulação, chamada de Polytope-Wise, superior à CSP,
pois evita suas extensões de formulação. Para os testes, foram utilizadas instâncias reais da Biologia e instâncias geradas aleatoriamente. Com dimensões de
K = {10, 20, 30, 40, 50}, que representam o número de seqüências em cada conjunto, n = {250, 500, 750, 1000, 2000, 5000, 10000}, que representam a dimensão de
cada seqüência, e com o alfabeto Σ = {2, 4, 20}. Os resultados foram comparados
com os trabalhos de Faro e Pappalardo (2010), Meneses et al. (2004) e Gomes et al.
(2008). Os experimentos mostraram que, para o problema CSP, seu tempo de execução foi muito satisfatório, e, mesmo para instâncias aleatórias, teve uma solução
perto da ótima.
No trabalho de Liu et al. (2011), foi apresentado um algoritmo exato, chamado
Distance First Algorithm (DFA), para solucionar problemas de CSP. Os autores
fizeram uma análise teórica para demonstrar que DFA consegue encontrar soluções
ótimas para um conjunto de três seqüências com alfabeto de tamanho dois. O mesmo
problema foi relatado também por Gramm et al. (2001), construindo o algoritmo
3-strings para solucionar este caso especial do CSP. Para os casos gerais do CSP, foi
2.1
Revisão bibliográfica do PCCP
14
projetado uma heurística polinomial, chamada LDDA-LSS, que é uma combinação
do algoritmo LDDA, proposto por Liu et al. (2004), com estratégias de busca local.
Essas estratégias são adaptadas dos trabalhos de Meneses et al. (2004) e Gomes
et al. (2008). Diferente destes autores, Liu et al. (2011) descreve como encontrar o
parâmetro N utilizado para definir o número de iterações do algoritmo.
Estas estratégias de busca local funcionam da seguinte forma: seja um conjunto
de seqüências S = {s1 , ..., sn }, com n seqüências de dimensões m. Então, seja t
a solução corrente e sindex uma string em S, tal que dH (si , t) é a maior distância
encontrada no conjunto, em que i = {1, 2, ..., n}. Então, para k = {1, 2, ..., m}, se
sindex
6= tk e substituindo tk por sindex
não faz a solução piorar, a substituição é feita
k
k
e a distância de Hamming entre t e todas as strings em S é computada. Depois de
verificar todas a m posições, uma nova string t é produzida e o processo se repete.
Os autores definem o número de iterações da seguinte forma:
N = m.|A|.b − rep
em que m é a dimensão da string, A é o tamanho do alfabeto e b−rep é pré-definido.
Depois de alguns testes experimentais, Liu et al. (2011) definiu b − rep = 0, 5,
para grandes instâncias com um alfabeto de 20 caracteres, e b − rep = 2, para os
demais casos. Para os devidos testes, os autores utilizaram dados biológicos reais e
simulados, sendo seis instâncias de alfabeto com 20 caracteres do conjunto de dados
do trabalho de McClure et al. (1994). As comparações foram feitas com o algoritmo
Exact, que faz uso de Otimização Inteira, o algoritmo proposto LDDA-LSS e o
Heuris-Seq, que é uma versão seqüencial da heurística proposta por Gomes et al.
(2008). Os resultados mostraram que o algoritmo proposto não é muito eficiente
para resolver instâncias pequenas, mas muito eficiente para instâncias de grandes
dimensões.
O trabalho de Zörnig (2011), por sua vez, apresenta um novo modelo de otimização linear inteira. Este modelo requer, segundo o autor, um número menor de
variáveis e restrições, o que representa uma melhoria no modelo de otimização linear
inteira binária utilizado em outros trabalho da literatura, como em Festa (2007) e
Meneses et al. (2004). Segundo Zörnig (2011), a redução do número de variáveis
e restrições do problema linear inteiro seria possível a partir do reconhecimento da
existência de isomorfismo entre colunas da matriz a ser tratada e a obtenção de
uma matriz denominada pelo autor de matriz normalizada. Essa normalização da
matriz proporciona, segundo o autor, a redução do tamanho do alfabeto. A solução
normalizada terá, então, o número de variáveis menor que a solução original, pois o
alfabeto desta terá no máximo o tamanho igual ao número de linhas da matriz.
Nos testes realizados pelo autor, foram aplicadas as instâncias geradas aleatoriamente a partir de alfabetos de tamanho 4 para cadeias cujo tamanho m pertence ao
intervalo 1000 ≤ m ≤ 2000, e também a partir de um alfabeto de tamanho 5 com
cadeias que possuem dimensão em torno de 3000 caracteres. A aplicação do modelo mostrado por Zörnig (2011) fica restrita a instâncias formadas por um reduzido
número de cadeias de no máximo 20.
Os resultados dos testes mostraram que em 14 das 20 instâncias o valor da função
objetivo da solução de arredondamento é o menor inteiro maior ou igual ao valor ideal
do relaxamento linear, tornando a solução aproximada do CSP, determinada pelo
arredondamento, uma solução ideal. Nos 6 casos restantes, o erro de aproximação
2.1
Revisão bibliográfica do PCCP
15
CSP é no máximo 1. Este trabalho chama a atenção pela técnica de álgebra linear
aplicada.
Usando técnicas de relaxação lagrangeana, Tanaka (2012) propõe um algoritmo
heurístico eficiente na resolução do CSP. A idéia principal é aplicar técnicas de relaxação lagrangeana para a formulação inteira-mista, permitindo obter uma solução
aproximada e, ao mesmo tempo, estreitar o limite inferior. O algoritmo proposto
é composto por duas partes. Na primeira, o algoritmo subgradiente resolve o problema dual lagrangeano (DLR). Segundo o autor, multiplicadores de Lagrange µ são
iterativamente atualizados para maximizar d∗ (µ). Este processo se repete até que
uma condição de término seja satisfeita. Na segunda etapa, é aplicada a metaheurística Busca Tabu para melhorar a solução. No procedimento Busca Tabu, Tanaka
(2012) fez uso de uma função de avaliação V , a qual avalia os melhores caracteres
para substituir por outros na solução inicial s. A seleção destes caracteres é feita
através da string mais distante em relação a s, escolhendo de forma determinística
os caracteres que se diferem entre essas duas seqüências. O critério para troca é
diminuir a distância máxima de Hamming entre s e as demais cadeias do conjunto.
A Busca Tabu é encerrada quando não houver melhora no valor da função objetivo
d, em movimentos sucessivos contabilizados por 4.N, sendo N é o número de strings
do conjunto.
As instâncias utilizadas para os testes foram as mesmas de Gomes et al. (2008),
com alfabeto Σ = {2, 4, 20} e instâncias simulando o genoma da “Actinobacteria”
Streptomyces coelicolor, cuja formação é composta de 72% dos caracteres GC, com
N = {10, 20, ..., 50} e a dimensão das strings dada por L = {1000, 2000, ..., 5000}.
As comparações do algoritmo proposto foram feitas com os seguintes trabalhos:
algoritmo paralelo Multistart de Gomes et al. (2008), comparando as médias do Gap;
o algoritmo CGSA de Liu et al. (2008), que utiliza como base a heurística Simulated
Annealing; o algoritmo GA proposto por Julstrom (2009) com L = 500 e Σ =
{2, 4, 10, 20, 30}; e Faro e Pappalardo (2010), com o algoritmo Ant-CSP, com todas
as strings de dimensão L = 1000 e Σ = 4. Os experimentos computacionais mostram
que o algoritmo proposto pôde encontrar boas soluções, ou soluções aproximadas, em
um tempo computacional muito rápido em relação a todas as heurísticas testadas.
Em um trabalho mais recente, de Souza (2012) implementou dois algoritmos
baseados nas metaheurísticas GRASP (Greedy Randomized Adaptative Search Procedure), ILS (Iterated Local Search) e AG (Algoritmo Genético), aplicando-os à
resolução do Problema da Cadeia de Caracteres mais Próxima (PCCP). Foram implementados quatro versões de algoritmos, a saber, GRASP-AG I e GRASP-AG II,
que se diferenciam na fase de construção GRASP; GRASP-ILS I e GRASP-ILS II,
que se diferenciam na escolha dos elementos a compor a Lista de Candidatos Restrita
(LCR). O algoritmo GRASP é responsável apenas pela fase de construção, sendo
a varredura do espaço de busca realizada pelos algoritmos AG e ILS. O método de
Descida Randômica é responsável pela busca local.
Após testes preliminares, verificou-se que o GRASP-AG I e GRASP-ILS I apresentaram melhores resultados computacionais em relação aos outros dois algoritmos.
As instâncias testadas no trabalho foram construídas a partir do alfabeto de quatro
caracteres do DNA dado por Σ = {A, C, T, G}. Os resultados foram comparados
com outros de Meneses et al. (2004), Gomes et al. (2008) e Mousavi e Esfahani
(2012). Para instâncias moderadas e grandes, os algoritmos apresentados atingiram
2.2
Uma Análise da revisão bibliográfica sobre PCCP
16
valores sub-ótimos razoáveis, porém, pouco competitivos em relação aos resultados
da literatura.
Em outro trabalho encontrado na literatura, que também faz uso da heurística
GRASP para solucionar o CSP, Mousavi e Esfahani (2012) utilizam uma função
heurística (cos(.)) de avaliação inspirada na teoria das probabilidades, a fim de
avaliar e comparar soluções candidatas. A função proposta pelos autores avalia o
beneficio de duas ou mais soluções candidatas diferentes, que possuam a mesma
distância de Hamming, diminuindo assim o custo computacional do algoritmo.
Essa nova função proposta por Mousavi e Esfahani (2012) funciona da seguinte
forma: dadas duas soluções candidatas x1 e x2 , é dada à solução x1 um valor maior
que o de x2 se e somente se ocorrem f (x1 ) < f (x2 ) ou f (x1 ) = f (x2 ) e cos(x1 ) <
cos(x2 ), em que: f (.) é a função da avaliação tradicional e cos(.) é a nova função
heurística desenvolvida pelos autores. Segundo os autores, esse tipo de avaliação
sugere que o número de mínimos locais poderá ser reduzido, quando for utilizada a
função cos(.) no lugar de f (.) para avaliar soluções candidatas.
A fase de construção GRASP é avaliada por essa função heurística, e foi ajustada
para atingir um equilíbrio adequado entre a escolha aleatória e gulosa dos candidatos
para compor a Lista de Candidatos Restrita (LCR). Já a busca local é feita por um
algoritmo de melhoria iterada.
Os resultados experimentais obtidos pelo algoritmo GRASP-CSP de Mousavi
e Esfahani (2012) foram comparados com os resultados das seguintes heurísticas
propostas para o CSP: CGSA por Liu et al. (2008); Ant-CSP por Faro e Pappalardo
(2010); a heurística DBCGA, do trabalho de Julstrom (2009); e o algoritmo exato
Mismatch count, de Hufsky et al. (2010).
Os parâmetros utilizados no GRASP-CSP, implementados no trabalho de Mousavi e Esfahani (2012) foram: Lista de Candidatos Restrita (LCR) com tamanho
2, 10 iterações do algoritmo e número de execuções igual a 20. A fim de demonstrar a ineficiência dos métodos exatos, em especial o Mismatch Count, foram geradas aleatoriamente, segundo os autores, 18 instâncias de tamanho reduzido com
um alfabeto binário (|Σ| = 2), com n = {10, 20, 30} (número de seqüências) e
m = {10, 20, 30, 40, 50, 100} (dimensões das seqüências).
As comparações entre os resultados do algoritmo GRASP-CSP, implementado
no trabalho de Mousavi e Esfahani (2012), e aqueles encontrados pelas heurísticas
dos trabalhos de Liu et al. (2008), Faro e Pappalardo (2010) e Julstrom (2009),
foram feitas com vários grupos de instâncias constituídas por alfabetos pertencentes
ao conjunto Σ = {2, 4, 10, 20, 30}. Para alguns casos com valores de m ≤ 50, as
soluções obtidas pelo algoritmo GRASP-CSP foram iguais, porém com o tempo de
processamento reduzido. Para os demais casos, o algoritmo teve um desempenho
superior e com um tempo bem abaixo das demais comparações.
2.2
Análise da Revisão Bibliográfica sobre PCCP
A seguir, a Tabela 2.1 contém os resultados da literatura referente aos autores
citados anteriormente, com destaque para o tipo de problema tratado e os métodos
utilizados para resolvê-los.
Para encontrar uma solução viável para problemas relacionados ao PCCP, há
2.2
Uma Análise da revisão bibliográfica sobre PCCP
17
Tabela 2.1: Resultados da literatura.
Autor
Ben-Dor (1997)
Gasieniec et al. (1999)
Li et al. (2002)
Deng et al. (2002)
Ecker et al. (2002)
Lanctot et al. (2003)
Mauch (2003)
Fonseca (2003)
Problema
CSP e DSSP
Hamming Center
Problem
Closest String problem e
Closest Substring problem
Closest String problem e
Farthest String Problem e
Distinguishing String Problem
Encontrar locais de
ligação a proteínas em
cadeias de DNA
CSP, FSP, Close to Most
String Problem, Distinguishing
String Selection Problem.
CSP
subseqüência de caracteres
(motifs)
Meneses et al. (2004)
PCCP
Pinto et al. (2006)
Gramm (2006)
PCCP
DSSS
Festa (2007)
CSP, FSP, FFMSP
Jing-Chao (2007)
Gomes et al. (2008)
Ma e Sun (2009)
CSP
PCCP
CSP, CSSP
Faro e Pappalardo (2009)
Chen et al. (2010)
Chimani (2011)
PCCP
Closest String Problem
CSP, CSSP
Liu et al. (2011)
CSP
Zornig (2011)
CSP
Tanaka (2012)
CSP
Mousavi e Esfahani (2012)
Souza (2012)
CSP
PCCP
Metodologia
Algoritmo de aproximação
Algoritmo de aproximação
de tempo polinomial
Algoritmo de aproximação
de tempo polinomial
Polinomial Time
Approximation Schemes
(PTAS)
Nonlinear Programming
(NLP)
Técnicas de Relaxamento de
Programação linear, Algoritmos de
Aproximação e Algoritmo heurístico
GA Run
Algoritmos Força-bruta,
Knuth-Morris-Pratt (KMP)
e Boyer-Moore (BM)
Otimização Inteira, uma
heurística e um Algoritmo
branch-and-bound
Algoritmos heurísticos GRASP
Algoritmo exato
de parâmetro-fixo
Otimização Combinatória,
heurísticas GRASP
Iterative Rounding
Algoritmo Paralelo Multistart
Polinomial Time Approximation
Schemes (PTAS)
Algoritmo Ant-CSP
Algoritmo 3-string approach
formulações do tipo Integer
Linear Program (ILP)
algoritmo exato Distance
First Algorithm (DFA)
Programação Linear Inteira
Relaxamento LP
Técnicas de Relaxação Lagrangeana,
Algoritmo Heurístico e a
Meta-heurística Busca Tabu
GRASP
GRASP, ILS e AG
o uso freqüente de metaheurísticas híbridas, algoritmos de aproximação de tempo
polinomial, heurística de busca local e o uso de Otimização Inteira. Estes métodos
são os mais utilizados para se obter uma solução rápida e de boa qualidade, otimizando, assim, os problemas relacionados a seqüências de caracteres, seja o objetivo
encontrar a cadeia mais próxima ou a mais distante.
Capítulo 3
Caracterização do Problema
Esse capítulo irá abordar o Problema da Cadeia de Caracteres mais Próxima
(PCCP) que, segundo a literatura, está entre os mais importantes problemas estudados pelos pesquisadores da Biologia Computacional. Em muitos problemas que
ocorrem nessa área, existe uma necessidade de comparar e encontrar características
comuns em seqüências de DNA, RNA e proteínas. Em se tratando de otimização
combinatória, o PCCP é considerado um problema NP-difícil.
Segundo a literatura, o Problema da Cadeia de Caracteres mais Próxima é um
dos vários problemas constituintes da classe de problemas da Biologia Computacional e da Teoria dos Códigos. Em destaque, tem-se a descoberta de alvos potenciais
para medicamentos, criação de testes diagnósticos e identificação de padrões em
seqüências de proteínas. Um dos principais objetivos deste trabalho é encontrar
uma seqüência (string) ou subseqüência (substring) de caracteres, que se aproxime
ao máximo da estrutura de um determinado conjunto de seqüências, formadas pelos mesmos grupos de caracteres, como as bases nitrogenadas do DNA, RNA ou
seqüências de proteínas. Para medir estas semelhanças, é utilizado como métrica a
distância de Hamming. A distância de Hamming entre duas seqüências de caracteres de mesma dimensão corresponde ao número de posições nas quais as seqüências
diferem.
A escolha da utilização da distância de Hamming se deve ao fato de ser a mais
utilizada em toda a literatura, empregada também no trabalho de Meneses et al.
(2004), e por ser a mais simples e objetiva forma de determinar as similaridades ou
diferenças entre duas seqüências.
O presente Capítulo está organizado como segue: a próxima seção introduz os
problemas mais importantes em Biologia Computacional, abordados no trabalho
de Festa (2007). A Seção 3.2 apresenta o Closest String Problem. A Seção 3.3
apresenta o Problema da Cadeia de Caracteres mais Distante ou Farthest String
Problem(FSP); a Seção 3.4 mostra o Far From Most String Problem (FFMSP);
a Seção 3.5 apresenta outros tipos de problemas relacionados com seqüências de
caracteres, estudados por Lanctot et al. (2003) e outros autores e, por fim, na Seção
3.6 será apresentada uma formulação proposta por Meneses et al. (2004) para a
solução do PCCP, tema desta dissertação, com algumas definições e exemplos.
18
3.1
Caracterização do Problema
3.1
19
Alguns problemas de comparação e seleção de
cadeias
Segundo Festa (2007), problemas de comparação e seleção de cadeias pertencem
a uma classe da Biologia Molecular mais conhecida como seqüências de consenso,
em que um conjunto finito de seqüências é dado, e o objetivo é encontrar o seu
consenso, ou seja, uma nova seqüência que concorde, tanto quanto possível, com
todos elementos de uma seqüência dada.
Alguns destes problemas são apresentados por Li et al. (1999). Dentre eles, estão:
(i) Consensus Patterns: dado um conjunto de seqüências S = {s1 , s2 , ..., sn }, com
|si | = m, e um número inteiro L, encontrar a string mediana s e uma substring
ti (Consensus Patterns), ambas com dimensão L, de cada si , minimizando
n
X
dH (s, ti ); e
i=1
(ii) Star Alignment: dado um conjunto de seqüências S = {s1 , s2 , ..., sn }, com
n
X
|si | = m, encontrar a seqüência mediana s minimizando
dE (si , s), em que
i=1
dE denota a distância edit.
De acordo com Festa (2007), os seguintes problemas abordados em seu trabalho
também estão relacionados com seqüências de consenso:
(i) o consenso é uma nova seqüência, cuja distância total, a partir de todas as
seqüências de um dado conjunto, é a menor possível (Closest String Problem);
(ii) o consenso é uma nova seqüência, cuja distância total a partir de todas as
seqüências de um dado conjunto é a maior possível (Farthest String Problem);
(iii) o consenso é uma nova seqüência, e este problema consiste em determinar
uma seqüência que seja a mais distante possível de um conjunto de seqüências
dadas (Far From Most String Problem).
As formulações matemáticas referentes aos três problemas citados são apresentados a seguir. As seguintes notações são utilizadas nestes três problemas:
• um alfabeto Ω = {c1 , c2 , · · · , ck } é um conjunto finito de elementos chamados
caracteres;
• uma seqüência s = {s1 , s2 , · · · , sm }, em que |s| = m, sendo m a dimensão
da seqüência s, ou seja, o número de cadeias que s possui, formadas pelo
alfabeto Ω, de modo que os caracteres si que compõem a cadeia pertencem a
Ω, i = 1, 2, · · · , m;
• Dadas duas seqüências s e t em Ω, tais que |s| = |t|, a distância de Hamming
entre s e t, denotada por dH(s,t) , é calculada pela expressão:
dH(s,t) =
|s|
X
i=1
φ(si , ti ),
(3.1)
3.2
Caracterização do Problema
20
em que a função φ(·) é tal que:
φ : Ω × Ω → {0, 1}
(3.2)
sendo:
φ(a, b) =
0, se a = b;
1, caso contrário.
(3.3)
Deve ser observado que a distância de Hamming entre duas cadeias a e b pode
ser calculada desde que as duas cadeias tenham o mesmo número de caracteres.
Essa distância é dada pela soma de uma unidade ao valor atual da distância para as
posições em que os caracteres são diferentes. Caso esses mesmos caracteres sejam
iguais, somaremos zero ao valor da distância atual. Esse procedimento do somatório
se repete para cada cadeia de uma instância. A seguir, um exemplo de como encontrar a distância de Hamming entre uma seqüência dada e as demais cadeias de um
conjunto.
Exemplo 3.1 Seja o alfabeto Ω = {A, C, G, T } e um conjunto de cadeias de caracteres S = {s1 , s2 , s3 }, formadas pelo alfabeto Ω, em que s1 = (GAT T G), s2 =
(GAT CA), s3 = (CT CGA). Se t = (GAT T C), determine a distância de Hamming
entre t e as demais cadeias do conjunto S.
• No conjunto S, tem-se: número de cadeias de caracteres em S é m = 3 e
|s1 | = |s2 | = |s3 | = 5 (dimensão de cada cadeia em S);
• Sendo |t| = 5, segue que |s1 | = |s2 | = |s3 | = |t|;
• Então, a distância de Hamming entre t e s1 , s2 , s3 é dada por: dH (s1 , t) = 1;
dH (s2 , t) = 2; dH (s3 , t) = 5
Todas essas seqüências possuem a mesma dimensão e são construídas a partir
de um único alfabeto, que é utilizado para definir as cadeias de caracteres. Estas
cadeias são utilizadas para representar as bases nitrogenadas do DNA, na forma do
alfabeto Ω = {A, C, G, T }.
3.2
Closest String Problem (CSP)
Dado um conjunto finito de n seqüências Σ = {s1 , s2 , . . . , sn } em Ω, cada um
de comprimento m, ou seja, de modo que si ∈ Ωm , i = 1, 2, . . . , n, o Problema da
Cadeia de Caracteres mais Próxima, ou (CSP), é encontrar uma seqüência central
t ∈ Ωm , ou seja, uma seqüência t de comprimento m, tal que a distância de Hamming
entre t e todas as outras seqüências em Σ seja mínima, ou seja:
dH (t, si ) ≤ d, ∀si ∈ Σ
(3.4)
O presente problema pode ser formulado como um problema de Otimização Inteira. Seja vk um conjunto de caracteres que aparecem na posição k no conjunto de
3.3
Caracterização do Problema
21
seqüências em Σ. Para cada k = 1, 2, . . . , m e j ∈ vk , define-se a variável de decisão
binária:
1, se o j-ésimo caractere em vk for utilizado na posição k;
xjk =
(3.5)
0, caso contrário.
De acordo com Festa (2007), o CSP admite a seguinte formulação matemática:
(CSP )
(3.6)
min d
sujeito a:
X
xjk = 1,
k = 1, 2, . . . , m
(3.7)
j∈vk
m−
m
X
xsij j ≤ d,
i = 1, 2, . . . , n
(3.8)
j=1
d ∈ N+ , xjk ∈ {0, 1},
k = 1, 2, . . . , m, ∀j ∈ vk .
(3.9)
Este problema foi primeiramente estudado na área da Teoria de Códigos (Roman
(1992)) e, mais tarde, sua intratabilidade computacional foi provado por M. Frances (1997) e Lanctot et al. (1999). Quando o valor de dH é muito pequeno, este
é o objetivo a ser alcançado por pesquisadores em genética, encontrando regiões
semelhantes, as quais se associariam a uma seqüência complementar de uma droga
alvo. Alguns autores, como Lanctot et al. (2003) e Li et al. (2002), apresentaram
esquemas de aproximação de tempo polinomial (Polynomial Time Approximation
Scheme) (PTAS) para solucionar o CSP.
Esta formulação para o CSP também pode ser encontrada no trabalho de Meneses et al. (2004), que apresenta outras duas formulações com base em Otimização
Inteira para solucionar o CSP.
3.3
Farthest String Problem(FSP)
Segundo Festa (2007), o Farthest String Problem - FSP pode ser útil em situações
como encontrar uma seqüência genética que não pode ser associada a um grupo de
espécies. Dado um conjunto finito de seqüências Σ = {s1 , s2 , . . . , sn }, um problema
complementar para o CSP é encontrar uma seqüência t ∈ Ωm mais distante das
seqüências em Σ.
De acordo com (Festa, 2007), o FSP também pode ser formulado como um
problema de Otimização Inteira. Seja, então, a variável de decisão xjk definida
como na expressão (3.5). Então, o problema (FSP) pode ser definido como:
(F SP )
max
d
(3.10)
3.4
Caracterização do Problema
22
sujeito a:
X
xjk = 1,
k = 1, 2, . . . , m
(3.11)
j∈Vk
m−
m
X
xsij j ≥ d,
i = 1, 2, . . . , n
(3.12)
j=1
d ∈ N+ , xjk ∈ {0, 1},
k = 1, 2, . . . , m, ∀j ∈ Vk .
(3.13)
A intratabilidade computacional do FSP foi demonstrada em Lanctot et al.
(2003), provando que o problema continua sendo intratável para um alfabeto com
apenas dois caracteres. O autor ainda mostra que existe uma PTAS para solucionar
o FSP.
Observe que a formulação matemática para o FSP é bastante semelhante à usada
pelo CSP, com apenas algumas mudanças no objetivo de otimização e o sinal de
desigualdade na restrição. Assim, para solucionar o problema, podem ser usadas
técnicas semelhantes como as empregadas para a solução do CSP.
3.4
Far From Most String Problem(FFMSP)
O Far From Most String Problem (FFMSP) é um dos problemas pertencentes a
um grupo chamado de problemas de seleção e comparação de cadeias de caracteres,
que pertencem a uma classe mais geral de problemas, conhecida como seqüências
consenso.
Dado um conjunto finito de seqüências, o objetivo é encontrar seu consenso, isto
é, uma nova seqüência que seja a mais próxima possível de todas as seqüências de
um dado conjunto. Em outras palavras, o objetivo é determinar uma seqüência
chamada consenso, porque ela representa, de alguma forma, todas as seqüências de
um determinado conjunto. Para o FFMSP, o objetivo é encontrar uma seqüência
que está distante do maior número de seqüências possíveis de um dado conjunto
com seqüências de mesma dimensão.
Um problema estreitamente relacionado com o FSP é o FFMSP. De acordo
com (Festa, 2007), a formulação para o FFMSP pode ser representada da seguinte
maneira.
Dado um limitante t, uma seqüência s deve ser encontrada a fim de maximizar
a variável x, de modo que:
dH (s, si ) ≥ t,
para si ∈ P ⊆ Σ e |P | = x.
(3.14)
Nesta formulação, P é um subconjunto de Σ, tendo cardinalidade dada por x.
Desse modo, aumentar o valor de x equivale a aumentar o número de cadeias das
quais a cadeia s a ser encontrada está em sua distância máxima. Neste caso, desejase encontrar uma string que seja o mais distante possível da maior parte das strings
do conjunto. No FSP, o objetivo é encontrar uma string que seja a mais distante
de todos os elementos de um conjunto.
3.5
Caracterização do Problema
23
Em um trabalho mais recente, Ferone et al. (2013) implementaram cinco heurísticas para solucionar o FFMSP. A primeira utiliza apenas o GRASP convencional; a
segunda faz uso da metaheurística Variable Neighbourhood Search (VNS) proposta
por Hansen e Mladenovic (2002); no terceiro método os autores utilizaram uma heurística híbrida, formada pelo GRASP com a heurística Path-relinking proposta por
Glover (1997), a qual aborda estratégias de intensificação, explorando trajetórias
ligadas à solução elite. No quarto método, outra heurística híbrida, formada pela
metaheurística VNS e Path-relinking. Por último, a composição dos três métodos
(GRASP, VNS e Path-relinking), sendo o método que obteve os melhores resultados,
quando comparado com os demais métodos citados.
3.5
Outros problemas relacionados
Além dos três problemas citados por Festa (2007), Lanctot et al. (2003) em seu
trabalho aborda mais outros quatro problemas: Closest Substring Problem, Farthest
Substring Problem, Close to Most String Problem e Distinguishing String Selection
Problem (DSSP). Todos eles reduzem-se à tarefa de encontrar um padrão que, com
algum erro, ocorre em algum conjunto de cadeias de caracteres (Closest Substring
Problem e suas variações) e não ocorrem em outro conjunto (Farthest String Problem
e suas variações). A seguir, outros problemas relacionados por Lanctot et al. (2003).
3.5.1
Closest Substring Problem
Dado um conjunto de seqüências S = {s1 , s2 , ..., sn } com |si | = m para i =
1, 2, ..., n, formadas por um alfabeto A e um número inteiro L, o objetivo é encontrar
uma seqüência (ou string) centro s de comprimento L minimizando d, tal que,
para cada si ∈ S, existe uma subseqüência (substring) ti de comprimento L com
dH (s, ti ) ≤ d .
O Closest Substring Problem é uma versão mais geral do Closest String Problem,
sendo também considerado um problema NP-Difícil. Em aplicações como identificação do alvo de drogas e projetos de teste genético, o raio d geralmente é pequeno.
Segundo Li et al. (2002), quando o raio d é pequeno, a string centro pode ser também
usada como motifs para vários problemas em alinhamento de seqüências, conforme
mostram McClure et al. (1994) e da Fonseca (2003).
3.5.2
Farthest Substring Problem
Dado um conjunto de seqüências Sf = {s1 , s2 , ..., sn } com |si | = m para i =
1, 2, ..., n, formadas por um alfabeto A e um número inteiro K, o objetivo é encontrar uma seqüência centro s de comprimento K maximizando df tal que, para cada
si ∈ Sf existe uma subseqüência ti de comprimento K com a distância de Hamming dH (s, ti ) ≥ df . O Farthest Substring Problem pode também ser formulado
como o Farthest String Problem citado por Festa (2007), é claro fazendo algumas
adaptações. Ambos os problemas são considerados NP-Difícil.
Um outro problema relacionado com subseqüências de caracteres é o Problema da
Maior Subseqüência Comum ou LCS - (Longest Common Subsequence), que possui o
3.6
Caracterização do Problema
24
objetivo de encontrar a subseqüência mais longa, comum a todas as seqüências de um
determinado conjunto. No trabalho de Hirschberg (1975), o autor desenvolveu um
algoritmo para solucionar o LCS em um espaço linear. Partindo de um alinhamento
global, a idéia era encontrar o ponto médio pelo qual passa um alinhamento ótimo.
3.5.3
Close to Most String Problem
Esse problema pode ser melhor explicado com a seguinte consideração, as vezes
é impossível encontrar uma seqüência que está longe ou perto de todas as seqüências
em um conjunto, sendo melhor a seguinte restrição, ser tão longe ou perto de tantas
seqüências desse conjunto, o quanto possível. Isso nos leva a dois tipos de problemas
o Far From Most String Problem(FFMSP) abordado no trabalho de Festa (2007) e
o Close to Most String Problem, que será definido a seguir.
Dado um conjunto Sc de seqüências de dimensão m pertencentes a um alfabeto
A e um limitante Kc > 0. O objetivo é encontrar uma string x de dimensão m
maximizando o número de strings si em Sc , satisfazendo a seguinte restrição da distância de Hamming dH (x, si ) ≤ Kc . Em outras palavras, nesse problema o principal
objetivo a ser alcançado é encontrar o maior número de seqüências possíveis, que
satisfaçam o limite da distância de Hamming, se diferenciando do Close String Problem, no qual, o objetivo é encontrar uma seqüência que se aproxime o mais perto
posssível de todas as demais seqüências do conjunto.
No trabalho de Boucher et al. (2012), os autores alanisam a intratabilidade do
Close to Most String Problem para quando o alfabeto é binário (|Σ| = 2), a partir do
problema abordado nos trabalhos de Ma (2000) e Lanctot et al. (2003). E provam
através de um teorema que tanto o Close to Most String Problem quanto o Far From
Most String Problem são NP-Difícil, para um alfabeto binário.
3.5.4
Distinguishing String Selection Problem (DSSP)
Este problema, também abordado no trabalho de Deng et al. (2002), pode ser
definido como se segue. Dado dois conjuntos Sc e Sf ambos de dimensão m, pertencentes a um alfabeto A e dois números inteiros positivos Kc (raio superior) e Kf
(raio inferior) com Kc ≤ Kf . O objetivo é encontrar uma string x ∈ Am tal que,
para cada string ci ∈ Sc , dH (x, ci ) ≤ Kc , e para cada string fi ∈ Sf , dH (x, fi ) ≥ Kf .
Alguns autores como Gramm et al. (2006) e Deng et al. (2002) distinguem Sc
como um conjunto de ’bad ’ strings e Sf como ’good ’ strings. O DSSP possui mais
dificuldade na resolução do que os outros problemas principalmente por causa dos
dois objetivos na sua descrição, sendo assim considerado NP-Difícil.
O DSSP tem o potencial de ajudar na seleção do alvo de drogas como por exemplo: dado um conjunto de seqüências de genes ortólogos (o mesmo gene em diferentes
organismos) de um grupo de patógenos (micro-organismo específico que causa doenças) intimamente relacionados, e um ’hospedeiro’ (como seres humanos ou animais),
o objetivo seria encontrar uma seqüência essencial que é mais conservada em todas
ou na maioria dos patógenos, mas não tão conservada nos ’hospedeiros’. A proteína
codificada por este fragmento pode ser um alvo para o desenvolvimento de novos
antibióticos. Este problema é melhor abordado no trabalho de Jiang et al. (2000).
3.6
Caracterização do Problema
3.6
25
Problema da Cadeia de Caracteres mais Próxima (PCCP)
No Problema da Cadeia de Caracteres mais Próxima - PCCP, tema desta presente
dissertação, deseja-se encontrar uma seqüência de caracteres t que se aproxime ao
máximo, segundo uma métrica, de todas as seqüências de um dado conjunto, no
qual as cadeias de caracteres possuem a mesma dimensão. Neste trabalho, a idéia
principal é encontrar uma seqüência centro t que se assemelhe, ao máximo, a um
conjunto de cadeias dado, ou seja, o objetivo é minimizar a distância máxima desta
cadeia de caracteres t às demais cadeias do conjunto.
Vários tipos de medidas têm sido propostas para encontrar as similaridades (ou
diferenças) entre as seqüências. A mais utilizada é a distância de Hamming, uma métrica que aparece em vários contextos ((Andronescu e Rastegari, 2003), (Yamamoto,
2004), entre outros). Uma justificativa técnica para o uso freqüente da distância de
Hamming na comparação de seqüências em Biologia Molecular pode ser encontrada
em Li et al. (1999). A distância de Hamming entre duas cadeias de caracteres é a
soma das diferenças de cada caractere de mesma posição, sendo uma delas a solução
corrente e a outra, uma cadeia do conjunto.
De acordo com M. Frances (1997) , o PCCP é conhecido como um problema
NP-difícil, ou seja, tem uma complexidade não-polinomial. Sendo assim, as técnicas
mais comumente empregadas para resolver problemas NP-Difíceis são algoritmos
heurísticos e algoritmos exatos que possuem complexidade não polinomial.
O trabalho de de Souza (2012) apresenta uma aplicação das heurísticas Greedy
Randomized Adaptative Search Procedure (GRASP), Iterated Local Search (ILS) e
Algoritmo Genético (AG), sendo utilizado um alfabeto de quatro caracteres para as
seqüências do conjunto.
O modelo apresentado a seguir está posto em Meneses et al. (2004), sendo também utilizado em Kelsey e Kotthoff (2010), Soleimani-damaneh (2011), dentre outros
trabalhos. Em seu trabalho, Meneses et al. (2004) apresenta outros dois tipos de
formulação com base em Otimização Inteira, mas considera este modelo apresentado
o mais apto para encontrar melhores soluções.
Sejam, então, as variáveis de decisão zki , definidas como:
1, se tk 6= xik ;
i
zk =
(3.15)
0, caso contrário.
O PCCP, assim, é formulado como:
(P CCP )
sujeito a:
n
X
min d
zki ≤ d i = 1, ..., n
(3.16)
(3.17)
k=1
≤ kzki i = 1, ..., n; k = 1, ...m
(3.18)
xik − tk ≤ kzki i = 1, ..., n; k = 1, ...m
(3.19)
zki ∈ {0, 1} i = 1, ..., n; k = 1, ...m
(3.20)
tk −
xik
3.6
Caracterização do Problema
26
d ∈ Z+
(3.21)
tk ∈ Z; k = 1, ...m
(3.22)
Neste modelo, tem-se que:
• k é o tamanho do alfabeto usado;
• d representa a diferença máxima entre t e a cadeia de caracteres testada, e é
o valor a ser minimizado;
• a restrição (3.17) determina o limite inferior para o valor d, que deve ser maior
ou igual ao número total de diferenças para cada cadeia do conjunto;
• as restrições (3.18) e (3.19) determinam os limites inferior e superior para a
diferença entre tk − xik ;
• as restrições (3.20) a (3.22) garantem valores inteiros para a solução.
No início do processo, a distância de Hamming dH recebe o valor zero e, a
cada diferença encontrada entre elementos de uma mesma posição, mas em cadeias
diferentes, é acrescida uma unidade ao valor de dH . O processo se repete até que
todas as cadeias da instância dada sejam comparadas com a cadeia que representa
a solução atual, que deverá ser modificada com a finalidade de minimizar o valor de
dH . Essa distância deverá ser minimizada, mantendo todas as outras abaixo dela.
Desta forma, não basta apenas calcular essa distância na totalidade das cadeias,
mas obter o valor da distância de Hamming individualmente e fazer alterações na
solução que minimize essa distância encontrada. Esse valor poderá se modificar de
uma linha para outra, porém deve diminuir a cada busca. Mais detalhes sobre a
distância de Hamming e sua formulação podem ser encontrados na Seção 3.1.
A seguir um exemplo de como pode ser construída uma seqüência centro t, reduzindo a distância de Hamming entre as cadeias de caracteres de um dado conjunto:
Exemplo 3.2 Dado um conjunto de seqüências S = {s1 , s2 , s3 }, formadas pelo alfabeto Ω = {A, C, T, G}, com s1 = (GAT T G), s2 = (GAT CA) e s3 = (CT CGA). Encontrar uma string centro t, que minimize a maior distância de Hamming (max dH )
em relação às strings do conjunto S.
• Seja t = (GAT T C) a solução inicial para o problema, construída a partir de
algum algoritmo de construção.
• Verificando a dH entre t e s1 , s2 , s3 , tem-se que: dH (s1 , t) = 1, dH (s2 , t) = 2 e
dH (s3 , t) = 5.
Após a comparação da string t, obtida na solução inicial, com as demais cadeias
de caracteres do conjunto S, o objetivo é diminuir o valor max dH , o qual foi encontrado entre t e s3 . Este procedimento pode ser feito através de algum algoritmo de
busca local, fazendo alterações nos caracteres da string t, escolhidos aleatoriamente,
afim de diminuir o max dH computado.
3.6
Caracterização do Problema
27
• Se for trocado o caractere G por C, como uma escolha aleatória dentre os
elementos do alfabeto Ω, na string t obtém-se uma nova string t, que pode ser
chamada de t′ , sendo t′ = (CAT T C).
• Verificando as distâncias em relação a t′ : dH (s1 , t′ ) = 2, dH (s2 , t′ ) = 3 e
dH (s3 , t′ ) = 4. Apesar do dH em relação às strings s1 e s2 terem aumentado,
o objetivo principal é diminuir o valor max dH , o que foi feito em uma unidade.
Então, a string t′ é considerada a melhor solução até o momento.
• Fazendo alterações aleatórias na string t′ para t′′ = (CAT T A), com o objetivo
de encontrar uma solução melhor.
• Então, são encontrados as seguintes distâncias: dH (s1 , t′′ ) = 2, dH (s2 , t′′ ) = 2
e dH (s3 , t′′ ) = 3, com o max dH (dado pela distância entre s3 e t′′ ) diminuindo
em mais uma unidade. Este processo é repetido até que se encontre soluções
melhores, ou até que algum critério de parada seja atingido, como número de
iterações ou tempo limite de processamento.
Como pode-se observar no exemplo, o objetivo do PCCP é encontrar uma seqüência de caracteres que seja a menos distante possível de todos os elementos de um
determinado conjunto. Os conjuntos de cadeias de caracteres utilizados para os experimentos computacionais nesta dissertação serão bem maiores do que o citado no
exemplo anterior, tanto na dimensão do conjunto quanto na dimensão das seqüências, tornando a busca por uma solução ótima ainda mais difícil de ser atingida.
Este processo será feito através de heurísticas computacionais, que deverão fazer
modificações sucessivas na solução inicial, diminuindo a cada passo a maior distância
de Hamming. Nesse processo, deve-se importar apenas com a maior distância, que
a cada processo de modificação irá se aproximando da distância mínima. Por isso,
a seqüência t é chamada de seqüência centro.
Para a solução do PCCP, serão implementadas duas heurísticas, uma com base
no framework do algoritmo BRKGA e outra utilizando a heurística IGS. Este procedimento será melhor descrito no Capitulo 4.
Capítulo 4
Metodologia de Pesquisa
4.1
Visão Geral
Problemas de otimização consistem em determinar a melhor combinação dentre
um conjunto de variáveis para maximizar ou minimizar uma função, geralmente
chamada de função objetivo ou função custo. Esses problemas podem ser divididos
em três categorias: aqueles cujas variáveis assumem valores reais (ou contínuos),
aqueles cujas variáveis assumem valores discretos (ou inteiros) e aqueles em que
há variáveis inteiras e contínuas, classificados, respectivamente, como problemas de
Otimização Contínua, Otimização Combinatória ou Discreta, e Otimização Mista.
O problema estudado nesta dissertação pertence à área de otimização combinatória. É um problema, do ponto de complexidade computacional, da classe NP-Difícil,
segundo Festa (2007). Por essa razão, são propostas aqui heurísticas para a solução do problema. As heurísticas são algoritmos que buscam encontrar uma solução
próxima da ótima, em um tempo computacional razoável.
De acordo com Maes et al. (1991), as heurísticas podem ser classificadas em
dois grupos: o primeiro baseado na teoria de otimização e programação matemática
e o segundo, na intuição de especialistas sobre o problema estudado. O primeiro
grupo tem a vantagem de ser fácil de se obter limitantes, os quais são totalmente
confiáveis. Já o segundo grupo tem como vantagens as observações práticas. Um
grupo particular das heurísticas é composto pelas metaheurísticas. Elas podem ser
definidas como uma estrutura de algoritmo de alto nível que podem ser especializadas
em resolver problemas de otimização. Além disso, é uma estratégia que guia outras
heurísticas na busca por soluções factíveis.
A seguir, são apresentadas heurísticas e metaheurísticas utilizadas para a resolução dos problemas relacionados com seqüências de caracteres. Nas Seções 4.6 e 4.10,
serão apresentados os procedimentos heurísticos implementados nesta dissertação
para a resolução do PCCP.
4.2
Algoritmo MultiStart
Os métodos que fornecem as origens do que se conhece como procedimento MultiStart consistem principalmente em aplicações repetidas de métodos construtivos.
A melhor solução produzida por estas aplicações repetidas normalmente são seleci28
4.2
Metodologia de Pesquisa
29
onadas para execução. As primeiras propostas podem ser encontradas nos domínios
das heurísticas de agendamento (Ciffler (1963) e Crowston et al. (1963)), no problema do caixeiro viajante (Held e Karp (1971) e Lawler et al. (1985)) e no problemas
da mochila (Senju e Toyoda (1968) e Kochenberger et al. (1974)).
A metaheurística MultiStart consiste em duas fases. Na primeira, as soluções
iniciais são geradas aleatoriamente na região viável do problema. Na segunda fase,
estas soluções são refinadas e melhoradas, gerando um ótimo global para o problema.
A solução inicial é gerada de forma aleatória com distribuição uniforme. O procedimento termina quando um critério de parada é atingido, como, por exemplo, número
de iterações, tempo de processamento, iterações sem melhora, dentre outros.
Um dos primeiros trabalhos dedicados ao método MultiStart, foi proposto por
Los e Lardinois (1982). O autor utilizou, como critério de parada, uma função de
distribuição assintótica do mínimo global.
No trabalho de Martí (2003), o autor descreve as principais aplicações e sucessos
do método MultiStart, tanto para problemas combinatórios quanto para otimização
global. Também se encontra um método para o problema Bandwidth Reduction
Problem (BRP).
Gomes et al. (2008) utilizou em seu trabalho o algoritmo MultiStart para resolver o Problema da Cadeia de Caracteres mais Próxima, fazendo modificações na
estrutura geral do método. Foi apresentada uma heurística paralela, combinando
um algoritmo de aproximação e estratégias de busca local, de forma que o primeiro
algoritmo gera soluções viáveis, garantidas a partir de um valor ideal e, então, o
segundo algoritmo faz uma busca local para melhorar as soluções.
O pseudocódigo do algoritmo MultiStart está apresentado na Figura 4.1.
Procedimento MultiStart((f (.), N(.), CriterioP arada, s))
1- f ∗ ← ∞; Valor associado a s∗
2- enquanto (Critério de parada não atendido) faça
3s ← ConstruaSoluo(); Gere uma solução s do espaço de soluções
4s ← BuscaLocal(s); Aplique um procedimento de melhora em s
5Se (f (s) < f (s∗ )) então
6s∗ ← s;
7f ∗ ← f (s);
8fim-Se;
9- fim-enquanto;
10- s ← s∗ ;
11- Retorne s;
Fim MultiStart;
Figura 4.1: Pseudocódigo MultiStart.
O procedimento MultiStart funciona da seguinte maneira: na linha 3, uma solução inicial s é construída. Essa fase é normalmente realizada por algum algoritmo
construtivo. A linha 4 é dedicada a melhorar esta solução s. Isto pode ser feito
aplicando um método simples de busca local, obtendo uma solução melhor s∗ .
4.3
Metodologia de Pesquisa
30
Segundo Martí et al. (2013), os procedimentos da metaheurística MultiStart foram originalmente concebidos como uma maneira de explorar um local ou procedimento de busca de bairro, aplicando-o simplesmente a múltiplas soluções iniciais
aleatórias. Os métodos modernos do Multistart geralmente incorporam uma forma
poderosa de diversificação na geração de soluções para ajudar a superar a otimalidade local. Sem esta diversificação, estes métodos podem tornar-se confinados a
uma pequena região do espaço de solução, tornando-se difícil, se não impossível,
encontrar um ótimo global.
4.3
Greedy Randomized Adaptive Search Procedure
A metaheurística Greedy Randomized Adaptive Search Procedure (GRASP) foi
introduzida por Feo e Resende (1995). É composta por duas fases, uma de construção e outra de busca local, desenvolvidas sequencialmente a cada execução. Na
fase construtiva, consideram-se, inicialmente, elementos previamente ordenados. Os
melhores candidatos são inseridos em uma lista, denominada Lista de Candidatos
Restrita (LCR), conforme uma função adaptativa gulosa que avalia o benefício referente a cada elemento. Os integrantes da lista são selecionados aleatoriamente para
compor a solução inicial.
A cada iteração, a LCR é atualizada, até que todos os elementos sejam alocados
na solução. A melhor solução encontrada, ao longo de todas as iterações GRASP
realizadas, é retornada como resultado ótimo local, a fim de minimizar o problema.
O pseudocódigo de um procedimento GRASP está ilustrado no Algoritmo 1.
Na fase de construção do algoritmo GRASP, uma solução viável é gerada de
forma incremental, inserindo, na solução parcial, um novo elemento a cada passo.
Para seleção destes elementos a serem incorporados na solução, todos os candidatos
são avaliados de acordo com uma função gulosa, que estima o benefício da seleção
de cada um dos elementos, e seleciona-se um subconjunto formado pelos melhores
candidatos para serem inseridos na LCR. O elemento a ser inserido na solução parcial
é selecionado de forma aleatória entre os pertencentes a LCR. Esta escolha aleatória
permite gerar diferentes soluções a cada execução do algoritmo GRASP. A Figura4.2
mostra o pseudocódigo da fase de construção GRASP.
Com o objetivo de solucionar o FFMSP (veja Seção 3.4), Festa (2007) faz o uso
da metaheurística GRASP. Em sua fase de construção, a LCR é composta pelos dois
melhores caracteres, determinados para cada posição do conjunto de seqüências do
banco de dados. A escolha é então feita de forma aleatória para compor a solução
inicial.
No trabalho de Mousavi e Esfahani (2012), é utilizado uma função heurística
(cos(·)) de avaliação, inspirada na teoria das probabilidades, a fim de avaliar e
comparar soluções candidatas na fase de construção GRASP. Esta função, proposta
pelo autor, avalia o benefício de duas ou mais soluções candidatas diferentes que
possuam a mesma distância de Hamming, diminuindo, assim, o custo computacional
do algoritmo.
A busca local é utilizada com frequência para resolver problemas de otimização
combinatória e serve principalmente como estratégia de apoio para outros algoritmos
4.4
Metodologia de Pesquisa
31
Fase-Construtiva GRASP
1- Solucao ← ∅;
2- Avalie o custo incremental dos elementos candidatos;
3- Enquanto Solucao não está completa faça
4Construa a lista de candidatos restrita (LCR);
5Selecione aleatoriamente
[ um elemento s de LCR;
6Solucao ← Solucao
{s};
7Recalcule os custos incrementais;
8- Fim Enquanto
9- Retorne Solucao;
Figura 4.2: Pseudocódigo da Fase-Construtiva GRASP.
como o GRASP e Busca Tabu. Isto se deve ao seu conceito de estratégia iterativa de
melhoria, que consiste em, dado uma solução inicial s, analisar soluções próximas de
s, denominadas vizinhanças de s, dadas por N(s), tendo, como objetivo, encontrar
soluções de melhor valor. Se uma solução melhor for encontrada, então a busca segue
pela vizinhança dessa solução. A busca continua até que não haja uma solução
melhorada, e a solução presente é definida como ótimo local. Outro critério de
parada que pode ser utilizado para a busca local é um número limitado de iterações.
Na Figura 4.3, é ilustrado o pseudocódigo básico da busca de um mínimo local,
avaliado por uma função f (s), em que, a análise da vizinhança será em busca de um
menor valor em relação à solução inicial s. Portanto, assim que não for mais encontrado na vizinhança de s um valor menor, então a solução presente será chamada
de mínimo local.
Busca Local (s)
1- Enquanto s não é um mínimo local faça
2Encontre s′ ǫN(s) tal que f (s′ ) < f (s) e f (s′ ) < f (s′′ ), ∀s′′ ǫN(s);
3s ← s′ ;
4- Fim Enquanto
Figura 4.3: Pseudocódigo da Busca Local GRASP.
Nos problemas de otimização, a busca local é também conhecida como heurística
de refinamento. Em alguns casos, para esta fase do GRASP, são utilizados algoritmos
de melhoria iterada como por exemplo, Best Improvement ou First Improvement.
Para a busca local do GRASP, Mousavi e Esfahani (2012) utiliza o algoritmo
first-move, considerando que seu uso representa melhorias para a solução do seu
problema ao invés do método best-move.
4.4
Metodologia de Pesquisa
32
Algoritmo 1: Pseudocódigo do procedimento GRASP
Procedimento GRASP(f(.),g(.),N(.),GRASPmax,s)
início
f∗ ← ∞
para (Inter = 1,2,...,GRASPmax) faça
Construcao(g(.), α, s)
BuscaLocal(f (.), N(.), s)
se (f (s) < f ∗ ) então
s∗ ← s
f ∗ ← f (s)
fim
fim
s ← s∗
Retorne s
fim
4.4
Iterated Local Search – ILS
A metaheurística Iterated Local Search (ILS), proposta por Lourenço et al. (2002),
consiste em aplicar um procedimento de busca local a uma solução inicial s0 e escapar de ótimos locais por meio de perturbações aplicadas à melhor solução corrente.
O êxito deste método está diretamente associado à definição do procedimento de
busca local, do procedimento de perturbação aplicado à solução atual e do critério
de aceitação das soluções.
O procedimento ILS consiste em um processo iterativo, no qual uma solução é
perturbada, gerando novas soluções de partida para um método de busca local. A
perturbação tem uma influência muito grande. Uma perturbação muito fraca, faz
com que a busca local caia freqüentemente em um ótimo local já visitado; deste
modo, a diversificação torna-se muito limitada. No entanto, com uma perturbação
muito alta, o ILS comporta-se como método Random Restart e há pouca possibilidade de se encontrar boas soluções. O ideal de uma perturbação é ser aleatória ou
semi-determinística, de modo a evitar ciclagem.
O algoritmo ILS inicia-se gerando uma solução inicial (s0 ) qualquer para o problema. Em seguida, é aplicada uma heurística de busca local, que varre o espaço de
busca para obter uma solução de ótimo local s. A partir dessa solução se inicia um
processo iterativo até que algum critério de parada seja satisfeito. Para cada iteração, é realizado um procedimento de perturbação aleatória da solução s, gerando
um novo ponto de partida (s′ ) para a busca local. Então, a heurística de busca local
é aplicada sobre s′ , encontrando uma solução de ótimo local s′′ dessa região. Um
critério de aceitação é aplicado para saber qual dessas soluções a busca continuará.
A definição da solução sobre qual será aplicada a próxima perturbação é feita
pelo critério de aceitação. O critério de aceitação adotado é o de melhorar o valor da
solução corrente s, isto é, uma solução s′′ é aceita para ser a nova solução s corrente
se f (s′′ ) < f (s). Uma forte intensificação é conseguida se somente as melhores
soluções são aceitas. Mas, por outro lado, sempre aceitar a nova solução é uma
forma de diversificar o espaço de busca.
4.5
Metodologia de Pesquisa
33
Segundo Lourenço et al. (2002), na prática, grande parte da complexidade do
ILS está escondida na dependência do histórico. Se acontecer de não ser nenhuma
tal dependência, a busca não tem memória, então a perturbação e o critério de
aceitação não dependem de nenhuma das soluções visitadas anteriormente, durante
a busca local, e aceitar ou não s′′ se torna uma regra fixa. A maioria dos trabalhos
que utilizam o ILS tem sido desta maneira, embora Stützle (1998) mostrou que
incorporar a memória melhora o desempenho do ILS.
Dentre as suas características, vale citar a facilidade de implementação e a flexibilidade com que se comporta em atividades híbridas com outras heurísticas e
metaheurísticas. O pseudocódigo geral da metaheurística ILS é mostrado na Figura 4.4.
Procedimento ILS
1- s0 = SolucaoInicial();
2- s = BuscaLocal(s0 );
3- inter = 0;
4- enquanto (inter < intermax ) faça
5inter = inter + 1;
′
6s = P erturbacao(s, historico);
′′
′
7s = BuscaLocal(s );
′
′′
8s = CriterioAceitacao(s, s , s );
9- fim-enquanto;
10- retorne s;
Fim.
Figura 4.4: Pseudocódigo do Iterated Local Search (ILS).
Com base na heurística ILS, Andronescu e Rastegari (2003) criaram um algoritmo para solucionar problemas relacionados a subseqüências de caracteres. Essas
subseqüências são chamadas pelos autores de motifs, que, em particular, são trechos
de bioseqüências (seqüências de DNA, RNA ou proteínas), que possuem regiões altamente conservadas, isto é, pouco afetadas por mutações, as quais desempenham
funções biológicas específicas. Estes trechos são relativamente curtos, para o DNA,
cerca de 5 a 25 nucleotídeos de comprimento. Para fins de comparação, os autores
implementam também outro tipo de algoritmo com base na metaheurística GRASP.
4.5
Iterated Greedy Search
A heurística de Busca Gulosa Iterativa (Iterated Greedy Search - IGS) parte de
uma solução inicial para um problema de otimização combinatória, para, em seguida,
fazer buscas locais e melhorar diversas vezes a solução inicial encontrada através de
um determinado número de iterações, segundo Gagnaire e Doumith (2007).
Na primeira fase, é feita a desconstrução da solução, através da aplicação de uma
perturbação gulosa em k elementos da solução que serão removidos. Na segunda
fase, é feita a reconstrução da solução, de modo que cada um dos k elementos
4.6
Metodologia de Pesquisa
34
anteriormente removidos são re-inseridos, gerando uma nova ordem de permutação.
Então, é aplicada uma busca local na solução resultante da segunda fase, gerando
uma nova solução candidata. Um critério de aceitação aplicado entre a solução
candidata e a solução inicial decide qual será a nova solução corrente.
A heurística IGS está fortemente relacionada a outros métodos estocásticos de
busca local, em particular à metaheurística ILS (Lourenço et al. (2002)).
No trabalho de Montemanni e Smith (2008), os autores utilizaram o algoritmo
Iterated Greedy Search para encontrar uma seqüência de caracteres viáveis, fazendo
modificações em sua estrutura, respeitando um número fixo de substituições dos
caracteres, denominado (IGSChg) e o tempo máximo de execução do algoritmo
dado por (TimeIGS).
4.6
Heurística IGS-PCCP
motivação para a utilização da metaheurística de Busca Gulosa Iterada baseiase no fato de que, recentemente, foi utilizada com sucesso nos trabalhos de FanjulPeyroa e Ruiz (2010), Framinan e Leisten (2008), Ruiz e Stützle (2007), Garcia et al.
(1998), Montemanni e Smith (2008), citado anteriormente, e em outros problemas
de otimização combinatória.
O funcionamento do IGS-PCCP pode ser ilustrado pela Figura 4.5. A partir de
um ótimo local s∗ , é feita uma perturbação que guia a uma solução intermediária
s′ . Após a aplicação de um método de busca local a s′ é produzido um novo ótimo
′
′
local s∗ . Considerando como critério de aceitação o fato de f (s∗ ) ser melhor que
′
f (s∗ ), então a busca prossegue a partir de s∗ .
Figura 4.5: Funcionamento dos ótimos locais da heurística IGS-PCCP.
O IGS-PCCP gera aleatoriamente uma solução inicial s0 , escolhendo os caracteres a partir de um conjunto Ω com 4, 20 ou 30 caracteres diferentes. Posteriormente,
na solução inicial, é feita uma busca local, utilizando o refinamento iterativo, resultando na solução intermediária s. Em seguida, é aplicada uma perturbação gulosa
em k caracteres de s, removendo uma quantidade de caracteres selecionados aleatoriamente e atribuindo novos caracteres, também selecionados aleatoriamente, em
4.6
Metodologia de Pesquisa
35
suas respectivas posições, gerando, assim, a solução intermediária s′ . Em seguida,
IGS-PCCP calcula a distância de Hamming da nova cadeia de caracteres em relação
às demais cadeias e esta solução é comparada à solução atual. A cada iteração do
IGS-PCCP, a solução com a menor distância máxima de Hamming, ou seja, menor max dH em relação a todas as seqüências do conjunto, é armazenada em s∗ ,
sempre sendo comparada com a solução s′ da iteração atual. A Figura 4.6 exibe o
pseudocódigo da metaheurística IGS-PCCP.
início IGS-PCCP (s′ , Tmax )
1- s, s∗ ← s′ ;
2- Enquanto T empo < Tmax faça
3s′ ← P erturbacao(k, s);
4Se s′ é melhor que s∗ então s∗ ← s′ ;
5Se s′ é melhor que s então s ← s′ ;
6- fim-Enquanto;
7- retorne s∗ ;
fim
Figura 4.6: Pseudocódigo da heurística IGS-PCCP.
Começando a partir da solução inicial s′ gerada aleatoriamente, as soluções ótimas locais s e s∗ são criadas na linha 1. Em seguida, o laço das linhas 2-6 é realizado
até o critério de parada ser satisfeito. Para este caso, o tempo foi limitado em 5
minutos (ou 300 segundos). Novos ótimos locais são obtidos através da aplicação
de uma perturbação gulosa de tamanho k na linha 3. Em seguida, se a solução
resultante é melhor que a solução corrente s∗ , ou seja, se max dH da nova solução for
menor que max dH de s∗ , a solução corrente é atualizada na linha 4. Na seqüência,
a solução s do ótimo local corrente é substituído por uma solução s′ se e somente se
max dH for maior. Então, a solução s′ é aceita se o seu custo for menor que o custo
de s. A melhor solução encontrada por esta heurística é retornada na linha 7.
A seguir um exemplo do funcionamento do IGS-PCCP.
Exemplo 4.1 Dado um conjunto de seqüências S = {s1 , s2 , s3 }, formadas pelo alfabeto Ω = {A, C, T, G}, com s1 = (CAAGT G), s2 = (ACCT GG), s3 = (GCAAT G).
Encontrar uma string centro t, que minimize a maior distância de Hamming (max dH )
em relação às cadeias de caracteres do conjunto S.
• Seja t = (AAT CGT ) a solução inicial para o problema, construída aleatoriamente a partir do alfabeto Ω.
• Em seguida, é verificado d dH entre t e s1 , s2 e s3 . Tem-se, então, que
dH (s1 , t) = 5, dH (s2 , t) = 4, dH (s3 , t) = 6.
Após a comparação da string t, obtida na solução inicial, com as demais cadeias
de caracteres do conjunto S, o objetivo é diminuir max dH encontrado entre t e s3 .
Este procedimento será feito pela perturbação de k = 2 caracteres na solução t, e a
reposição será feita de forma aleatória dentre os elementos de Ω, com o objetivo de
diminuir max dH computado.
4.7
Metodologia de Pesquisa
36
• Fazendo de forma aleatória a perturbação de 2 caracteres em t, obtém-se uma
nova solução t′ = (ACT CGG).
• Verificando as distâncias em relação a t′ : dH (s1 , t′ ) = 5, dH (s2 , t′ ) = 2 e
dH (s3 , t′ ) = 4. Observa-se, então, que a dH entre t e s1 permaneceu a mesma.
No entanto, em relação às seqüências s2 e s3 , houve uma redução em duas
unidades. O principal objetivo era diminuir max dH , o que foi alcançado.
Então, a solução inicial recebe a solução t′ , que é considerada a melhor solução
até o momento.
• Fazendo uma nova perturbação de dois elementos na seqüência t′ , obtém-se
t′′ = (ACACCG). Esta solução é considerada se for uma melhor solução em
relação a t′ .
• Então, são verificadas as seguintes distâncias: dH (s1 , t′′ ) = 4, dH (s2 , t′′ ) = 3 e
dH (s3 , t′′ ) = 3. Como o max dH (dado pela distância entre s1 e t′′ ) diminuiu
em mais uma unidade, então a solução t′′ é aceita. Este processo é repetido
até que o tempo de limite de processamento seja atingido.
Os valores para a perturbação k serão descritos na Seção 5, pois variam de acordo
com a dimensão e composição dos elementos das cadeias de caracteres.
4.7
Algoritmos Genéticos
Algoritmos Genéticos (Genetic Algorithms – AG) são algoritmos inspirados nos
mecanismos da evolução natural e recombinação genética. São baseados no princípio
darwiniano de seleção natural e sobrevivência do mais apto, ou seja, da evolução das
espécies e na genética. Conforme Lacerda e Carvalho (1999), os algoritmos genéticos foram introduzidos por Holland (1975) e por Goldberg e Holland (1988). São
classificados como algoritmos evolucionários, definidos como algoritmos probabilísticos e que fornecem um mecanismo de busca paralela e adaptativa, inspirados nos
conceitos de evolução populacional.
Os princípios da natureza nos quais os algoritmos genéticos se inspiram são
simples. O princípio de seleção privilegia os indivíduos mais aptos com maior longevidade e, portanto, com maior probabilidade de reprodução. Indivíduos com mais
descendentes têm mais chance de perpetuarem seus códigos genéticos nas próximas
gerações. Tais códigos genéticos constituem a identidade de cada indivíduo e estão
representados nos cromossomos.
Estes princípios foram a base para a construção de algoritmos computacionais
que buscam uma melhor solução para um determinado problema, através da evolução de populações de soluções codificadas através de cromossomos artificiais. Em
algoritmos genéticos, um cromossomo é uma estrutura de dados que representa uma
das possíveis soluções do espaço de busca do problema. Cromossomos são então submetidos a um processo evolucionário que envolve avaliação, seleção, recombinação
ou cruzamento (crossover ) e mutação. Após vários ciclos de evolução, a população
deverá conter indivíduos mais aptos.
O algoritmo genético é uma subdivisão do algoritmo evolucionário, classe de algoritmos em que também se encontra a programação evolucionária e a estratégia
4.8
Metodologia de Pesquisa
37
evolucionária. Todos partilham de uma base conceitual comum, que consiste na
simulação da evolução de estruturas individuais, via processo de seleção e os operadores de busca, referidos como operadores genéticos, como mutação e crossover.
Todo o processo depende do grau de adaptação, ou seja, do fitness (aptidão) do
indivíduo frente ao ambiente.
Algumas definições para os algoritmos genéticos são:
• Genoma e Cromossomo: estrutura de dados que codificam uma solução para
o problema, definidos como um ponto no espaço de busca. Um cromossomo
pode ser representado por um vetor, ou por uma cadeia de bits, por exemplo.
• Gene: elemento que compõe o cromossomo. Se este for um vetor ou uma
cadeia de bits, um gene é um componente do vetor ou da cadeia de bits.
• Indivíduo: formado pelo cromossomo e sua aptidão.
• Alelo: os valores que um gene pode assumir. Um alelo terá valor 1 ou 0, se o
cromossomo for uma cadeia de bits.
Como dito anteriormente, nos algoritmos genéticos o espaço de busca é explorado
pelos operadores crossover e mutação. A população é gerada e diversificada pelos
operadores, os quais assumem variações em intervalos pré-estabelecidos. A taxa
de crossover assume valores de 60% a 90% e a taxa de mutação entre 0,1% a 5%.
Pelo fato da mutação destruir informação nos cromossomos, esse percentual assume
pequenos valores, de forma a evitar constantes variações. Estratégia importante
encontrada nos algoritmos genéticos é o Elitismo, que consiste na transferência dos
melhores indivíduos de uma geração para outra, sem que estes sofram modificações.
De acordo com Whitley (1993), o AG é freqüentemente descrito como um método
de busca global, não utilizando gradiente de informação e podendo ser combinado
com outros métodos para refinamento de buscas, quando há aproximação de um
máximo ou mínimo local.
Atualmente, o AG é muito empregado na resolução de problemas de Bioinformática. Como exemplo, a descoberta da estrutura de RNA (Fogel et al. (2002)),
para a predição de non-coding RNA (ncRNA) (Saetrom et al. (2005)), e em diversos problemas ligados a seqüências de DNA, RNA e proteínas, como nos trabalhos
descritos a seguir.
Para elaborar uma seqüência artificial que incorpore a variação da seqüência
encontrada em uma população viral, o algoritmo genético foi utilizado por Mauch H
(2003), com o objetivo de determinar uma homologia dessas seqüências artificiais
com uma solução ideal (ou entre 90% - 95%), para todas as seqüências virais em
uma população, utilizando seqüências de RNA interference e RNA mensageiro.
Uma aplicação mais recente de algoritmo genético, baseado em uma técnica
chamada data-based coding, foi proposta por Julstrom (2009), para solucionar o
Closest String Problem. O autor ainda constrói dois outros algoritmos, também
baseados no AG, para comparar a solução ótima com o data-based coding GA.
Já no trabalho de de Souza (2012), o autor fez a construção de dois algoritmos
híbridos, utilizando o GRASP juntamente com o Algoritmo Genético. A heurística
GRASP é responsável pela construção inicial; já o AG tem a função de fazer uma
varredura do espaço de busca. Neste trabalho, o objetivo é solucionar o PCCP, tema
também da presente dissertação.
4.8
4.8
Metodologia de Pesquisa
38
Random-Key Genetic Algorithm
Random-Key Genetic Algorithm (RKGA) foi desenvolvido por Bean (1994) para
aplicação em problemas de sequenciamento. Neste algoritmo, o cromossomo é gerado
com os valores de seus genes dentro do intervalo real [0, 1] e a população evolui a cada
geração, obedecendo às regras de elitismo, de cruzamento e de mutação específicas
do algoritmo.
De acordo com Gonçalves e Resende (2011), no RKGA o processo de evolução
da população ao longo de sucessivas gerações emprega uma estratégia de elitismo,
que consiste em levar, para a próxima geração, todos os elementos do conjunto
elite. Por outro lado, para garantir diversidade e, assim, escapar de mínimos locais,
alguns novos indivíduos são gerados por meio de mutação, da mesma forma que
os indivíduos da população inicial. A próxima geração é completada por meio do
operador de cruzamento.
O RKGA evolui de uma população de vetores de chaves aleatórias sobre um número de iterações, chamado de gerações. A população inicial é composta de vetores
p de chaves aleatórias. Cada componente do vetor solução é gerado independentemente de forma aleatória no intervalo real [0, 1]. Depois que a fitness de cada
indivíduo é calculada pelo decodificador na geração k, a população é particionada
em dois grupos de indivíduos (ver Figura 4.7): um pequeno grupo pe de indivíduos
elite, ou seja, aqueles com os melhores valores de aptidão, e o restante do conjunto
p − pe , de indivíduos não-elite.
Figura 4.7: A população de soluções p é particionada em um conjunto menor pe de
soluções elite, mais aptos, e um conjunto maior p − pe de soluções não-elite, menos
aptos (Resende (2012)).
Segundo Resende (2012), para evoluir a população, uma nova geração de indivíduos deve ser produzida. A partir da geração k, o processo de evolução copia as
soluções elite pe para a geração k + 1 e adiciona pm mutantes à população da geração k + 1 (Figura 4.8). Um mutante é simplesmente um vetor de chaves aleatórias
geradas na mesma forma que um elemento da população inicial é gerado. Em cada
geração, um pequeno número (pm ) de mutantes é introduzido na população (Figura 4.8). Com os indivíduos elite pe e os mutantes pm contabilizados na população
4.8
Metodologia de Pesquisa
39
k + 1, os indivíduos p − pe − pm adicionais precisam ser produzidos para completar
os indivíduos p que compõem a nova população. Isso é feito pela produção da prole
p − pe − pm através do processo de acasalamento ou crossover. Veja a Figura 4.9.
Figura 4.8: Todas soluções elite pe da população k são copiadas sem alteração para
a população k + 1 e as soluções mutantes pm são geradas na população k + 1 como
vetores de chaves aleatórias (Resende (2012)).
Figura 4.9: Para completar a população k + 1, a prole p − pe − pm é criada pela
combinação de um pai escolhido aleatoriamente do conjunto elite da população k,
com um pai escolhido aleatoriamente do conjunto não-elite também da população
k. Os pais podem ser escolhidos para o crossover mais de uma vez por geração
(Resende (2012)).
4.9
Metodologia de Pesquisa
40
No trabalho de Bean (1994), o autor seleciona dois pais ao acaso de toda a
população para implementar o crossover em um RKGA e também permite um pai
ser selecionado mais de uma vez em uma determinada geração.
O cruzamento é feito com a combinação de um elemento do conjunto elite com
um do conjunto não-elite, gerando um único filho em cada cruzamento. O número
de indivíduos mutantes é gerado aleatoriamente e colocado na população da nova
partição, também chamada de BOT . O restante da população da próxima geração
é completada pelo crossover.
4.9
Biased Random-Key Genetic Algorithm
A formulação de Algoritmo Genético Baseados em Chaves Aleatórias Tendenciosas (Biased Random-Key Genetic Algorithm – BRKGA) foi introduzida por Gonçalves e Almeida (2002) como uma variação dos Algoritmos Genéticos Baseados em
Chaves Aleatórias (Random-Key Genetic Algorithm – RKGA).
A diferença entre o BRKGA e o RKGA está na definição do cromossomo do indivíduo gerado pelo cruzamento. Enquanto no RKGA as probabilidades de influência
dos pais são iguais, no BRKGA a probabilidade de influência do indivíduo elite é
maior que a probabilidade de influência do indivíduo não-elite. Em alguns casos, o
segundo pai é selecionado de toda a população. É permitida a repetição na escolha
de um pai e, portanto, um indivíduo pode produzir mais de um filho, desde que seja
exigido pe < p − pe , ou seja, a probabilidade que um determinado indivíduo elite
ser selecionado para acasalamento (1/pe) seja maior do que a de um determinado
indivíduo não-elite (1/(p − pe)) e, portanto, determinado indivíduo elite tem uma
probabilidade mais elevada de passar suas características para as gerações futuras
do que um determinado indivíduo não elite. Também contribui para este efeito
o operador de cruzamento Parametrized Uniform Crossover, proposto por Spears
e deJong (1991), que é o mecanismo usado para implementar o acasalamento no
BRKGA, além do fato que um pai sempre é selecionado a partir do conjunto elite.
Seja pe > 0, 5 o parâmetro escolhido. Este parâmetro é a probabilidade de uma
prole herdar o alelo de seu pai do conjunto elite. Seja n o número de genes no
cromossomo de um indivíduo, para i = 1, ..., n. O i-ésimo alelo c(i) da prole c
assume o valor do i-ésimo alelo e(i) do pai elite (e) com probabilidade pe , e o valor
do i-ésimo alelo ē(i) do pai não-elite (ē) com probabilidade 1 − pe (Gonçalves e
Resende (2011)). Desta forma, é mais provável que a prole herde características do
pai elite do que aquelas do pai não-elite (sobrevivência do mais apto). Desde que
seja assumido que qualquer vetor de chaves aleatórias pode ser decodificada em uma
solução, então a prole resultante do acasalamento é sempre válida, ou seja, pode ser
decodificada em uma solução de problemas de otimização combinatória.
Exemplo 4.2 A Figura 4.10 ilustra o processo de cruzamento de dois vetores de
chaves aleatórias com quatro genes cada. Cada cromossomo é composto por um vetor
de 4 genes (ou caracteres), que são gerados de forma aleatória, utilizando o alfabeto
Ω = {A, C, T, G} para compor estes vetores. Os alelos dos cromossomos também
são gerados de forma aleatória no intervalo [0, 1]. O cromossomo 1 representa o
indivíduo elite e o cromossomo 2 refere-se ao indivíduo não-elite.
4.10
Metodologia de Pesquisa
41
Neste exemplo, o valor de pe = 0, 7, ou seja, a descendência herda o alelo do pai
elite com probabilidade de 70% e do outro progenitor com probabilidade de 30%.
Figura 4.10: Operador de cruzamento no BRKGA (Gonçalves e Resende (2011)).
Um gerador aleatório no intervalo real [0, 1] simula o sorteio de uma moeda
tendenciosa. Se o resultado for menor ou igual a 0, 7 então o filho herda o alelo do
pai elite; caso contrário, ele herda o alelo do outro pai (não-elite). Neste exemplo,
a prole herda o alelo do pai elite em seu primeiro, terceiro e quarto genes, e do pai
não-elite o segundo gene, assemelhando-se ao pai elite mais do que em relação ao
outro pai.
Quando a próxima população é completada, ou seja, quando se tem p indivíduos,
os valores de aptidão são computados para todos os vetores de chaves aleatórias
recém-criados e a população é particionada em indivíduos elite (T OP ) e não-elite
(REST ) para iniciar uma nova geração. Veja outro esquema na Figura 4.11, em
que a parcela BOT , da nova população gerada, representa os indivíduos mutantes
e a parcela MID representa os indivíduos descendentes do cruzamento.
Em todas as gerações, a população é dividida em dois conjuntos, denominados
T OP e REST . Nos testes computacionais da Seção 5, foram utilizadas populações
com 100, 500 e 1000 indivíduos. O conjunto T OP da população armazena os indivíduos com as melhores soluções. Estes indivíduos são copiados, sem alterações, para
as próximas gerações. O restante da população da nova geração é encontrado pela
aplicação de operadores de cruzamento e mutação.
Na operação de mutação do algoritmo BRKGA, a cada geração um número
fixo de cromossomos mutantes é inserido na população. Para escapar de mínimos
locais, uma parte dos cromossomos menos aptos é substituída por cromossomos
gerados aleatoriamente, de forma semelhante à geração da população inicial. Os
tamanhos das parcelas T OP , REST e BOT são informados através de parâmetros
do algoritmo. A Figura 4.11 mostra a evolução da população do algoritmo genético
entre duas gerações.
4.10
Metodologia de Pesquisa
42
Figura 4.11: Transição entre gerações sucessivas (Noronha et al., 2011).
4.10
Heurística BRKGA-PCCP
O uso de Algoritmo Genéticos Baseados em Chaves Aleatórias Tendenciosas
(BRKGA) na presente dissertação foi motivado pelo sucesso da utilização desta metaheurística para a resolução de problemas em Buriol et al. (2005), Buriol et al.
(2007), Gonçalves e Resende (2004), Gonçalves e Resende (2011), Dias et al. (2011),
Noronha et al. (2011), Reis et al. (2011), assim como em outros problemas de otimização combinatória Arulselvan et al. (2007), Gonçalves et al. (2005), Malve e Uzsoy
(2007), Samanlioglu et al. (2008), Lawrence e Mark (2006).
Os cromossomos no BRKGA-PCCP são compostos por vetores de caracteres.
Cada caractere recebe um número real aleatório entre 0 e 1. Posteriormente, a
população é ordenada em ordem crescente, de acordo com o valor aleatório atribuído à cada caractere. A distância de Hamming entre as cadeias de caracteres
e a seqüência resultante da ordenação dos caracteres é calculada. A distância de
Hamming calculada pelo BRKGA-PCCP é atribuída como valor de de adaptação
do cromossomo.
Em todas as gerações, a população é dividida em dois conjuntos, denominados
T OP e REST . O cruzamento é realizado entre um cromossomo da parcela T OP
com um cromossomo da parcela REST . Cada filho recebe suas chaves, de modo
que ou a chave é herdada da porção mais apta (T OP ) da população, com uma probabilidade de 0, 7, ou a chave é herdada do cromossomo pertencente à população
menos apta (REST ) da população, com probabilidade de 0, 25. Assim, o tamanho
total da população inicial é T OP + REST e a quantidade de cromossomos criados
a cada geração através de cruzamento é REST + BOT cromossomos filhos. Cromossomos mutantes são colocados na parcela BOT (com probabilidade de 0, 05) da
nova população gerada.
O pseudocódigo do algoritmo genético utilizado é descrito na Figura 4.12. Na
linha 2 deste algoritmo, os vetores de chaves são iniciados com valores aleatórios.
Na linha 3, é calculada a distância de Hamming para cada vetor. O laço entre
as linhas 5 e 15 é executado até que o instante de tempo Tmax ou outro critério
de parada seja alcançado. Na linha 6, a população é ordenada de acordo com a
4.10
Metodologia de Pesquisa
43
BRKGA-PCCP (G, R, prec , Tmax )
1- Para cada elemento da cadeia de caracteres faça
2Gerar vetor com chaves aleatórias;
3Avaliar vetor de acordo com a Distância de Hamming;
4- fim-para
5- Enquanto T empo < Tmax faça
6Ordene a população pela Distância de Hamming;
7Divide em T OP , REST e BOT ;
8Copiar para a próxima geração a parcela T OP da população;
9Para n ← 1 até |REST | faça
10Selecione aleatoriamente um elemento da parcela T OP ;
11Selecione aleatoriamente um elemento da parcela REST ∪ BOT ;
12Para cada chave do novo cromossomo faça
13p3 ← Crossover(p1, p2 , prec );
14fim-Para
15fim-Para
16Gerar aleatoriamente parcela BOT da nova população;
17Avaliar cada elemento da população;
18- fim-Enquanto
Figura 4.12: Pseudocódigo do Algoritmo Genético com Chaves Aleatórias Tendencioso para o Problema da Cadeia de Caracteres mais Próxima - BRKGA-PCCP.
distância de Hamming de cada indivíduo. Na linha 8, é realizada a reprodução da
porção T OP da população, que é integralmente copiada para a próxima geração.
Entre as linhas 11 e 13 é realizado o cruzamento, gerando os cromossomos da porção
MID da população. Na linha 16 são gerados os novos elementos da parcela BOT ,
responsáveis pela diversificação da população. Na linha 17, a nova população é
avaliada.
Capítulo 5
Experimentos Computacionais
Neste capítulo são apresentados os resultados computacionais obtidos pelas heurísticas BRKGA-PCCP e IGS-PCCP para a resolução do Problema da Cadeia de
Caracteres mais Próxima (PCCP). Estas duas heurísticas foram comparadas entre si e os melhores resultados foram comparados com os da heurística IntegerProgramming (IP) utilizada por Meneses et al. (2004). Para avaliar os dois métodos
propostos para solucionar o PCCP, foram utilizadas as instâncias do trabalho de
Meneses et al. (2004) e do trabalho de Mousavi e Esfahani (2012), as quais são
freqüentemente usadas por vários autores para fins de comparação. Na Seção 5.1
será apresentado o conjunto de instâncias utilizadas para os devidos experimentos. A Seção 5.2 apresenta os resultados das diferentes perturbações da heurística
IGS-PCCP para todas as instâncias testadas. Na Seção 5.3 serão apresentados os resultados para as diferentes populações p da heurística BRKGA-PCCP. Na Seção 5.4
é feita uma comparação entre os melhores resultados das duas heurísticas propostas
nesta dissertação. Por fim, na Seção 5.5 é feita a comparação entre as heurísticas
BRKGA-PCCP e a solução via Programação Inteira (IP).
As heurísticas BRKGA-PCCP e IGS-PCCP foram codificadas utilizando a linguagem de programação C + + e compiladas com o compilador GNU GCC versão
4.4.3. Os experimentos foram executados em um computador com processador Intel
Core I5, tendo 2.76 GHZ, com 4 GB de memória RAM.
5.1
Instâncias de Teste
Uma parte do conjunto de instâncias utilizadas nesta dissertação para os testes
computacionais foram retiradas do trabalho de Meneses et al. (2004). Neste trabalho, Meneses et al. (2004) teve o objetivo de solucionar o Closest String Problem. A
maioria das instâncias utilizadas em seu trabalho foram geradas aleatoriamente, exceto por um conjunto de 6 instâncias retiradas do trabalho de McClure et al. (1994),
que pertencem ao seguinte conjunto: Σ = 20, n = {6, 10, 12} e m = {98, 100, 141}.
As instâncias aleatórias do trabalho de Meneses et al. (2004) foram geradas por
um processo bem simples, na forma: dados os parâmetros n (número de cadeias de
caracteres do conjunto), m (dimensão de cada cadeia de caracteres) e um alfabeto
(Σ), escolhe-se aleatoriamente um caractere pertencente a Σ para cada posição na
seqüência de caracteres resultante.
44
5.2
Experimentos Computacionais
45
O algoritmo utilizado para a geração de números aleatórios é uma implementação do Linear Congruential Generator, proposto por Park e Miller (1988), com
parâmetros 16, 807 (multiplicador) e 231 − 1 (número primo).
Para os testes dessa dissertação, foram relacionados os seguintes conjuntos de instâncias. O alfabeto utilizado é composto por 4 caracteres, que são representados pela
base nitrogenada do DNA, na forma do alfabeto Ω = {A, C, T, G}; o conjunto de cadeias de caracteres n = {10, 15, 20, 25, 30} representa a quantidade de seqüências de
caracteres que cada cadeia possui; os valores para m = {300, 400, 500, 600, 700, 800}
definem a dimensão que cada seqüência pode possuir, ou seja, o número de caracteres
que cada seqüência pode conter.
A motivação para a utilização das instâncias do trabalho de Meneses et al. (2004)
é devido ao seu uso freqüente por pesquisadores da área, como Pinto et al. (2006),
Festa (2007), Chen et al. (2010) e Chimani et al. (2011), dentre outros trabalhos.
O segundo conjunto de instâncias utilizado para fins de experimentação nesta
dissertação foi retirado do trabalho de Mousavi e Esfahani (2012), com cadeias de
caracteres formadas por um alfabeto Ω = {20, 30}. São dois conjuntos formados por
20 e 30 caracteres diferentes, em que cada conjunto possui n = 10 e m = 500. Estas
instâncias foram retiradas do trabalho de Julstrom (2009), em que foram geradas
aleatoriamente.
5.2
Ajustes para a Perturbação k da Heurística IGSPCCP
Para fins experimentais, foram testadas variações no parâmetro k de perturbações da heurística IGS-PCCP, com o alfabeto Ω = {4} e k dado por valores pertencentes ao conjunto {0, 03; 0, 1; 0, 2; 0, 3; 0, 4; 0, 5; 0, 6; 0, 7}. O parâmetro k indica o
número de caracteres a serem perturbados. Veja Algoritmo 4.6.
A Tabela 5.1 relata os valores encontrados para os valores de k dados por 3%,
10% e 20%. Na Tabela 5.2 são mostrados os resultados para as perturbações de
30%, 40% e 50% e, na Tabela 5.3, são apresentados os resultados com k igual a 60%
e 70% de perturbação dos caracteres de cada instância.
Nestas três tabelas, a primeira coluna (Instâncias) indica o número de seqüências
n e a dimensão m que cada seqüência deste conjunto possui. As colunas Min, Max
e Desv representam, respectivamente, os valores de valor mínimo da distância de
Hamming, valor máximo da distância de Hamming e desvio padrão das distâncias
de Hamming encontrados pelas 5 execuções de cada conjunto de cadeias n × m. Os
valores para o desvio padrão, de todos os testes, foram considerados até a segunda
casa decimal.
Para o conjunto de cadeias de caracteres em que Ω = {20, 30}, sempre com
n = 10 e m = 500, foram testadas variações no parâmetro de perturbação k dadas
por valores pertencentes ao conjunto {0, 1; 0, 2; 0, 3; 0, 4; 0, 5; 0, 6; 0, 7}. A Tabela 5.4
mostra os resultados de variações no parâmetro k do algoritmo IGS-PCCP para as
instâncias com um alfabeto de 20 caracteres diferentes. A Tabela 5.5 apresenta os
resultados de variações no parâmetro k para as instâncias com alfabeto Ω = {30}.
O critério de escolha do melhor valor de k para a perturbação na metaheurística
IGS-PCCP foi a menor média entre os valores mínimos encontrados pelas pertur-
5.4
Experimentos Computacionais
46
bações. Para as instâncias com Ω = {4} (ver tabelas 5.1, 5.2 e 5.3), a perturbação
para k = 0, 5 obteve a menor média dos valores mínimos, tendo valor médio da
distância de Hamming dado por 374, 5. O segundo melhor valor é k = 0, 7, com
valor médio da distância de Hamming dado por 375, 2. Este valor (k = 0, 7) obteve
valores ótimos para a menor distância de Hamming em quatro das vinte instâncias,
empatando com a perturbação k = 0, 5. Como a média dos valores mínimos para
k = 0, 5 foi menor, este foi o escolhido para comparar com os obtidos pela heurística
BRKGA-PCCP.
Para o alfabeto Ω = {20, 30}, a menor média dos valores mínimos encontrados,
para ambos os casos, foi para a perturbação k = 0, 2. Com Ω = {20}, a menor
média da distância mínima de Hamming foi de 462, 2; a menor média mais próxima
foi obtida pela perturbação k = 0, 1, com média = 462, 8, com desvio padrão maior
do que a perturbação k = 0, 2.
Quando Ω = {30}, a menor média encontrada foi de 472, 8 para k = 0, 2. A
menor média mais próxima é com a perturbação k = 0, 3 e média 473. Estas duas
perturbações tiveram uma pequena diferença entre as médias e também no desvio
padrão. Então, os valores ótimos para as instâncias com Ω = {20, 30} são obtidos
pela perturbação k = 0, 2, sendo esses resultados escolhidos para se comparar com
a heurística BRKGA-PCCP.
5.3
Ajustes para a População da Heurística BRKGAPCCP
Os testes experimentais para a heurística BRKGA-PCCP foram realizados para
uma população p de indivíduos tendo valores p tais que p ∈ {100, 500, 1000}.
Quando o alfabeto Ω = {4}, a população com p = 1000 indivíduos superou as
demais instâncias com p = 100 e p = 500, exceto pela instância com n = 25 e
m = 300, em que p = 500 obteve a menor distância de Hamming, ficando uma
unidade abaixo do valor ótimo encontrado pela população com p = 1000 indivíduos,
conforme Tabela 5.6. Em conseqüência, a menor média da distância mínima de
Hamming foi dada pelo experimento com população p = 1000 e média 338, 9.
Para as cadeias de caracteres com Ω = {20} (Tabela 5.7) e Ω = {30} (Tabela 5.8),
os melhores valores foram encontrados para a população com p = 1000 indivíduos,
obtendo a média 403, 6 para Ω = {20} e média 417, 6 para Ω = {30}. Os valores
ótimos da heurística BRKGA-PCCP, para as instâncias com Ω = {4, 20, 30}, são
obtidos pelos testes que utilizam a população com p = 1000 indivíduos, e estes
posteriormente serão comparados com os resultados ótimos obtidos pela heurística
IGS-PCCP.
5.4
Comparação entre as heurísticas
Após ter verificado quais foram os parâmetros que obtiveram os melhores valores
para cada uma das heurística, será apresentada a seguir a comparação entre estes
resultados obtidos pelas heurísticas BRKGA-PCCP e IGS-PCCP.
5.4
Experimentos Computacionais
47
Tabela 5.1: Comparação entre os resultados das perturbações em k da heurística
IGS-PCCP para k = 3%, 10% e 20%.
Instâncias
IGS-PCCP k = 3%
IGS-PCCP k = 10%
IGS-PCCP k = 20%
n
m
Min
Max
Desv
Min
Max
Desv
Min
Max
Desv
10
300
208
245
12,56
209
233
11,07
206
233
12,35
10
500
357
393
12,74
355
382
15,51
354
389
13,79
10
700
506
556
19,25
504
533
16,97
497
533
17,81
15
300
208
244
13,15
209
236
13,38
209
236
15,32
15
500
350
402
20,96
361
389
14,94
353
381
14,12
15
700
492
546
19,82
493
540
21,19
488
540
22,48
20
300
213
242
11,9
210
240
15,08
204
236
15,07
20
500
352
398
17,74
349
388
18,69
351
392
20,04
20
700
493
558
24,91
496
540
22,52
496
536
21,07
25
300
204
243
15,84
209
235
14,23
203
235
15,77
25
500
341
396
20
346
389
20,24
352
391
20,3
25
600
427
487
22,87
428
467
20,82
424
464
21,5
25
700
495
554
23,11
489
540
27,58
500
542
22,39
25
800
568
632
26,67
566
617
26,62
565
616
28,07
30
300
205
244
14,76
207
236
14,38
209
237
14,09
30
400
280
322
17,42
277
315
18,4
279
311
17,28
30
500
356
398
18,01
346
390
20,93
347
392
21,74
30
600
424
476
21,97
418
465
23,59
414
464
21,73
30
700
496
538
23,71
497
537
23,08
495
543
24,73
30
800
566
634
26,44
566
616
22,83
564
616
23,94
Nos experimentos realizados para esta dissertação, foram considerados os seguintes grupos de instâncias: para o conjunto em que n possui quantidades de
cadeias de caracteres na forma n ∈ {10, 15, 20}, m possui as seguintes dimensões
m ∈ {300, 500, 700}. Quando n = 25, tem-se m ∈ {300, 500, 600, 700, 800} e, para
n = 30, tem-se min{300, 400, 500, 600, 700, 800}. Todas estas instâncias são formadas pelo alfabeto Ω = {4}.
As heurísticas BRKGA-PCCP e IGS-PCCP foram codificadas utilizando a linguagem de programação C++ e compiladas com o compilador GNU GCC versão
4.4.3. Os experimentos foram executados em um computador com processador Intel
Core I5, tendo 2.76 GHZ, com 4 GB de memória RAM.
A seguir, na Tabela 5.9, são comparados os resultados das heurísticas BRKGAPCCP e IGS-PCCP, obtidos com cinco execuções para cada instância n × m. A
primeira coluna (Instâncias) indica a composição das cadeias de caracteres, com n
sendo o número de cadeias de caracteres que cada conjunto possui e m a dimensão de
5.4
Experimentos Computacionais
48
Tabela 5.2: Comparação entre os resultados das perturbações em k da heurística
IGS-PCCP para k = 30%, 40% e 50%.
Instâncias
IGS-PCCP k = 30%
IGS-PCCP k = 40%
IGS-PCCP k = 50%
n
m
Min
Max
Desv
Min
Max
Desv
Min
Max
Desv
10
300
212
227
11,42
210
234
12,22
201
234
13,94
10
500
355
387
15,18
347
385
17,84
356
382
14,97
10
700
505
534
17,28
493
526
18,79
499
544
19,89
15
300
204
234
13,31
204
232
14,52
207
230
11,23
15
500
352
386
19,7
347
383
18,5
351
384
17,03
15
700
498
537
21,39
499
531
17,85
492
537
21,48
20
300
204
237
16,49
207
233
13,09
208
233
14,69
20
500
351
392
20,02
346
388
17,56
350
384
19,3
20
700
487
542
23,27
502
536
17,89
497
540
21,64
25
300
345
389
19,86
201
234
14,31
202
234
14,63
25
500
345
389
19,86
356
387
16,63
353
390
20,73
25
600
422
468
22,68
420
461
23,21
414
464
22,79
25
700
502
541
21,87
493
549
26,91
490
539
23,84
25
800
577
616
21,45
574
617
24,95
563
617
24,54
30
300
201
238
16,7
200
237
15,54
203
236
15,71
30
400
277
311
15,27
282
311
15,82
274
311
19,07
30
500
351
391
20,2
347
389
18,56
354
394
19,86
30
600
416
469
23,86
422
463
22,78
422
465
22,36
30
700
497
539
22,8
501
544
25,26
490
542
24,71
30
800
570
617
23,68
567
620
26,76
564
618
28,77
cada seqüência do conjunto. As colunas Min, Média, Max, representam respectivamente os valores mínimos, médios e máximos encontrados da distância de Hamming
para mensurar esses valores.
O tempo de processamento de cada heurística foi limitado em 300 segundos, ou
5 minutos. A Tabela 5.9 apresenta os resultados numéricos para a heurística IGSPCCP, com perturbação k = 50%, e, para o método BRKGA-PCCP, com população
p = 1000 indivíduos. A dimensão dos conjuntos T OP , REST e BOT da heurística
BRKGA-PCCP foi configurada com 0, 25|p|, 0, 70|p| e 0, 05|p| respectivamente, sendo
p o tamanho da população. Os resultados numéricos com valores em negrito indicam
as soluções ótimas encontradas pela respectiva heurística.
Na Tabela 5.9, a heurística BRKGA-PCCP apresentou melhores resultados em
relação à heurística IGS-PCCP em todas as instâncias, seja para os valores mínimos
encontrados, seja quanto aos valores médios e máximos.
A Tabela 5.10 mostra a comparação entre os resultados para as heurísticas
5.5
Experimentos Computacionais
49
Tabela 5.3: Comparação entre os resultados das perturbações em k da heurística
IGS-PCCP para k = 60% e 70%.
Instâncias
IGS-PCCP k = 60%
IGS-PCCP k = 70%
n
m
Min
Max
Desv
Min
Max
Desv
10
300
205
232
12,42
209
234
12,56
10
500
358
388
14,54
349
380
14,4
10
700
505
539
17,04
493
539
19,57
15
300
206
232
14,16
209
234
11,94
15
500
358
383
17,34
350
387
17,8
15
700
501
543
22,89
493
540
20,81
20
300
209
236
12,73
205
233
13,66
20
500
355
387
17,86
344
391
19,63
20
700
483
536
26,31
500
539
21,83
25
300
206
235
15,26
211
233
12,75
25
500
353
386
17,28
348
390
21,39
25
600
425
470
20,92
417
467
22,54
25
700
497
541
21,83
494
534
22,17
25
800
569
616
24,12
579
616
22,48
30
300
204
238
17,38
206
235
14,39
30
400
279
311
18,41
274
312
19,67
30
500
350
392
21,13
351
393
20,56
30
600
414
467
23,58
417
471
24,04
30
700
484
537
22,9
495
547
24,53
30
800
573
617
25,1
560
616
27,86
BRKGA-PCCP e IGS-PCCP, com alfabeto Ω = {20, 30}. A primeira coluna indica o alfabeto Ω que compõe as cadeias de caracteres. As colunas Min, Média e
Max indicam, respectivamente, os valores mínimos, médias e máximos encontrados
pela execução de cinco vezes cada uma das instâncias das duas heurísticas propostas
nesta dissertação. Para todas as instâncias da Tabela 5.10, são utilizadas instâncias
com n = 10 e m = 500. Os resultados em negrito indicam os valores ótimos encontrados em relação às heurísticas BRKGA-PCCP e IGS-PCCP. Novamente, o algoritmo
BRKGA-PCCP obteve melhores resultados para todas as instâncias envolvidas.
5.5
Experimentos Computacionais
50
Tabela 5.4: Comparação entre os resultados das perturbações no parâmetro k da
heurística IGS-PCCP para o alfabeto Ω = {20}, com n = 10 e m = 500.
k = 0, 1
k = 0, 2
k = 0, 3
k = 0, 4
k = 0, 5
k = 0, 6
k = 0, 7
5.5
Min
465
461
464
461
463
Max
478
478
480
482
479
Desv
7,03
Min
461
463
458
465
464
Max
479
479
478
482
478
Desv
9,25
8,35
9,2
8,76 6,93
Min
458
465
467
462
462
Max
4480
477
480
476
479
Desv
9,66
7,22
7,38
7,9
9,01
Min
468
468
464
461
463
Max
479
477
480
480
479
Desv
6,55
6,97
8,82 8,96 7,93
Min
454
467
467
468
460
Max
482
480
481
479
481
Desv
10,9
7,16
8,33 6,06 9,18
Min
463
463
463
464
463
Max
480
478
476
480
479
Desv
8,46
7,88
8,44 9,04
7,2
Min
465
463
466
462
462
Max
481
481
480
478
478
Desv
9,33
7,98
7,92 7,57 8,72
10,02 7,14 10,3 9,53
Comparação entre as heurísticas BRKGA-PCCP
e PI
Na Tabela 5.11 é mostrada a comparação dos resultados obtidos pela heurística
BRKGA-PCCP e pelos resultados de Programação Inteira (PI) apresentados em
Meneses et al. (2004). A escolha da heurística BRKGA-PCCP se deve ao fato desta
ter obtido valores ótimos melhores em comparação com a heurística IGS-PCCP. As
colunas Min, Média, Max e Tempo indicam, respectivamente, os valores mínimos,
médias, máximos e tempo, medido em segundos, para os resultados encontrados
pela distância de Hamming. Os valores numéricos marcados em negrito indicam os
melhores resultados obtidos da comparação entre as heurísticas BRKGA-PCCP e
Programação Inteira.
Os testes da heurística de Meneses et al. (2004) foram realizados com um processador Pentium 4 CPU com 2.80 GHz e 512 MB de RAM, Windows XP. A heurística
foi implementada em linguagem C++ e CPLEX 8.1 (ILOG 2003). Como critério de
5.5
Experimentos Computacionais
51
Tabela 5.5: Comparação entre os resultados das perturbações da heurística IGSPCCP para o alfabeto Ω = {30}, com n = 10 e m = 500.
k = 0, 1
k = 0, 2
k = 0, 3
k = 0, 4
k = 0, 5
k = 0, 6
k = 0, 7
Min
476
474
471
475
474
Max
488
485
485
487
488
Desv
6,1
6,65 7,45 6,52 6,78
Min
473
472
472
474
473
Max
486
487
489
489
486
Desv
6,13 7,32 8,07 7,56 7,63
Min
470
474
472
472
477
Max
488
486
485
486
487
Desv
7,99 7,24
6,9
7,79 5,85
Min
470
476
471
477
475
Max
486
488
486
486
487
Desv
8,03 5,75 6,38 5,86 6,24
Min
470
474
479
474
470
Max
488
488
489
486
486
Desv
7,24 7,11 5,92
7,3
8,06
Min
473
473
470
474
475
Max
485
486
487
486
488
Desv
6,61 6,62 7,42 6,25 5,96
Min
473
475
476
476
474
Max
487
486
486
487
486
Desv
6,58 7,36 5,89 5,59
6,4
parada da heurística Programação Inteira, foi utilizado o número de iterações igual
a 10.000.
Os resultados mostram que a heurística BRKGA-PCCP é fortemente competitiva
frente aos resultados ótimos encontrados pela aplicação da heurística em Programação inteira apresentados em Meneses et al. (2004). Em 8 das 20 instâncias foram
encontrados os valores ótimos apresentados na referência citada.
5.5
Experimentos Computacionais
52
Tabela 5.6: Comparação entre os resultados das populações p = 100, p = 500 e
p = 1000 para a heurística BRKGA-PCCP, com Ω = {4}.
Instâncias
p = 100 indivíduos
p = 500 indivíduos
p = 1000 indivíduos
n
m
Min
Max
Desv
Min
Max
Desv
Min
Max
Desv
10
300
192
198
1,8
176
180
1,3
174
177
1,1
10
500
331
338
2,12
297
302
1,48
292
295
0,94
10
700
466
476
3,49
419
427
2,37
411
414
0,95
15
300
196
206
3,02
183
188
1,89
181
185
1,66
15
500
336
349
3,95
313
319
1,9
306
310
1,51
15
700
485
496
3,41
444
450
2,22
433
438
1,79
20
300
202
210
3,38
189
196
2,28
187
193
2,22
20
500
345
356
3,74
323
330
2,55
315
321
2,26
20
700
489
500
3,71
455
461
2,22
446
452
2,32
25
300
207
215
3,27
192
202
3,16
193
199
2,28
25
500
342
359
5,87
326
336
3,07
323
328
1,81
25
600
408
432
8,22
392
404
3,55
385
394
3,41
25
700
483
508
7,15
463
471
2,9
453
460
2,67
25
800
562
582
6,59
530
539
3,29
519
526
2,54
30
300
196
216
6,31
196
204
3,65
194
200
2,44
30
400
274
289
5,51
265
272
2,98
262
268
2,44
30
500
348
365
6,38
333
343
3,37
323
335
3,74
30
600
426
438
4,63
399
408
3,66
394
402
2,99
30
700
488
508
6,78
465
480
4,79
461
469
2,91
30
800
559
580
7,65
534
548
4,08
526
534
3,16
Tabela 5.7: Comparação entre os resultados das diferentes populações p da heurística
BRKGA-PCCP para o alfabeto Ω = {20}.
p = 100
p = 500
p = 1000
Min
450
449
452
449
449
Max
455
454
457
456
457
Desv
1,48
1,7
1,79 2,55 2,55
Min
417
415
417
415
415
Max
422
418
423
419
422
Desv
1,95 1,25 1,79 1,34 2,16
Min
404
403
404
403
404
Max
406
404
405
405
406
Desv
1,15 1,43 1,17
1,1
1,34
5.5
Experimentos Computacionais
53
Tabela 5.8: Comparação entre os resultados das diferentes populações p da heurística
BRKGA-PCCP para o alfabeto Ω = {30}.
p = 100
p = 500
p = 1000
Min
460
461
462
462
463
Max
469
469
466
468
467
Desv
2,91 2,50 1,47 1,91 1,16
Min
430
430
432
432
432
Max
437
433
435
436
436
Desv
2,57 1,05 0,85 1,37 1,25
Min
419
419
416
417
417
Max
420
420
417
420
419
Desv
1,54 0,94 1,72 1,91 1,83
5.5
Experimentos Computacionais
54
Tabela 5.9: Comparação entre os resultados das heurísticas BRKGA-PCCP e IGSPCCP, para instâncias tendo Ω = {4}; n ∈ {10, 15, 20} e m ∈ {300, 500, 700};
n = 25 e m ∈ {300, 500, 600, 700, 800}; n = 30 e min{300, 400, 500, 600, 700, 800}
Instâncias
BRKGA-PCCP
IGS-PCCP
n
m
Min
Média
Max
Min
Média
Max
10
300
174
174,8
177
201
212,4
234
10
500
292
293,2
295
356
359,4
382
10
700
411
412,2
414
499
508,2
544
15
300
181
181,6
185
207
211,8
230
15
500
306
307,2
310
351
356
384
15
700
433
434,6
438
492
501,4
537
20
300
187
188,8
193
208
211,8
233
20
500
315
316,8
321
350
355,8
384
20
700
446
448,6
452
497
504,4
540
25
300
193
194
199
202
209,4
234
25
500
323
324,2
328
353
355
390
25
600
385
387
394
414
425
464
25
700
453
454,4
460
490
502
539
25
800
519
520,4
526
563
574,8
617
30
300
194
195,6
200
203
208,6
236
30
400
262
263
268
274
279
311
30
500
323
329
335
354
357,2
394
30
600
394
395,8
402
422
427,4
465
30
700
461
463,2
469
490
502,2
542
30
800
526
527,6
534
564
571
618
5.5
Experimentos Computacionais
55
Tabela 5.10: Comparação entre os resultados das heurísticas BRKGA-PCCP e IGSPCCP para o alfabeto Ω = {20, 30}, n = 10 e m = 500.
Alfabeto
BRKGA-PCCP
IGS-PCCP
Ω
Min
Média
Max
Min
Média
Max
20
404
405,2
406
461
465
479
403
403,6
404
463
465,2
479
404
405
405
458
464,8
478
403
404
405
465
467,6
482
404
405,2
406
464
467,8
478
419
420
420
473
477,8
486
419
419,4
420
472
475,6
487
416
417,6
417
472
476
489
417
420
420
474
477,2
489
417
418,6
419
473
475,4
486
30
5.5
Experimentos Computacionais
56
Tabela 5.11: Comparação entre os resultados da heurística BRKGA-PCCP e os
resultados de Programação Inteira apresentados em Meneses et al. (2004).
Instâncias
BRKGA-PCCP
Programação Inteira
n
m
Min
Média
Max
Min
Média
Max
Tempo
10
300
174
174,8
177
174
175.50
177
0,12
10
500
292
293,2
295
288
289.50
292
0,34
10
700
411
412,2
414
405
407.50
410
1,84
15
300
181
181,6
185
183
184.25
187
6,02
15
500
306
307,2
310
306
306.50
307
44,98
15
700
433
434,6
438
426
428.50
432
21.78
20
300
187
188,8
193
190
190.25
191
1.170,98
20
500
315
316,8
321
314
316.25
319
901,44
20
700
446
448,6
452
442
442.75
444
940,21
25
300
193
194
199
195
195.75
196
2.741,15
25
500
323
324,2
328
321
323.25
325
741,62
25
600
385
387
394
387
388.00
389
1.805,16
25
700
453
454,4
460
450
452.25
453
907,61
25
800
519
520,4
526
515
516.75
520
1.254,19
30
300
194
195,6
200
198
198.25
199
3.223,68
30
400
262
263
268
262
263.25
264
1.852,67
30
500
323
329
335
326
329.25
331
2.215,67
30
600
394
395,8
402
393
394.25
395
2.700,30
30
700
461
463,2
469
459
459.75
460
1.803,28
30
800
526
527,6
534
522
523.50
526
2.337,20
Capítulo 6
Considerações Finais
Esta dissertação apresentou o estudo sobre o Problema da Cadeia de Caracteres
Mais Próxima (PCCP), sendo propostas duas heurísticas para a solução deste problema. No PCCP, o objetivo é encontrar uma seqüência centro t, que minimize a
distância desta às demais cadeias de caracteres de um dado conjunto com seqüências
de mesma dimensão.
Para a solução do PCCP, foram implementadas as heurísticas Biased RandomKey Genetic Algorithms (BRKGA) e Iterated Greedy Search (IGS), que foram comparadas entre si. Posteriormente, os melhores resultados, que foram obtidos pela
heurística BRKGA-PCCP, foram comparados com os da heurística Programação
Inteira do trabalho de Meneses et al. (2004). A justificativa para o uso do algoritmos genéticos com chaves aleatórias tendenciosas é pela sua aplicação bem sucedida
em vários problemas de otimização, citados nesta dissertação.
Inicialmente foi apresentada uma introdução mostrando fatores que levaram ao
surgimento do PCCP e suas variações, para resolução de problemas reais da Biologia Molecular. Foram apresentadas também as definições de DNA, RNA e síntese
protéica. No Capítulo 2, foram apresentados os trabalhos mais importantes relacionados ao PCCP, destacando as heurísticas utilizadas e os problemas abordados.
No Capítulo 3, foram apresentadas as característica do PCCP e suas formulações,
como também outros problemas que abordam a comparação e seleção de cadeias
de caracteres. No Capítulo 4, foram apresentados os algoritmos mais usados para
a resolução do PCCP encontrados na literatura, assim como as heurísticas utilizadas para resolução do mesmo nesta dissertação. No Capítulo 5, foram abordadas
as instâncias extraídas do trabalho de Meneses et al. (2004) para a solução deste
problema, bem como os resultados dos experimentos computacionais propostos.
A partir dos resultados apresentados no Capítulo 5, pode-se concluir que os
algoritmos propostos para o Problema da Cadeia de Caracteres Mais Próxima demonstraram eficiência na resolução do problema em questão.
Observou-se que a heurística IGS-PCCP não gerou bons resultados, ficando sempre atrás dos resultados alcançados pela heurística BRKGA-PCCP. O valor mais
próximo que a heurística IGS-PCCP alcançou do BRKGA-PCCP foi para as instâncias n = 25 e n = 30, ambas para m = 300, com nove unidades da distância de
Hamming de diferença.
Analisando as cadeias de caracteres formadas por um alfabeto Ω = {4}, pode-se
verificar que, para valores de n ∈ {15, 10, 25, 30} e m = 300, n = 25 com m =
57
6.0
Considerações Finais
58
600 e n = 30 com m = 500, conseguiu-se superar os valores dos resultados da
heurística Programação Inteira proposta por Meneses et al. (2004). Para valores
de n = 15 com m = 500 e n = 30 com m = 400, os valores foram iguais entre as
heurística (ver Tabela 5.11). Para os valores das demais instâncias, as distâncias de
Hamming obtidas ficaram muito próximas aos da heurística Programação Inteira,
com diferenças que, em alguns casos, chegam a 8 unidades no máximo. Com relação
ao tempo de processamento, a heurística BRKGA-PCCP alcançou, na maioria dos
casos, valores muito abaixo dos encontrados pela heurística de Meneses et al. (2004),
sendo, em alguns resultados, 90% mais rápido e obtendo valores melhores.
Para as cadeias de caracteres com um alfabeto Ω = {20, 30}, a heurística BRKGAPCCP também obteve melhores resultados para a distância mínima de Hamming em
relação à heurística IGS-PCCP. Os testes para as duas heurísticas foram realizadas
com um tempo limite de cinco minutos de processamento.
Conclui-se, então, que a heurística BRKGA-PCCP se mostrou bastante robusta,
obtendo valores próximos do ótimo em um tempo de processamento reduzido.
Como trabalhos futuros, há a necessidade de um melhor ajuste dos parâmetros
das heurísticas, como número de iterações, tempo de processamento, dentre outros
que devem ser feitos através de testes. O desenvolvimento de outras formulações
matemáticas e também a implementação de algoritmos que ainda não foram testados
poderão trazer melhores resultados.
Referências Bibliográficas
Andronescu, Mirela e Rastegari, Baharak. (2003). Motif-grasp and motif-ils: Two
new stochastic local search algorithms for motif finding. Relatório técnico, Computer
Science Department, University of British Columbia, Vancouver, Canada.
Arulselvan, A.; Commander, C. e Pardalos, P. (2007). A random keys based genetic
algorithm for the target visitation problem. Advances in Cooperative Control and
Optimization, volume 369, p. 389–397. Springer.
Avery, O. T.; MacLeod, C. M. e McCarty, M. (1944). Studies on the chemical
nature of the substance inducing transformation of pneumococcal types: Induction
of transformation by a desoxyribonucleic acid fraction isolated from pneumococcus
type iii. Journal of Experimental Medicine, v. 79, n. 2, p. 137–158.
Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, v. 2, p. 154–160.
Ben-Dor, A.; Lancia, G.; Perone, J. e Ravi, R. (1997). Banishing bias from consensus
sequences. in: Proceedings of the 8th Annual Symposium on Combinatorial Pattern
Matching, v. 247–261.
Boucher, C.; Landau, G. M.; Levy, A.; Pritchard, D. e Weimann, O. (2012). On
approximating string selection problems with outliers. Kärkkäinen, J. e Stoye, J.,
editors, Combinatorial Pattern Matching, volume 7354 of Lecture Notes in Computer
Science, p. 427–438. Springer Berlin Heidelberg.
Buriol, L. S.; Resende, M. G. C.; Ribeiro, C. C. e Thorup, M. (2005). A hybrid
genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks,
v. 46, p. 36–56.
Buriol, L. S.; Resende, M. G. C. e Thorup, M. (2007). Survivable IP network design
with OSPF routing. Networks, v. 49, p. 51–64.
Chen, Jing-Chao. (2009). Iterative rounding for the closest string problem. Proceedings of the 5th Conference on Computability in Europe (CiE 2009), p. 89–98,
Heidelberg, Germany.
Chen, Zhi-Zhong; Ma, Bin e Wang, Lusheng. (2010). A three-string approach to
the closest string problem. Journal of Computer and System Sciences, v. 6196, p.
449–458.
59
Referências Bibliográficas
60
Chimani, M.; Woste, M. e Böcker, S. (2011). A closer look at the closest string
and closest substring problem. Müller-Hannemann, M. e Werneck, R. F. F., editors,
Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX
2011), p. 13–24, (2011).
Ciffler, B. (1963). Scheduling general production systems using schedule algebra.
Naval Research Logistics Quarterly, v. 10, n. 1, p. 237 – 255.
Crowston, W. B.; Glover, F.; Thompson, G. L. e Trawick, J. D. (1963). Probabilistic
and parametric learning combinations of local job shop scheduling rules. ONR
Research Memorandum 117, Carnegie-Mellon University, Pittsburgh, PA, EUA.
daFonseca, Paulo Gustavo Soares. Índices completos para casamento de padrões e
inferência de motifs. Dissertação de Mestrado, Universidade Federal de Pernambuco,
(2003).
de Souza, J. C. Aplicação de metaheurísticas ao problema da cadeia de caracteres
mais próxima. Dissertação de Mestrado, Centro Federal de Educação Tecnológica
De Minas Gerais (CEFET), (2012).
Deng, Xiaotie; Li, Guojun e Wang, Lusheng. (2002). Center and distinguisher for
strings with unbounded alphabet. Journal of Combinatorial Optimization, v. 6, p.
383–400.
Dias, L. G. S.; Goulart, N.; Noronha, T. F. e deSouza, S. R. (2011). Algoritmo
genético para o problema de instalação de fibras em redes Óticas. XLIII Simpósio
Brasileiro de Pesquisa Operacional, Ubatuba, SP.
Ecker, J. G.; Kupferschmid, M.; Lawrence, C. E.; Reilly, A. A. e Scott, A. C. H.
April(2002). An application of nonlinear optimization in molecular biology. European
Journal of Operational Research, v. 138, n. 2, p. 452–458.
Fanjul-Peyroa, L. e Ruiz, R. (2010). Iterated greedy local search methods for
unrelated parallel machine scheduling. European Journal of Operational Research,
v. 207, p. 55–69.
Faro, Simone e Pappalardo, Elisa. (2010). Ant-csp: An ant colony optimization
algorithm for the closest string problem. SOFSEM 2010: Theory and Practice of
Computer Science, volume 5901 of SOFSEM ’10, p. 370–381, Berlin, Heidelberg.
Springer-Verlag.
Feo, Thomas A. e Resende, Mauricio G.C. (1995). Greedy randomized adaptive
search procedures. Journal of Global Optimization, v. 6, p. 109–133.
Ferone, Daniele; Festa, Paola e Resende, Mauricio G. C. (2013). Hybrid metaheuristics for the far from most string problem. Hybrid Metaheuristics, p. 174 – 188.
Springer Berlin Heidelberg, (2013).
Festa, Paola. (2007). On some optimization problems in molecular biology. Mathematical Biosciences, v. 207, p. 219–234.
Referências Bibliográficas
61
Fogel, Gary B.; Porto, V. William; Weekes, Dana G.; Fogel, David B.; Griffey, Richard H.; McNeil, John A.; Lesnik, Elena; Ecker, David J. e Sampath, Rangarajan.
(2002). Discovery of rna structural elements using evolutionary computation. Nucleic Acids Research, v. 30, p. 5310 – 5317.
Framinan, Jose e Leisten, Rainer. (2008). A multi-objective iterated greedy search
for flowshop scheduling with makespan and flowtime criteria. OR Spectrum, v. 30,
p. 787–804.
Gagnaire, M. e Doumith, E. (2007). An iterative greedy algorithm for scheduled traffic grooming in wdm optical networks. Advanced Networks and Telecommunication
Systems First International Symposium On, (2007).
Garcia, B. L.; Mahey, P. e LeBlanc, L. J. (1998). Iterative improvement methods
for a multiperiod network design. European Journal of Operational Research, v. 110,
p. 150–165.
Gasieniec, Leszek; Jansson, Jesper e Lingas, Andrzej. (1999). Efficient approximation algorithms for the hamming center problem. Proceedings of the tenth annual
ACM-SIAM Symposium on Discrete algorithms, SODA’99, p. 905–906, Philadelphia,
PA, USA. SIAM.
Glover, F. (1997). Tabu search and adaptive memory programing: Advances, applications and challenges. Barr, R. S.; Helgason, R. V. e Kennington, J. L., editors,
Interfaces in Computer Science and Operations Research, volume 7 of Operations
Research/Computer Science Interfaces Series, p. 1–75. Springer US.
Goldberg, D. E. e Holland, J. H. (1988). Genetic algorithms and machine learning.
Machine Learning, v. 3, n. 2-3, p. 95–99.
Gomes, Fernando C.; Meneses, Cláudio N.; Pardalos, Panos M. e Viana, Gerardo
Valdisio R. (2008). A parallel multistart algorithm for the closest string problem.
Computers and Operations Research, v. 35, p. 3636–3643.
Gonçalves, J. F. e Almeida, J. (2002). A hybrid genetic algorithm for assembly line
balancing. Journal of Heuristics, v. 8, p. 629–642.
Gonçalves, J. F.; Mendes, J. J. M. e Resende, M. G. C. (2005). A hybrid genetic
algorithm for the job shop scheduling problem. European Journal of Operational
Research, v. 167, p. 77–95.
Gonçalves, J. F. e Resende, M. G. C. (2004). An evolutionary algorithm for manufacturing cell formation. Computers and Industrial Engineering, v. 47, p. 247–273.
Gonçalves, José Fernando e Resende, Mauricio G. C. (2011). Biased random-key
genetic algorithm for combinatorial optimization. JOURNAL OF HEURISTICS, v.
17, p. 487–525.
Gramm, J.; Niedermeier, R. e Rossmanith, P. (2001). Exact solutions for closest
string and related problems. Algorithms and Computation, v. 2223, p. 441–453.
Referências Bibliográficas
62
Gramm, Jens; Guo, Jiong e Niedermeier, Rolf. (2006). Parameterized intractability
of distinguishing substring selection. Theory of Computing Systems, v. 39, p. 560.
Hansen, Pierre e Mladenovic, Nenad. (2002). Developments of variable neighborhood
search. Operations Research/Computer Science Interfaces Series, v. 15, p. 415 – 439.
Held, M. e Karp, R. M. (1971). The traveling salesman problem and minimum
spanning trees. Mathematical Programming, v. 1, p. 6 – 25.
Hirschberg, D. S. (1975). A linear space algorithm for computing maximal common
subsequences. Magazine Communications of the ACM, v. 18 Issue 6, p. 341 – 343.
Holland, J. H. (1975). Adaptation in natural and artificial systems. University of
Michigan Press, Ann Arbor, MI, EUA.
Hufsky, Franziska; Kuchenbecker, Léon; Jahn, Katharina; Stoye, Jens e Böcker, Sebastian. (2010). Swiftly computing center strings. Moulton, Vincent e Singh, Mona,
editors, Algorithms in Bioinformatics, 10th International Workshop, WABI 2010,
Liverpool, UK, September 6-8, 2010. Proceedings, volume 6293 of Lecture Notes in
Computer Science, p. 325–336. Springer, (2010).
Jain, Kamal. (2001). A factor 2 approximation algorithm for the generalized steiner
network problem. Combinatorica, v. 21, p. 39 – 60.
Jiang, T.; Trendall, C.; Wang, S.; Wareham, T. e Zhang, X. (2000). Drug target
identification using gibbs sampling techniques. Proceedings of Pacific Symposium
on Biocomputing, p. 389 – 400, (2000).
Julstrom, Bryant A. (2009). A data-based coding of candidate strings in the closest
string problem. Proceedings of the 11th Annual Conference Companion on Genetic
and Evolutionary Computation Conference: Late Breaking Papers, GECCO ’09, p.
2053–2058, New York, NY, USA. ACM.
Kelsey, Tom e Kotthoff, Lars. (2010). The exact closest string problem as a constraint
satisfaction problem. Computing Research Repository, v. abs/1005.0089.
Kochenberger, Gary A.; McCarl, Bruce A. e Wyman, F. Paul. (1974). A heuristic
for general integer programming. Decision Sciences, v. 5, p. 36 – 44.
Lacerda, E. G. M. e Carvalho, A. C. P. L. F. (1999). Introdução aos algoritmos
genéticos. Galvão, C. O. e Valença, M. J. S., editors, Sistemas Inteligentes: Aplicações a Recursos Hídricos e Ciências Ambientais, volume 1, p. 99–148. Editora da
Universidade Federal do Rio Grande do Sul, Porto Alegre, RS, 1 edição.
Lanctot, J. K.; Li, M.; Ma, B.; Wang, S. e Zhang, L. (1999). Distinguishing
string selection problems. Proceedings of the tenth annual ACM-SIAM symposium
on Discrete algorithms, p. 633 – 642, (1999).
Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu e Zhang, Louxin. (2003).
Distinguishing string selection problems. Information and Computation, v. 185, p.
41 – 55.
Referências Bibliográficas
63
Lawler, E.L.; Lenstra, J.K.; Kan, A.H.G. Rinnooy e Shmoys, D.B. (1985). The
traveling salesman problem. Networks, v. 18, p. 253 – 254.
Lawrence, V. S. e Mark, S. D. (2006). A random-key genetic algorithm for the
generalized traveling salesman problem. European Journal of Operational Research,
v. 174, p. 38–53.
Lesk, A. M. (2008). Introdução à Bioinformática. Artmed, 2 edição.
Li, Ming; Ma, Bin e Wang, Lusheng. (1999). Finding similar regions in many strings.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of computing
(STOC’99), p. 473–482, (1999).
Li, Ming; Ma, Bin e Wang, Lusheng. (2002). On the closest string and substring
problems. Journal of the ACM, v. v. 49, n. 2, p. 157–171.
Liu, X.; Holger, M.; Hao, Z. e Wu, G. (2008). A compounded genetic and simulated
annealing algorithm for the closest string problem. The 2nd International Conference
on Bioinformatics and Biomedical Engineering, 2008 (ICBBE 2008), p. 702 – 705,
(2008).
Liu, Xiaolan; Fu, Keqiang e Shao, Renxiang. (2004). Largest distance decreasing
algo- rithm for the closest string problem. Journal of Information & Computational
Science, v. 1(2), p. 287–292.
Liu, Xiaolan; Liu, Shenghan; Hao, Zhifeng e Mauch, Holger. (2011). Exact algorithm
and heuristic for the closest string problem. Computers &OperationsResearch, v. 38,
p. 1513–1520.
Liu, Xuan; He, Hongmei e Sýkora, Ondrej. July 22-24, 2005(2005). Parallel genetic
algorithm and parallel simulated annealing algorithm for the closest string problem.
Advanced Data Mining and Applications, volume 3584, p. 591–597, Wuhan, China.
Springer Berlin Heidelberg.
Los, M. e Lardinois, C. (1982). Combinatorial programming, statistical optimization
and the optimal transportation network problem. Transportation Research, v. 2, p.
89 – 124.
Lourenço, Helena R.; Martin, Olivier C. e Stützle, Thomas. (2002). Iterated local
search. Handbook of Metaheuristics, volume 57 of International Series in Operations Research and Management Science, p. 321–353. Kluwer Academic Publishers,
(2002).
M. Frances, A. Litman. (1997). On covering problems of codes. Theory Comput.
Syst., v. 30, n. 2, p. 113–119.
Ma, Bin. (2000). A polynomial time approximation scheme for the closest substring
problem. Combinatorial Pattern Matching, v. 1848, p. 99 – 107.
Ma, Bin e Sun, Xiaoming. (2009). More efficient algorithms for closest string and
substring problems. SIAM Journal on Computing, v. 39(4), p. 1432–1443.
Referências Bibliográficas
64
Maes, J.; McClain, J. O. e Wassenhove, L. N. V. (1991). Multilevel capacitated lotsizing complexity and ip-based heuristics. European Journal Of Operational Research,
v. 53, p. 131 – 148.
Malve, S. e Uzsoy, R. (2007). A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and
incompatible job families. Computers and Operations Research, v. 34, p. 3016–3028.
Martí, R. (2003). Multi-start methods. Glover, F. e Kochenberger, G., editors,
Handbook of Metaheuristics, volume 57, p. 355–368. Springer.
Martí, Rafael; Resende, Mauricio G.C. e Ribeiro, Celso C. (2013). Multi-start
methods for combinatorial optimization. European Journal of Operational Research,
v. 226, n. 1, p. 1 – 8.
Mauch H, Hu JSMelzer MJ. (2003). Genetic algorithm approach for the closest
string problem. Proceedings of the 2003 IEEE Computer Society Conference on
Bioinformatics (CSB’03), p. 560–561, (2003).
McClure, Marcella A.; Vasi, Taha K. e Fitch, Walter M. (1994). Comparative
analysis of multiple protein- sequence alignment methods. Molecular Biology and
Evolution, v. 1994, p. 571–592.
Meneses, C. N.; Oliveira, C. A. S. e Pardalos, P. M. (2005). Optimization techniques
for string selection and comparison problems in genomics. Engineering in Medicine
and Biology Magazine, IEEE, v. 24, p. 81 – 87.
Meneses, Cláudio N.; Lu, Zhaosong; Oliveira, Carlos A. S. e Pardalos, Panos M.
(2004). Optimal solutions for the closest-string problem via integer programming.
INFORMS Journal of Computing, v. 16, n. 4, p. 419–429.
Montemanni, Roberto e Smith, Derek. (2008). Construction of constant gc-content
dna codes via a variable neighbourhood search algorithm. Journal of Mathematical
Modelling and Algorithms, Vol. 7, No. 3. (2008), pp. 311-326, v. 7, n. 3, p. 311–326.
Mousavi, Sayyed Rasoul e Esfahani, Navid Nasr. (2012). A grasp algorithm for
the closest string problem using a probability-based heuristic. Comput. Operations
Research, v. 39, n. 2, p. 238–248.
Noronha, T. F.; Resende, M. G. C. e Ribeiro, C. C. (2011). A biased randomkey genetic algorithm for routing and wavelength assignment. Journal of Global
Optimization, v. 50, p. 503–518.
Pappalardo, E. Combinatorial Optimization Methods for Problems in Genomics.
Phd thesis, University of Catania, Department of Mathematics and Computer Science, University of Catania, (2012).
Park, S. K. e Miller, K. W. (1988). Random number generators: good ones are hard
to find. Communications of the ACM, v. 31, p. 1192 – 1201.
Pasternak, J. J. (2002). Genética molecular humana: mecanismos das doenças
hereditárias. Editora Manole Ltda.
Referências Bibliográficas
65
Pinto, Eduardo Ribas; dosAnjos Formiga Cabral, Lucídio e Macambira, Elder Magalhães. (2006). Metaheurística grasp na resolução do problema da cadeia de caracteres
mais próxima. XXXVIII SBPO, (2006).
Prosdocimi, F.; Cerqueira, G.C.; Binneck, E.; Silva, A. N.A. F.and Reis; Junqueira, A. C.M.; Santos, A. C. F.; Júnior, A. N.; Wust, C. I.; Filho, F. C.; Kessedjian, J. L.; Petretski, J. H.; Camargo, L. P.; Ferreira, R. G. M.; Lima, R. P.;
Pereira, R. M.; Jardim, S.; Sampaio, V. S. e Folgueras-flatschart, A. V. Novembro/
Dezembro(2002). Bioinformática: Manual do usuário. Biotecnologia, Ciência &
Desenvolvimento, v. 5, n. 29, p. 12–25.
Reis, R.; Ritt, M.; Buriol, L. S. e Resende, M. G. C. (2011). A biased randomkey genetic algorithm for ospf and deft routing to minimize network congestion.
International Transactions in Operational Research, v. 18, p. 401–423.
Resende, Mauricio G. C. (2012). Biased random-key genetic algorithms with applications in telecommunications. TOP: An Official Journal of the Spanish Society of
Statistics and Operations Research, v. 20, n. 1, p. 130–153.
Roman, S. (1992). Coding and information theory. Graduate Texts in Mathematics,
Springer-Verlag, v. 134.
Ruiz, R. e Stützle, T. (2007). A simple and effective iterated greedy algorithm
for the permutation flowshop scheduling problem. European Journal of Operational
Research, v. 177, p. 2033–2049.
Saetrom, P.; Sneve, R.; Kristiansen, K.I.; Snøve, O.; Grünfeld, T.; Rognes, T. e
Seeberg, E. (2005). Predicting non-coding rna genes in escherichia coli with boosted
genetic programming. Nucleic Acids Res, v. 33, n. 10, p. 3263 – 3270.
Samanlioglu, F.; Ferrell, W. G.Jr. e Kurz, M. E. (2008). A memetic randomkey genetic algorithm for a symmetric multi-objective traveling salesman problem.
Computers and Industrial Engineering, v. 55, p. 439–449.
Senju, Shizuo e Toyoda, Yoshiaki. (1968). An approach to linear programming with
0 - 1 variables. Management Science, v. 15, p. 196 – 207.
Soleimani-damaneh, M. (2011). An optimization modelling for string selection in
molecular biology using pareto optimality. Applied Mathematical Modelling, v. 35,
n. 8, p. 3887–3892.
Spears, W. e deJong, K. (1991). On the virtues of parameterized uniform crossover.
Proceedings of the Fourth International Conference on Genetic Algorithms, p. 230–
236, San Mateo.
Stützle, T. Local Search Algorithms for Combinatorial Problems - Analysis, Improvements, and New Applications. PhD thesis, Darmstadt University of Technology,
Department of Computer Science, (1998).
Tanaka, Shunji. (2012). A heuristic algorithm based on lagrangian relaxation for
the closest string problem. Computers & Operations Research, v. v. 39, n. 3, p.
709–717.
Referências Bibliográficas
66
Watson, J. D. e Crick, F. H. (1953). Molecular Structure of Nucleic Acids; a
Structure for Deoxyribose Nucleic Acid. Nature, v. 171, n. 4356, p. 737–738.
Whitley, Darrell. (1993). A genetic algorithm tutorial. Statistics and Computing, v.
4, p. 65 – 85.
Yamamoto, Keity. Arredondamento randômico e o problema da sequência mais
próxima. Dissertação de Mestrado, Universidade Federal Fluminense, (2004).
Zörnig, Peter. (2011). Improved optimization modelling for the closest string and
related problems. Applied Mathematical Modelling, v. 35, n. 12, p. 5609–5617.