Universidade Estadual de Londrina
Centro de Tecnologia e Urbanismo
Departamento de Engenharia Elétrica
Alinhamento de Seqüências Biológicas Utilizando
Algoritmo Genético e Processamento Distribuı́do
Paulo Eduardo Mologni da Silva
Orientador
Prof. Dr. Ailton Akira Shinoda - UNESP/Ilha Solteira-SP
Banca Examinadora
Prof. Dr. Ailton Akira Shinoda - Presidente
Prof. Dr. Marcelo Carvalho Tosin - UEL/Londrina-PR
Profa. Dra. Maria Angélica de O. Camargo Brunetto - UEL/Londrina-PR
Dissertação submetida ao Departamento de Engenharia Elétrica
da Universidade Estadual de Londrina, para preenchimento
dos pré-requisitos parciais para obtenção do tı́tulo de
Mestre em Engenharia Elétrica
Londrina, 24 de março de 2005
Dedico este trabalho à toda minha famı́lia e amigos.
iii
Resumo
Este trabalho descreve um método alternativo para encontrar o alinhamento
ótimo de seqüências de nucleotı́deos utilizando Algoritmo Genético (AG). A seqüência
alinhada leva em conta o cromossomo e cada cromossomo é associado com uma
função objetiva (função de aptidão) baseada na matriz de substituição BLOSUM50
e implementado na linguagem C++ (Linux e Windows) com uma biblioteca de
programação distribuı́da (Messaging Passing Interface - MPI).
Duas implementações do algoritmo proposto foram analisadas, a primeira sem
o recurso de processamento distribuı́do (AG Serial), e a segunda com o recurso (AG
Paralelo).
Os resultados obtidos mostraram que o método é eficaz.
i
Abstract
This work describes an alternative method based on Genetic Algorithm (GA)
to find the optimal pair-wise alignment. The alignment sequence takes into account
the chromosome and each chromosome is associated with a fitness function based
on BLOSUM50 substitution matrix implemented in the C++ language (Linux e
Windows) with a distributed programming library (Messaging Passing Interface MPI).
Two implementations of the proposed algorithm were analyzed, the first without
the resource of distributed processing (Serial AG), and the second with the resource
(Parallel AG).
The obtained results showed that the method is effective.
ii
Agradecimentos
- A Deus e à minha famı́lia. Em especial: à minha esposa, à minha mãe e à minha
irmã as quais apoiaram-me e ajudaram-me muito; à minha tia Irene, grande incentivadora.
- Ao prof. Ailton Akira Shinoda, meu orientador, e ao prof. Carlos Dias Maciel,
co-orientador, pelo grande incentivo, apoio, amizade e profissionalismo;
- Aos demais amigos do curso: professores, funcionários e alunos que fizeram parte
desta caminhada;
- À CAPES pela bolsa de estudos;
- Ao CNPQ e à UEL pela infra-estrutura fornecida ao projeto intitulado: Análise
de Géis de Eletroforese, onde desenvolvemos este trabalho.
iii
Sumário
Resumo
i
Abstract
ii
Agradecimentos
iii
Sumário
iv
Lista de Figuras
vii
Lista de Tabelas
xii
Lista de Abreviaturas
xiv
Glossário
xvi
Introdução
xvii
1 Fundamentação
1.1
1
Fundamentos Biológicos . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.1
DNA: O Material Genético . . . . . . . . . . . . . . . . . . . .
1
1.1.2
Replicação do DNA: Transmissão da Informação Genética . .
3
1.1.3
Expressão Gênica: Controle do Crescimento e Desenvolvimento
4
iv
SUMÁRIO
1.1.4
Mutação: Mudanças no Material Genético com o Tempo . . .
1.1.5
Resumo:
8
Pontos Importantes . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2
1.3
Alinhamento de Seqüências Par-a-Par . . . . . . . . . . . . . . . . . . 12
1.2.1
Justificativa para o Alinhamento Protéico . . . . . . . . . . . 15
1.2.2
Gaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.3
Modelo de Pontuação: Matriz de Pontuação . . . . . . . . . . 17
1.2.4
Algoritmos de alinhamentos . . . . . . . . . . . . . . . . . . . 23
1.2.5
Significância das Pontuações . . . . . . . . . . . . . . . . . . . 33
Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.3.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.3.2
Definição e Funcionamento . . . . . . . . . . . . . . . . . . . . 38
1.3.3
Algoritmo Genético Paralelo . . . . . . . . . . . . . . . . . . . 43
2 Métodos e Materiais
2.1
2.2
2.3
50
Ambiente de Simulação . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.1.1
Linguagens de Programação Utilizadas . . . . . . . . . . . . . 50
2.1.2
Estrutura das Máquinas Utilizadas . . . . . . . . . . . . . . . 51
Alinhamento Biológico Através do Algoritmo Genético . . . . . . . . 52
2.2.1
Aproximação AG . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.2.2
Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.2.3
Dados Utilizados no AG Serial . . . . . . . . . . . . . . . . . . 62
Alinhamento Biológico Através do Algoritmo Genético Paralelo . . . 64
2.3.1
Computação Distribuı́da . . . . . . . . . . . . . . . . . . . . . 64
2.3.2
AG no Ambiente Distribuı́do . . . . . . . . . . . . . . . . . . . 69
2.3.3
Aproximação AG Paralela . . . . . . . . . . . . . . . . . . . . 71
v
SUMÁRIO
2.3.4
Dados Utilizados no AG Paralelo . . . . . . . . . . . . . . . . 76
3 Resultados
3.1
77
Análise de Desempenho do AG Serial Proposto
. . . . . . . . . . . . 78
3.1.1
Análise de Desempenho: Seqüencias SEQex1 e SEQex2 . . . . 79
3.1.2
Análise de Desempenho: Seqüencias P69905 e P68871 . . . . . 82
3.1.3
Tempo de Manipulação de Instâncias de Objetos versus Tempo
de Processamento . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.2
Comparação dos Resultados
do
AG
Serial
Proposto com o
Algoritmo de Needleman e Wunsch . . . . . . . . . . . . . . . . . . . 87
3.3
Comparação dos Resultados do AG Paralelo Proposto com o Algoritmo de Needleman e Wunsch . . . . . . . . . . . . . . . . . . . . . . 94
4 Conclusão
100
4.1
Conclusão dos Resultados do AG Serial . . . . . . . . . . . . . . . . . 100
4.2
Conclusão dos Resultados do AG Paralelo . . . . . . . . . . . . . . . 102
4.3
Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Referências Bibliográficas
104
vi
Lista de Figuras
1.1
Visão bidimensional da estrutura do DNA. A informação genética
dos seres vivos é armazenada nas grandes moléculas de DNA em
seqüências de pares de bases: A:T, T:A, G:C e C:G. . . . . . . . . . .
2
1.2
Replicação do DNA. A separação e a sı́ntese ocorrem de modo gradativo.
3
1.3
Exemplo da transcrição e tradução usando a sı́ntese da globina β humana. Durante a transcrição (etapa 1), o filamento de DNA é um molde para a sı́ntese de
um filamento de RNA complementar. O mRNA resultante (RNA mensageiro) é
transportado para o citoplasma. No citoplasma, a seqüência de bases do mRNA é
“traduzido” na seqüência de aminoácidos formando assim o polipeptı́dio do gene
de acordo com as regras do código genético. A tradução (etapa 2) ocorre em
estruturas complexas chamadas ribossomos. A sı́ntese de globina β final requer a
remoção pós-traducional da metionina terminal (etapa 3) [69]. . . . . . . . . .
7
1.4
Mutação: alteração em bases da seqüência de DNA [69]. . . . . . . . 10
1.5
Três alinhamentos de seqüências para um fragmento da globina α
humana. °
a Similaridade evidente para a globina β humana. °
b
Um alinhamento de forma estrutural razoável para a leghaemoglobina
do lupos amarelo. °
c Um alinhamento espúrio com alta pontuação
para uma glutationa homólogo do nematóide S-transferase chamada
F 11G11.2 [33]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6
Alinhamento par-a-par das proteı́nas RBP (Retinol-Binding Protein)
humana e β-lactoglobulina bovina [34]. . . . . . . . . . . . . . . . . . 16
vii
LISTA DE FIGURAS
1.7
Duas seqüências usadas para ilustrar os algoritmos de programação
dinâmica. Elas estão arranjadas por par de resı́duos alinhados de
forma a mostrar os valores correspondentes da matriz BLOSUM50.
As pontuações positivas estão em negrito.
1.8
. . . . . . . . . . . . . . . 24
Três caminhos possı́veis para o alinhamento até (i, j): xi alinhado
com yj , xi alinhado com um gap e yj alinhado com um gap. . . . . . 26
1.9
F (i, j) obtido a partir dos três valores possı́veis. . . . . . . . . . . . . 26
1.10 Matriz da programação dinâmica global. As setas mais largas, apontando para valores (em negrito) do alinhamento ótimo, representam
os ponteiros do traceback. O valor no canto inferior direito da matriz
é a pontuação total do alinhamento ótimo. . . . . . . . . . . . . . . . 27
1.11 Alinhamento obtido a partir do processo de traceback da Figura 1.10
e posterior inversão das seqüências χ e ψ. . . . . . . . . . . . . . . . . 28
1.12 Matriz da programação dinâmica local. Alinhamento ótimo local com
pontuação 28. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.13 Alinhamento obtido a partir do processo de traceback da Figura 1.12
e posterior inversão das seqüências χ e ψ. . . . . . . . . . . . . . . . . 30
1.14 Tipos de sobreposição dos pares de seqüência x e y. . . . . . . . . . . 31
1.15 Cruzamento de dois cromossomos em apenas uma posição. . . . . . . 39
1.16 Mutação em uma posição do cromossomo biológico. . . . . . . . . . . 40
1.17 Mutação em uma posição do cromossomo binário. . . . . . . . . . . . 40
1.18 Fluxograma para exemplificar o algoritmo genético. . . . . . . . . . . 41
1.19 Estrutura convencional do algoritmo genético. . . . . . . . . . . . . . 42
1.20 AG Global em Arquitetura DSM. . . . . . . . . . . . . . . . . . . . . 44
1.21 Pseudo-código do AG Migração [32]. . . . . . . . . . . . . . . . . . . 45
1.22 Topologia de Migração em Anel ou Unidirecional. . . . . . . . . . . . 46
1.23 Topologia de Migração da Vizinhança ou Bidirecional. . . . . . . . . . 46
viii
LISTA DE FIGURAS
1.24 Topologia de Migração Irrestrita ou Multidirecional. . . . . . . . . . . 47
1.25 Topologia AG de Difusão. . . . . . . . . . . . . . . . . . . . . . . . . 48
1.26 Pseudo-código do AG de Difusão [32]. . . . . . . . . . . . . . . . . . . 49
2.1
Um possı́vel alinhamento. . . . . . . . . . . . . . . . . . . . . . . . . 52
2.2
Outro possı́vel alinhamento. . . . . . . . . . . . . . . . . . . . . . . . 53
2.3
Descrição da configuração cromossômica binária. . . . . . . . . . . . . 53
2.4
Função de aptidão (fitness function). . . . . . . . . . . . . . . . . . . 54
2.5
Representação de um alinhamento na aproximação AG. . . . . . . . . 55
2.6
Pais selecionados para a operação de cruzamento na aproximação AG. 56
2.7
Operação de cruzamento na aproximação AG. . . . . . . . . . . . . . 56
2.8
Filhos gerados após a operação de cruzamento na aproximação AG.
As duas primeiras linhas representam um filho e as duas últimas o
outro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.9
Mutação AG: 2 pontos de mutação selecionados aleatoriamente. . . . 57
2.10 Mutação AG: executando a mutação nos 2 pontos selecionados. . . . 57
2.11 Mutação AG: alterando outras posições para manter o mesmo número
de aminoácidos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.12 Mutação AG: 2 pontos de mutação selecionados aleatoriamente. . . . 58
2.13 Mutação AG: executando a mutação nos 2 pontos selecionados. . . . 58
2.14 Mutação AG: alterando outras posições para manter o mesmo número
de aminoácidos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.15 Fluxograma da aproximação AG. . . . . . . . . . . . . . . . . . . . . 60
2.16 Algoritmo da aproximação AG. . . . . . . . . . . . . . . . . . . . . . 61
2.17 Visão estratégica computacional [65]. . . . . . . . . . . . . . . . . . . 65
2.18 Esquema de processos MPI. . . . . . . . . . . . . . . . . . . . . . . . 70
ix
LISTA DE FIGURAS
2.19 Fluxograma da aproximação AG paralelo - processo mestre. . . . . . 71
2.20 Fluxograma da aproximação AG paralelo - processo escravo. . . . . . 72
2.21 Algoritmo da aproximação AG paralelo - processo mestre. . . . . . . 73
2.22 Algoritmo da aproximação AG paralelo - processo escravo. . . . . . . 74
2.23 Funcionamento do AG Paralelo. . . . . . . . . . . . . . . . . . . . . . 75
3.1
Desempenho do AG Serial sem RE (NRE) por probabilidade de mutação. 80
3.2
Desempenho do AG Serial com RE apenas uma vez. . . . . . . . . . . 80
3.3
Desempenho do AG Serial com RE a cada 10 gerações. . . . . . . . . 81
3.4
Desempenho do AG Serial com RE. . . . . . . . . . . . . . . . . . . . 81
3.5
Desempenho do AG Serial com RE a cada 10 gerações. . . . . . . . . 83
3.6
Desempenho do AG Serial com RE. . . . . . . . . . . . . . . . . . . . 83
3.7
Índice de convergência do AG Serial com RE a cada 10 gerações. . . . 84
3.8
Índice de convergência do AG Serial com RE. . . . . . . . . . . . . . 84
3.9
Tempo de Processamento x (RE e NRE com 50% e 100% de probabilidade de mutação). Seqüências: SEQex1 e SEQex2. . . . . . . . . . 85
3.10 Tempo de Processamento x (RE e NRE com 50% e 100% de probabilidade de mutação). Seqüências: P69905 e P68871. . . . . . . . . . 86
3.11 Fitness máximo (normalizado) no processo evolutivo das seqüências:
SEQex1 e SEQex2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.12 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P69905 e P68871 (populacao1 ). . . . . . . . . . . . . . . . . . . . . . 90
3.13 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P69905 e P68871 (populacao2 ). . . . . . . . . . . . . . . . . . . . . . 90
3.14 Fitness máximo (normalizado) no processo evolutivo das seqüências:
SMHY1C e SMRT1 (populacao1 ). . . . . . . . . . . . . . . . . . . . . 91
x
LISTA DE FIGURAS
3.15 Fitness máximo (normalizado) no processo evolutivo das seqüências:
SMHY1C e SMRT1 (populacao2 ). . . . . . . . . . . . . . . . . . . . . 91
3.16 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P69905 (populacao1 ). . . . . . . . . . . . . . . . . . . . . . 92
3.17 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P69905 (populacao2 ). . . . . . . . . . . . . . . . . . . . . . 92
3.18 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P68871 (populacao1 ). . . . . . . . . . . . . . . . . . . . . . 93
3.19 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P68871 (populacao2 ). . . . . . . . . . . . . . . . . . . . . . 93
3.20 Fitness máximo (normalizado) no processo evolutivo das seqüências:
SEQex1 e SEQex2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.21 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P69905 e P68871 (populacao1 ). . . . . . . . . . . . . . . . . . . . . . 96
3.22 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P69905 e P68871 (populacao2 ). . . . . . . . . . . . . . . . . . . . . . 96
3.23 Fitness máximo (normalizado) no processo evolutivo das seqüências:
SMHY1C e SMRT1 (populacao1 ). . . . . . . . . . . . . . . . . . . . . 97
3.24 Fitness máximo (normalizado) no processo evolutivo das seqüências:
SMHY1C e SMRT1 (populacao2 ). . . . . . . . . . . . . . . . . . . . . 97
3.25 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P69905 (populacao1 ). . . . . . . . . . . . . . . . . . . . . . 98
3.26 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P69905 (populacao2 ). . . . . . . . . . . . . . . . . . . . . . 98
3.27 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P68871 (populacao1 ). . . . . . . . . . . . . . . . . . . . . . 99
3.28 Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P68871 (populacao2 ). . . . . . . . . . . . . . . . . . . . . . 99
xi
Lista de Tabelas
1.1
Cada aminoácido é formado por 3 nucleotı́deos adjacentes (códon) [71].
5
1.2
Códon (3 bases) → Aminoácido (mRNA) [72, 73, 74]. . . . . . . . .
6
1.3
Códon → Aminoácido.
1.4
A matriz de substituição BLOSUM50. Os valores logarı́tmicos das
. . . . . . . . . . . . . . . . . . . . . . . . . 15
probabilidades foram escalados e arredondados para o inteiro mais
próximo por propósitos de eficiência computacional. Os valores na
diagonal principal são de pares de resı́duos idênticos [33]. . . . . . . . 20
2.1
Subconjunto da matriz de substituição BLOSUM50. . . . . . . . . . 54
2.2
Seqüências utilizadas nas simulações
. . . . . . . . . . . . . . . . . . 62
2.3
Seqüências utilizadas nas simulações
. . . . . . . . . . . . . . . . . . 76
3.1
Tempo médio de processamento (Figuras 3.1-3.4) por probabilidade
de mutação.
3.2
Tempo médio de processamento (Figuras 3.5-3.6) por probabilidade
de mutação.
3.3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Resultados obtidos pelo algoritmo clássico de Needleman e Wunsch,
e o algoritmo genético. O algoritmo clássico não realiza E/S
(entrada/saı́da) de dispositivo, enquanto que o AG serial RE faz
E/S. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
xii
LISTA DE TABELAS
3.4
Resultados obtidos pelo algoritmo clássico de Needleman e Wunsch,
e o algoritmo genético. O algoritmo clássico realiza E/S (entrada/saı́da) de dispositivo, enquanto que o AG serial RE faz E/S. 88
3.5
Resultados obtidos pelo algoritmo clássico de Needleman e Wunsch,
e o algoritmo genético proposto. O algoritmo clássico não realiza
E/S (entrada/saı́da) de dispositivo, enquanto que o AG serial RE
faz E/S. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.6
Resultados obtidos pelo algoritmo clássico de Needleman e Wunsch,
e o algoritmo genético. O algoritmo clássico realiza E/S (entrada/saı́da) de dispositivo, enquanto que o AG serial RE faz E/S. 95
xiii
Lista de Abreviaturas
AG
ASPARAGOS
Algoritmo Genético
Asynchronous Parallel Genetic Optimization Strategy
BLAST
Basic Local Alignment Search Tool
Blosum
Block Substution Matrix
DNA
ácido desoxirribonucleico - deoxyribonucleic acid
DSM
Distributed Shared Memory
FASTA
Linux
MOSIX
MPI
MSA-EA
MRTG
NRE
NCBI
NOWs
RE
RNA
(FAST-ALL) - Fast Alignment for All Sequences
Sistema Operacional Livre
Multicomputer Operating System for Unix
Messaging Passing Interface
Multiple Sequence Aligmnent - Evolutionary Algoritm
Multi Router Traffic Grapher
Não-reestruturada
National Center for Biotechnology Information
Rede de Estações - Network of Workstation
Reestruturada
ácido ribonucleico - ribonucleic acid
xiv
Lista de Abreviaturas
SAGA
Sequence Alignment by Genetic Algorithm
SMM
Shared Memory Multiprocessor
SMP
Processamento Simétrico - Symetric MultiProcessing
Windows
mRNA
Sistema Operacional Proprietário
RNA mensageiro
xv
Glossário
NRE
RE
cluster
códon
daemon
seqüência(s) NRE (algoritmo genético não-reestruturado): que
possue(m) gaps alinhados entre os resı́duos
seqüência(s) RE (algoritmo genético reestruturado): que possue(m) gaps alinhados apenas à direita dos resı́duos
conjunto de computadores interligados
trinca de nucleotı́deos
processo de computador que provê serviços sem interatividade
direta com o usuário
gaps
buracos/lacunas num alinhamento
shell
interpretador de comandos de um sistema operacional
xvi
Introdução
As informações que compõem todo ser vivo tais como caracterı́sticas fı́sicas,
comportamento e funções especı́ficas (expressões gênicas, supressões gênicas, crescimento, etc) são armazenadas em grandes macromoléculas chamadas de ácidos
nucléicos. Em todos os organismos vivos o material genético é organizado em estruturas chamadas cromossomos e a sua quantidade depende da espécie.
A informação genética em ácidos nucléicos é especificada pela seqüência de
quatro compostos contendo nitrogênio chamados bases. Dessa forma, a estrutura
genética de todos os organismos vivos é codificada usando-se um alfabeto de quatro
letras (nucleotı́deos): adenina (A), guanina (G), timina (T) e citosina (C).
O DNA 1 consiste de duas fitas complementares entrelaçadas entre si formando
uma dupla hélice [69]. Cada fita do DNA é então um polı́mero quase sempre não
ramificado de unidades de desoxirribonucleotı́deos os quais são compostos por: um
açúcar (a desoxirribose que no RNA
2
é substituı́da pela ribose), uma base nitroge-
nada e um ou até três grupos fosfato [69].
Quando faltam partes destas estruturas, as seqüências protéicas e enzimas
responsáveis pelo funcionamento do organismo são produzidas inadequadamente ou
não são produzidas. Neste caso, seria interessante produzir seqüências com a mesma
funcionalidade, então inserı́-las dentro do organismo para compensar esta carência.
Para encontrar, estudar e reproduzir as caracterı́sticas destes genes, é necessário
saber como eles interagem. Assim, a tarefa elementar da análise de seqüências é
saber se duas seqüências biológicas estão relacionadas, e uma das formas de se obter
1
2
DNA: ácido desoxirribonucleico - deoxyribonucleic acid: cadeia de ácidos nucléicos
RNA: ácido ribonucleico - ribonucleic acid: cadeia de ácidos nucléicos
xvii
Introdução
informações é fazendo o alinhamento destas seqüências de nucleotı́deos que compõem
os genes. Normalmente isto é resolvido alinhando as seqüências, ou partes delas, e
então decidindo se aquele alinhamento é o mais provável pelo fato das seqüências
estarem relacionadas, ou por casualidade. O algoritmo de programação dinâmica
que responde esta questão é conhecido na análise de seqüências biológicas como
algoritmo de Needleman-Wunsch [81]. Esse trabalho propõe um método alternativo
baseado na técnica do Algoritmo Genético (AG) [29], para achar o alinhamento
ótimo entre duas seqüências de nucleotı́deos.
AG são algoritmos de busca e de metodologia de otimização de soluções baseados no mecanismo de seleção e genética naturais. Eles combinam sobrevivência entre estruturas de seqüências “saudáveis” com uma estrutura de troca de informação
aleatória. Assim, os AG valem-se de informações históricas para investigar um novo
ponto de busca de uma soluçõa com um esperado resultado melhorado.
Ao longo de uma evolução genética, o indivı́duo apto tem maiores chances
de produzir descendência de boa qualidade. Numa aplicação prática de AG, uma
população de indivı́duos é estabelecida e estes podem ser iniciados com valores
aleatórios, onde estes valores representam quantitativamente o grau de determinadas caracterı́sticas. O tamanho desta população varia de um problema a outro. Em
cada ciclo de operação genética, designado como processo evolutivo, uma geração
subseqüente é criada a partir dos indivı́duos da população atual. Isto somente sucede
se um grupo destes indivı́duos, geralmente chamados de pais ou uma coleção designada de conjunto de emparceiramento, for selecionado por uma rotina de seleção
especı́fica. Os genes dos pais são misturados e recombinados para a produção de
descendentes na próxima geração. É esperado que deste processo de evolução, o melhor indivı́duo criará um número maior de descendentes e assim haverá uma maior
chance de sobreviver na geração subseqüente, simulando o mecanismo natural da
sobrevivência do mais forte, a seleção natural.
Para a aplicação do AG nesse trabalho, a seqüência alinhada (indivı́duo) é descrita por um cromossomo onde este é associado a uma função objetiva (função de
aptidão - fitness function) baseada na matriz de substituição BLOSUM50 [94]. Para
cada geração alguns pares de cromossomos são escolhidos aleatoriamente para cruzaxviii
Introdução
mento (crossover), ou seja, para recombinação de informações genéticas, considerando-se uma taxa de cruzamento. O próximo passo é a mutação destes descendentes
levando-se em conta uma taxa de mutação. O último passo é a seleção dos cromossomos com os mais altos valores de aptidão (fitness). Este ciclo é repetido até que o
número de gerações seja atingido ou um valor de aptidão seja ultrapassado. Considerando que o AG já possui uma arquitetura de paralelismo intrı́nseca, não requer
esforço algum para construir um sistema computational paralelo. Especificamente,
o AG pode ser explorado completamente em sua estrutura paralela para ganhar a
velocidade exigida para usos práticos [30].
A tentativa de aplicar o AG ao problema de multialinhamento surgiu em 1993
quando Ishikawa [98] publicou um AG hı́brido que não tentava otimizar diretamente
o alinhamento mas a ordem na qual as seqüências deveriam ser alinhadas usando
programação dinâmica.
O primeiro AG capaz de trabalhar com seqüências numa maneira mais geral
foi descrito uns poucos anos depois por Notredame e Higgins [99], imediatamente
antes de um trabalho similar por Zhang [101].
Durante os anos seguintes, foram introduzidas pelo menos três novas estratégias
de multialinhamento de seqüências baseado em algorı́timos evolutivos [102, 103, 104].
No presente momento existem muitos trabalhos de AG aplicado ao multialinhamento sendo desenvolvidos com o objetivo de otimizar a eficiência e a exatidão
dos algorı́timos [96, 105, 106].
No capı́tulo 1, são abordados os conceitos básicos: da biologia relacionados
com as estruturas genéticas; dos principais algoritmos de alinhamento de seqüências
de nucleotı́deos; de AG e seu funcionamento através de exemplos; e de AG Paralelo.
No capı́tulo 2, são mostrados os métodos e dados utilizados na implementação do AG
no alinhamento de seqüências de nucleotı́deos. O capı́tulo 3 refere-se aos resultados
obtidos da aplicação do AG paralelo no alinhamento de seqüencias de nucleotı́deos
em comparação com o AG serial. Finalmente o capı́tulo 4 encerra este trabalho com
a sı́ntese dos resultados obtidos e algumas sugestões de trabalhos futuros.
xix
Capı́tulo 1
Fundamentação
1.1
Fundamentos Biológicos
Neste capı́tulo é mostrado os conceitos biológicos necessários para entender a
complexidade dos processos evolutivos envolvendo informações genéticas. Também
é descrito a estrutura, a mutação e a herança do material genético.
1.1.1
DNA: O Material Genético
A estrutura genética de todos os organismos vivos é codificada usando-se um
alfabeto de quatro letras (nucleotı́deos) divididos em dois grupos:
• purinas: adenina (A) e guanina (G);
• pirimidinas: timina (T) e citosina (C).
Por convenção as purinas são abreviadas por R e as pirimidinas por Y.
O DNA consiste de duas fitas complementares entrelaçadas entre si formando
uma dupla hélice. Cada fita do DNA é então um polı́mero quase sempre não ramificado de unidades de desoxirribonucleotı́deos os quais são compostos por: um açúcar
(a desoxirribose que no RNA é substituı́da pela ribose), uma base nitrogenada e
1
Capı́tulo 1. Fundamentação
um ou até três grupos fosfato. Para simplificar o entendimento a Figura 1.1 mostra
apenas as bases aos pares, onde a fita azul representa os açúcares e os fosfatos. A
sempre se pareia com T (no RNA T é substituı́da por U), e G sempre se pareia
com C. Mesmo que existam apenas quatro letras no alfabeto genético, uma enorme
quantidade de informações pode ser armazenada devido o tamanho das moléculas
de ácido nucléico. Por exemplo, uma cópia completa do genoma humano (toda a
informação genética em um conjunto completo de cromossomos humanos) contém 3
bilhões (3 × 109 ) [69] de pares de bases de DNA. Como cada posição numa seqüência
pode assumir 1 dos 4 pares de bases, podemos ver que o número de seqüências
possı́veis, dado n como o tamanho da seqüência, é de 4n . Sendo o genoma humano
com n = 3 × 109 , sua capacidade de armazenamento de informações é enorme e
diretamente proporcional à variabilidade de caracterı́sticas da espécie humana.
Figura 1.1: Visão bidimensional da estrutura do DNA. A informação genética dos
seres vivos é armazenada nas grandes moléculas de DNA em seqüências
de pares de bases: A:T, T:A, G:C e C:G.
2
Capı́tulo 1. Fundamentação
1.1.2
Replicação do DNA: Transmissão da Informação Genética
A informação genética de um organismo é transmitida de célula a célula durante o desenvolvimento, e de geração a geração durante a reprodução pela replicação. Dois filamentos de DNA com pareamento apropriado de bases são complementares. Assim, em termos de transmissão da informação genética para moléculas
filhas de DNA, os dois filamentos de uma dupla hélice parental podem servir como
molde para a sı́ntese de um novo filamento complementar (veja Figura 1.2). Como
resultado, as duas moléculas filhas de DNA serão idênticas à molécula de DNA
parental. Assim, a estrutura do DNA é perfeita para seu papel de transmitir a
informação genética de célula a célula e de geração a geração.
Embora o uso dos filamentos parentais de DNA como moldes para a sı́ntese
de novos filamentos complementares seja um modo simples e elegante de duplicar
a informação genética, o mecanismo pelo qual o DNA se replica é bem complexo
e vai além do objetivo desse trabalho. É dada apenas a idéia básica de como este
mecanismo funciona.
Figura 1.2: Replicação do DNA. A separação e a sı́ntese ocorrem de modo gradativo.
3
Capı́tulo 1. Fundamentação
1.1.3
Expressão Gênica: Controle do Crescimento e Desenvolvimento
A informação genética controla a morfogênese do organismo, seja ela um vı́rus,
uma bactéria, uma planta ou um animal. Esta informação genética deve ser expressa
com precisão tanto espacialmente quanto temporalmente para produzir a forma tridimensional apropriada do organismo. Nos organismos multicelulares, a informação
genética deve controlar o crescimento e a diferenciação do organismo, desde o zigoto unicelular até o adulto. Para efetuar este processo complexo, cada gene de
um organismo deve ser expresso na época apropriada e nas células apropriadas
durante o desenvolvimento. As etapas iniciais nas vias de expressão gênica são chamadas de transcrição e tradução e estão ilustradas na Figura 1.3. A transcrição e
a tradução resultam na sı́ntese de proteı́nas, as macromoléculas que catalisam as
reações metabólicas essenciais à vida e contribuem para a maior parte da estrutura dos organismos vivos. As proteı́nas são moléculas grandes e complexas que
contêm de um a vários polipeptı́dios. Os polipeptı́dios, por sua vez, são cadeias longas de subunidades pequenas repetidas chamadas aminoácidos. Vinte aminoácidos
diferentes (conforme a Tabela 1.1) são incorporados em polipeptı́dios em resposta
à formação genética armazenada nas moléculas de DNA. Os polipeptı́dios em geral
têm centenas de aminoácidos de comprimento. Com os 20 aminoácidos diferentes, os
organismos vivos podem produzir um número imenso de proteı́nas diversas. Existem
20100 seqüências diferentes, por exemplo, de um polipeptı́dio com 100 aminoácidos
de comprimento. Esta variação enorme na estrutura das proteı́nas é, em grande
parte, responsável pela enorme variabilidade dos organismos vivos.
A primeira etapa na expressão gênica, a transcrição, envolve a conversão da
informação genética armazenada sob a forma de pares de bases na dupla hélice do
DNA em seqüências de bases de uma molécula unifilamentar de RNA mensageiro
(mRNA). Catalisado por enzimas chamadas RNA polimerases, este processo ocorre
quando um filamento do DNA atua como molde para a sı́ntese de um filamento
complementar de RNA. A transcrição usa as mesmas regras do pareamento de bases
que a replicação do DNA, exceto que a base uracila (U) é incorporada no RNA na
posição em que está presente a timina no DNA. Os pontos em que a transcrição
4
Capı́tulo 1. Fundamentação
Tabela 1.1: Cada aminoácido é formado por 3 nucleotı́deos adjacentes (códon) [71].
Aminoácido
Sı́mbolo
Aminoácido Sı́mbolo
ácido aspártico
D
isoleucina
I
ácido glutâmico
E
leucina
L
alanina
A
lisina
K
arginina
R
metionina
M
asparagina
N
prolina
P
cisteı́na
C
serina
S
fenilalanina
F
tirosina
Y
glutamina
Q
treonina
T
glicina
G
triptofano
W
histidina
H
valina
V
começa e termina são determinados por seqüências de bases que são reconhecidas
por alguns dos fatores protéicos que participam do processo de transcrição.
Durante a tradução, a seqüência de bases em uma molécula de mRNA é convertida na seqüência especificada de aminoácidos em um polipeptı́dio, de acordo
com as regras do código genético [69, 71]. Cada aminoácido é especificado por um
códon, uma trinca de bases adjacentes na molécula de mRNA, conforme a Tabela
1.2. A tradução é um processo complexo que ocorre em estruturas macromoleculares citoplasmáticas chamadas ribossomos, e requer a participação de muitas outras
macromoléculas.
As etapas subseqüentes na via pelas quais um gene exerce seu efeito na morfogênese de um organismo são geralmente complexas, especialmente em eucariontes
multicelulares. As vias de expressão genética freqüentemente envolvem interações
macromoleculares, interações célula-célula e comunicação intercelular por hormônios
e outras moléculas sinalizadoras, interações de tecidos e órgãos e restrições impostas
por fatores ambientais. Os estudos atuais do controle genético do crescimento e de
desenvolvimento das plantas e animais estão produzindo novos e excitantes resultados. Muitos genes que controlam o crescimento e desenvolvimento das plantas
e animais foram recentemente identificados e caracterizados, e as vias detalhadas
5
Capı́tulo 1. Fundamentação
U
C
A
G
UU
Fenilalanina
Fenilalanina
Leucina
Leucina
UC
Serina
Serina
Serina
Serina
UA
Tirosina
Tirosina
Ocre
UG
Cisteı́na
Cisteı́na
Opala
CU
Leucina
Leucina
Leucina
Leucina
CC
Prolina
Prolina
Prolina
Prolina
CA
Histidina
Histidina
Glutamina
Glutamina
CG
Arginina
Arginina
Arginina
Arginina
AU
Isoleucina
Isoleucina
Isoleucina
AC
Treonina
Treonina
Treonina
Treonina
AA
Asparagina
Asparagina
Lisina
Lisina
AG
Serina
Serina
Arginina
Arginina
GU
Valina
Valina
Valina
Valina
GC
Alanina
Alanina
Alanina
Alanina
GA
Ácido Aspartico
Ácido Aspartico
Ácido Glutâmico
Ácido Glutâmico
GG
Glicina
Glicina
Glicina
Glicina
Âmbar
Triptofano
Metionina
Tabela 1.2: Códon (3 bases) → Aminoácido (mRNA) [72, 73, 74].
— Códon de inı́cio da cadeia polipeptı́dica (iniciador)
—
Códon de término da cadeia polipeptı́dica (finalizador)
6
Capı́tulo 1. Fundamentação
Figura 1.3: Exemplo da transcrição e tradução usando a sı́ntese da globina β humana. Durante a
transcrição (etapa 1), o filamento de DNA é um molde para a sı́ntese de um filamento
de RNA complementar. O mRNA resultante (RNA mensageiro) é transportado
para o citoplasma. No citoplasma, a seqüência de bases do mRNA é “traduzido” na
seqüência de aminoácidos formando assim o polipeptı́dio do gene de acordo com as
regras do código genético. A tradução (etapa 2) ocorre em estruturas complexas
chamadas ribossomos. A sı́ntese de globina β final requer a remoção pós-traducional
da metionina terminal (etapa 3) [69].
da morfogênese estão sendo descobertas em vários organismos modelo, tais como o
verme Caenorhabditis elegans, a mosca das frutas Drosophila melanogaster, a planta
Arabidopsis thaliana, e até o camundongo (veja as referências [75, 76, 77]).
7
Capı́tulo 1. Fundamentação
1.1.4
Mutação:
Mudanças no Material Genético com o
Tempo
Embora a informação genética deva ser transmitida de geração a geração com
considerável precisão, esta informação não permanece estática. Ocasionalmente a
informação genética sofre mudanças, ou mutações, para produzir nova variabilidade
genética que fornece a matéria-prima para a evolução. Os novos genes variantes produzidos por mutação, chamados genes mutantes, em geral resultam em organismos
com caracterı́sticas anormais.
As mutações que atingem um único sı́tio, ou mutações de ponto, em genes
individuais podem ser substituições de pares de bases ou a inserção ou remoção
de um ou alguns pares de bases contı́guos. A inserção ou remoção de um ou dois
pares de bases dentro de seqüências codificantes de um gene irá alterar o códon da
matriz de leitura (a série de trincas de bases que especifica os aminoácidos durante
a tradução) no mRNA. Assim, tais mutações são chamadas de matriz de leitura.
As mutações de matriz em geral resultam em produtos gênicos não-funcionais. Por
outro lado, as substituições de pares de bases em geral resultam na substituição de
um só aminoácido por outro aminoácido, pois cada substituição de par de bases
muda apenas um códon.
A relação entre substituições de pares de bases e de aminoácidos pode ser
melhor ilustrada com um exemplo. A anemia falciforme ocorre em humanos que
levam duas cópias do gene de uma globina β que diferem do gene normal da globina
β adulta por uma única substituição de par de bases. A substituição no gene de Hbsβ
altera o sexto aminoácido do polipeptı́dio da hemoglobina β de ácido glutâmico, nas
pessoas normais, para valina nas pessoas com anemia falciforme [78] (veja Figura
1.4). A única alteração de aminoácido na cadeia de globina β resulta nas hemácias
em forma de foice e em anemia falciforme nas pessoas com duas cópias do gene Hbsβ .
Esta alteração das hemácias não só resulta em reduzida capacidade de transporte
de oxigênio no sangue, caracterı́stica da anemia falciforme, mas também causa um
grande número de efeitos secundários, tais como prejuı́zo de crescimento, fadiga
geral, baço aumentado, dor recorrente e aumento da suscetibilidade aos micróbios e
8
Capı́tulo 1. Fundamentação
infecções virais. Assim, uma única substituição de par de bases pode ter um grande
efeito no fenótipo do organismo portador da mutação [69].
9
Capı́tulo 1. Fundamentação
Figura 1.4: Mutação: alteração em bases da seqüência de DNA [69].
10
Capı́tulo 1. Fundamentação
1.1.5
Resumo:
Pontos Importantes
A informação genética dos organismos vivos é armazenada na seqüência de
quatro bases no DNA ou, em alguns vı́rus, no RNA. O DNA é uma molécula bifilamentar. Durante a replicação do DNA, os dois filamentos separam, e cada filamento serve como um molde para a sı́ntese de um novo filamento complementar,
produzindo duas moléculas filhas idênticas de DNA. A informação genética de um
organismo controla seu crescimento e desenvolvimento por meio de vias complexas de expressão gênica. Mudanças ocasionais no material genético fornecem nova
variabilidade genética que é essencial para o processo de evolução.
11
Capı́tulo 1. Fundamentação
1.2
Alinhamento de Seqüências Par-a-Par
O princı́pio básico do alinhamento de seqüências (completo ou parcial) de gene
ou proteı́nas é saber a relação que elas possuem com outros genes ou proteı́nas. A
relação entre duas proteı́nas, considerando-se suas seqüências, sugere que elas são
homólogas 1 . Através do alinhamento de seqüências é possı́vel identificar domı́nios
ou sentidos para DNAs ou seqüências de proteı́nas que são compartilhados entre um
grupo de moléculas. Além disso, a relação das proteı́nas com organismos e entre
organismos ajuda-nos a entender melhor o sentido biológico da vida.
Para o desenvolvimento de algoritmos de alinhamento trataremos de quatro
assuntos fundamentais que são:
• Os tipos de alinhamento a serem considerados;
• O sistema de pontuação (scoring system) para classificar alinhamentos;
• O algoritmo usado para achar o alinhamento ótimo;
• Os métodos estatı́sticos usados para avaliavar a significância de uma pontuação
do alinhamento.
Também é dada uma breve justificativa para o alinhamento de proteı́nas ao
invés de nucleotı́deos na seção 1.2.1.
A Figura 1.5 mostra 3 exemplos de alinhamentos par-a-par de uma região da
seqüência protéica da globina α humana [33]. A linha central em cada alinhamento
indica posições idênticas com letras (do alfabeto de aminoácidos) e posições “similares” com um sinal de + (mais). Os pares “similares” de resı́duos (nucleotı́deos
ou aminoácidos) possuem uma pontuação positiva na matriz de substituição usada
na pontuação do alinhamento, a qual será explicada em seguida. No primeiro alinhamento (Figura 1.5°
a ) existem muitas posições onde os pares de resı́duos são
idênticos; há outras posições que são funcionalmente conservativas, tal como o par
D-E quase no final do alinhamento, representando um alinhamento de um resı́duo
1
Dois genes são homólogos se eles possuem relação com um ancestral comum [34].
12
Capı́tulo 1. Fundamentação
Figura 1.5: Três alinhamentos de seqüências para um fragmento da globina α
humana. °
a Similaridade evidente para a globina β humana. °
b
Um
alinhamento de forma estrutural razoável para a leghaemoglobina do lupos amarelo. °
c Um alinhamento espúrio com alta pontuação para uma
glutationa homólogo do nematóide S-transferase chamada F 11G11.2
[33].
de ácido aspártico com um resı́duo de ácido glutâmico, ambos negativamente carregados. A Figura 1.5°
b mostra um alinhamento biologicamente importante, essas
seqüências estão relacionadas evolutivamente, tendo a mesma forma tridimensional
e funcionam em ligações de oxigênio. Entretanto, neste caso há muito menos identidades 2 e gaps 3 (buracos ou lacunas) foram inseridos na seqüência da globina α para
manter regiões ao longo do alinhamento onde a leghaemoglobina possui resı́duos extras. A Figura 1.5°
c mostra um alinhamento com um número similar de identidades
ou mudanças conservativas. Porém, neste caso, estamos olhando um alinhamento
2
3
Identidade: até que ponto 2 seqüências (nucleotı́deos ou aminoácidos) são invariantes [34].
O termo gaps será melhor explicado na seção 1.2.2.
13
Capı́tulo 1. Fundamentação
espúrio de uma proteı́na que possui estrutura e função completamente diferentes.
Um dos desafios dos métodos de alinhamento par-a-par é de distingüir casos
como da Figura 1.5°
b e°
c.
14
Capı́tulo 1. Fundamentação
1.2.1
Justificativa para o Alinhamento Protéico
Usualmente consegue-se mais informações comparando seqüencias de proteı́nas
do que alinhando seqüências de DNAs. Há várias razões para isto. Muitas alterações
na seqüência de DNA (especialmente na terceira posição de um códon) não alteram
o aminoácido especificado (veja exemplo da Tabela 1.3). Além do mais, muitos
aminoácidos possuem propriedades biofı́sicas semelhantes (exemplo: lisina e arginina são ambos básicos). As relações importantes entre aminoácidos relacionados
(exceto sem pareamento) podem ser entendidas utilizando o sistema de pontuação
comentado na seção anterior o qual será descrito mais adiante. Nessa perspectiva
as seqüências de DNA são menos informativas [34].
Códon
Aminoácido
UCx
Serina
CUx
Leucina
CCx
Prolina
CGx
Arginina
ACx
Treonina
GUx
Valina
GCx
Alanina
GGx
Glicina
Tabela 1.3: Códon → Aminoácido.
15
Capı́tulo 1. Fundamentação
1.2.2
Gaps
O alinhamento par-a-par é útil como um caminho para identificar mutações
que ocorreram durante a evolução e assim causaram divergências de seqüências de
duas proteı́nas analisadas. As mutações mais comuns são: substituições, inserções
e remoções. Substituições ocorrem quando uma mutação resulta na alteração do
códon de um aminoácido trocando-o por outro (como mostra a Figura 1.4). Este
resulta no alinhamento de dois aminoácidos diferentes, como serina e treonina (veja
também a seção 1.1.4 sobre mutação e a Tabela 1.3). Inserções e remoções ocorrem
quando resı́duos são respectivamente adicionados ou removidos, sendo representados
por caracteres nulos (o sı́mbolo ponto ou traço: . ou -) os quais são adicionados
numa ou noutra sequência. Inserções e remoções (mesmo sendo contı́nuas e longas)
são referenciadas como gaps no alinhamento.
No alinhamento ilustrado na Figura 1.6 existem 8 gaps (desconsiderando as
extremidades). Destes, 2 ocorrem no fim das proteı́nas, 2 gaps longos estão no meio
do alinhamento, e há 4 gaps de 1 ou 2 aminoácidos. Observe também que uma das
conseqüências dos gaps é complementar cada seqüência do alinhamento deixando-as
exatamente com o mesmo tamanho.
A adição de gaps num alinhamento pode ser biologicamente relevante, porque
os gaps refletem alterações evolucionárias que ocorreram. Assim, os gaps permitem
o alinhamento completo de duas proteı́nas [34].
Figura 1.6: Alinhamento par-a-par das proteı́nas RBP (Retinol-Binding Protein)
humana e β-lactoglobulina bovina [34].
16
Capı́tulo 1. Fundamentação
1.2.3
Modelo de Pontuação: Matriz de Pontuação
A pontuação total que determina um alinhamento será a soma dos termos de
cada par alinhado dos resı́duos, mais os termos de cada gap. Esta interpretação
corresponderá ao algoritmo probabilı́stico que determina o quanto as seqüências
estão relacionadas, considerando inicialmente que elas não têm relação alguma. Informalmente, identidades e substituições conservativas são mais prováveis em alinhamentos, e assim os termos contribuem com pontuação positiva; já as mudanças
não-conservativas são menos freqüentes em alinhamentos reais, e assim os termos
contribuem com pontuação negativa [33, 27, 34, 67, 66, 68].
Usando a concepção de um esquema de pontuação aditiva onde podemos considerar mutações em locais diferentes numa seqüência por terem ocorridos independentemente (tratando um gap de qualquer tamanho como uma única mutação).
Todos os algoritmos descritos neste capı́tulo para encontrar alinhamentos ótimos
dependem do esquema de pontuação. A suposição de independência parece ser uma
aproximação razoável para o DNA e seqüencias protéicas, embora sabe-se que interações entre resı́duos possuem um papel muito crı́tico determinando a estrutura
da proteı́na.
Para obtermos a matriz precisamos da pontuação de cada par de resı́duos alinhados. Um biólogo com uma boa intuição sobre proteı́nas consegue criar um conjunto de 210 termos valorados de pontuação para todos possı́veis pares de aminoácidos 4 , mas é extremamente útil estar fundamentado numa teoria para a pontuação.
Derivaremos as pontuações da substituição a partir de um modelo probabilı́stico.
Primeiro, estabeleceremos algumas notações. Consideraremos um par de seqüências x e y, de tamanhos n e m, respectivamente. Tomemos xi como sendo o
0
0
i−esimo sı́mbolo de x e yj como sendo o j −esimo sı́mbolo de y. Estes sı́mbolos vêm
do alfabeto Λ; neste caso do DNA serão 4 bases, logo Λ = {A, G, C, T }, e no caso
de proteı́nas os vinte aminoácidos. Denotaremos sı́mbolos deste alfabeto por letras
minúsculas como a, b. Por enquanto, somente consideraremos alinhamentos globais
par-a-par sem gaps, isto é, 2 alinhamentos com tamanhos de seqüências iguais como
4
20 aminoácidos (conforme a Tabela 1.1) mais o gap dão C221 =
21!
2!(21−2)!
= 210 pares possı́veis.
17
Capı́tulo 1. Fundamentação
na Figura 1.5°
a.
Dado um par de seqüências alinhadas, deseja-se determinar uma pontuação
para o alinhamento o qual será uma medida probabilı́stica do quanto as seqüências
estão relacionadas. Isto é feito através de modelos que determinam uma probabilidade ao alinhamento em cada um dos dois casos; então consideramos a taxa (ou
razão) das duas probabilidades [33].
O modelo não-relacionado ou aleatório R é simplista [33]. Ele assume que a
letra a ocorre independentemente com alguma freqüência qa , e portanto a probabilidade das duas seqüências é justamente o produto das probabilidades de cada
aminoácido:
P (x, y|R) =
Y
qxi
i
Y
qyj .
(1.1)
j
No modelo pareado alternativo M [33], pares alinhados de resı́duos ocorrem
com uma probabilidade comum pab . Este valor pab pode ser entendido como a
probabilidade que cada um dos resı́duos a e b têm sido independentemente derivados
de algum resı́duo original desconhecido c em seu ancestral comum (c talvez seja igual
a a e/ou b). Isto fornece a probabilidade para o alinhamento completo expresso por:
P (x, y|M ) =
Y
pxi yi .
i
A taxa destas duas probabilidades é conhecida como a taxa probabilı́stica:
Q
Y pxi yy
px y
P (x, y|M )
= Q i Qi i =
.
P (x, y|R)
qxi qyi
i qxi
i qy i
i
Para chegar a um sistema de pontuação aditivo, nós tomamos o logaritmo
desta taxa, conhecido como a taxa probabilı́stica logaritmica:
S=
X
s(xi , yi ),
(1.2)
i
onde
18
Capı́tulo 1. Fundamentação
s(a, b) = log(
pab
)
qa qb
(1.3)
é a taxa de probabilidade logarı́tmica dos pares de resı́duo (a, b) ocorrendo como um
par alinhado, ao invés de um par não-alinhado.
Como procurávamos, a Equação 1.2 é uma soma das pontuações individuais
s(a, b) de cada par alinhado de resı́duos. As pontuações s(a, b) podem ser organizadas numa matriz. Para proteı́nas, por exemplo, elas formam uma matriz 20 × 20,
0
0
com s(ai , aj ) em posições i, j na matriz, onde ai , aj são os i − esimo e j − esimo
aminoácidos (em qualquer numeração). Isto é conhecido como: matriz de pontuação
ou matriz de substituição. Um exemplo de uma matriz de substituição derivada é a
matriz BLOSUM50, mostrada na Tabela 1.4. Podemos utilizar estes valores para
pontuar o alinhamento da Figura 1.5°
a e obter a pontuação 130. Outro conjunto
de matrizes de substituição muito utilizadas são as matrizes PAM (accepted point
mutation [34]).
Resumindo, BLOSUM (Blocks Substitution Matrix) refere-se a blocos de matrizes de substituição. É uma matriz de substituição na qual a pontuação de cada
posição é derivada de observações das freqüências de substituições em blocos de
alinhamentos locais em proteı́nas relacionadas. Cada matriz é moldada para uma
particular distância evolucionária. Na matriz BLOSUM62, por exemplo, o alinhamento do qual foram derivadas as pontuações foi criado usando seqüências que compartilham não mais que 62% de identidade. Seqüências mais idênticas que 62% são
representadas por uma única seqüência no alinhamento para evitar uma pesagem
excessiva na relação entre os membros familiares muito próximos [34].
Um resultado importante é que mesmo que um biologista intuitivo formule uma
matriz de substituição especı́fica, esta matriz implica em “freqüências alvo” pab as
quais estarão de acordo com a teoria mostrada anteriormente [94]. Assim, qualquer
matriz de substituição faz uma descrição sobre a probabilidade de observação dos
pares ab num alinhamento real [31]. Muitas matrizes de substituição podem ser
encontradas na referência [93].
19
Capı́tulo 1. Fundamentação
Tabela 1.4: A matriz de substituição BLOSUM50. Os valores logarı́tmicos das probabilidades foram escalados e arredondados para o inteiro mais próximo
por propósitos de eficiência computacional. Os valores na diagonal principal são de pares de resı́duos idênticos [33].
A R N D C Q E G H I L K M F
P
S T W Y V
A
5 -2 -1 -2
-1 -1 -1
-1
1
R
-2
-4
1
0 -3
0 -4 -3
3 -2 -3
-3 -1 -1
-3 -1 -3
N
-1 -1
7
2
-2
0
0
1 -3 -4
0 -2 -4
-2
1
0
-4 -2 -3
D
-2 -2
2
8
-4
0
2 -1
-1 -4 -4 -1 -4 -5
-1
0 -1
-5 -3 -4
C
-1 -4 -2 -4 13 -3 -3 -3
-3 -2 -2 -3 -2 -2
-4 -1 -1
-5 -3 -1
Q
-1
1
0
0
-3
7
2 -2
1 -3 -2
2
-1
0 -1
-1 -1 -3
E
-1
0
0
2
-3
2
6 -3
0 -4 -3
1 -2 -3
-1 -1 -1
-3 -2 -3
-2
-3 -3 -4
G
7 -1 -2
0 -3
0
0 -1
-3 -2 -3
1 -1
-3
0
8
-2 -1 -2 -1 -1 -3
0 -4
-2 -4 -4 -2 -3 -4
0
I
-1 -4 -3 -4
-2 -3 -4 -4
-4
5
2 -3
2
L
-2 -3 -4 -4
-2 -2 -3 -4
-3
2
5 -3
3
K
-1
0 -1
-3
2
M
-1 -2 -2 -4
-2
0 -2 -3
-1
2
3 -2
7
0
-3 -2 -1
-1
F
-3 -3 -4 -5
-2 -4 -3 -4
-1
0
1 -4
0
8
-4 -3 -2
1
P
-1 -3 -2 -1
-4 -1 -1 -2
-2 -3 -4 -1 -3 -4 10 -1 -1
-4 -3 -3
-1
-1 -3 -3
1 -1
1
0
T
0 -1
0 -1
1 -2
0 -1
0
0 -3 -3
0 -1 -1
0 -2
-3 -2
-2
S
0 -2 10 -4 -3
0
H
3
1
0
-2 -1 -2
-3
0
-3 -3 -1
-3 -1
4
1
-4 -3 -1
-2 -1
1
-1
-3 -2 -3
6 -2 -4
0 -1
2 -4
0
1
4 -1
0 -2 -3
-1
5
2
-4 -2 -2
-1 -1 -1 -2
-2 -1 -1 -1 -1 -2
-1
2
5
-3 -2
W -3 -3 -4 -5
-5 -1 -3 -3
-3 -3 -2 -3 -1
1
-4 -4 -3 15
2 -3
Y
-2 -1 -2 -3
-3 -1 -2 -3
4
-3 -2 -2
8 -1
V
0 -3 -3 -4
-1 -3 -3 -4
2 -1 -1 -2
-4 -4
1 -3
0
1 -1
-3 -2
0
2
-3 -1
0
5
20
Capı́tulo 1. Fundamentação
Penalidades para Gaps
O padrão de custo associado a um gap de tamanho λ é dado por uma pontuação
linear[33, 66, 68]:
φ(λ) = −λγ
(1.4)
φ(λ) = −γ − (λ − 1)δ
(1.5)
ou por uma pontuação discreta
onde γ é chamado de penalidade de gap aberto (gap-open) e δ é chamado de penalidade de extensão do gap (gap-extension). Usualmente os valores para a penalidade
δ são menores do que os valores para a penalidade γ, permitindo longas inserções e
remoções serem penalizadas menos do que deveriam se utilizássemos o custo de gap
linear. Isto é desejável quando gaps de poucos resı́duos são esperados quase tanto
como gaps de um único resı́duo [33].
As penalidades para gaps também correspondem a um modelo probabilı́stico
de alinhamento, embora isto seja menos identificado do que uma base probabilı́stica
para matrizes de substituição. Assumimos que a probabilidade de um gap ocorrer
num lugar em particular em uma dada seqüência é o produto da função f (λ) do
tamanho do gap, e a probabilidade combinada do conjunto de resı́duos inseridos
[33], logo:
P (gap) = f (λ)
Y
qxi .
(1.6)
i → posição no gap
A forma da Equação 1.6 como um produto de f (λ) com o termo qxi corresponde a
uma concepção de que o tamanho de um gap não está correlacionado com os resı́duos
que o mesmo contém [33].
Aqui, os valores naturais das probabilidades qa são as mesmas utilizadas no
modelo aleatório, porque ambos correspondem aos resı́duos independentemente nãopareados. Neste caso, quando dividimos a probabilidade desta região de acordo com
21
Capı́tulo 1. Fundamentação
o modelo aleatório para formar as taxas probabilı́sticas, os termos qxi são cancelados, assim deixamos somente o termo que depende do tamanho φ(λ) = log(f (λ));
penalidades de gap correspondem ao logaritmo da probabilidade de um gap daquele
tamanho [33].
Por outro lado, se há evidências de uma distribuição diferente de resı́duos em
regiões de gaps então deve haver pontuações de resı́duos especı́ficos para resı́duos
não-alinhados nestas regiões, isto é, os logarı́tmos de suas taxas de freqüência em
regiões de gaps contra os das regiões alinhadas. Isso pode acontecer, por exemplo,
se aminoácidos polares são mais prováveis de ocorrerem em gaps de alinhamentos
protéicos do que indicado por suas freqüências médias, porque os gaps são mais
prováveis de estar em laços (loops) na superfı́cie da estrutura protéica do que no seu
interior [33].
22
Capı́tulo 1. Fundamentação
1.2.4
Algoritmos de alinhamentos
Depois de definido o sistema de pontuação, faz-se necessário um algoritmo
para encontrar o alinhamento ótimo entre duas seqüências. Onde ambas seqüências
possuem o mesmo tamanho n, existe somente um possı́vel alinhamento global das
seqüências completas, mas o assunto se torna mais complicado uma vez que são
permitidos gaps (ou uma vez que iniciamos a observação de alinhamentos locais
entre subseqüências das duas seqüências). Existem
2n
Cn =
Ã
2n
n
!
=
(2n)!
22n
√
'
(n!)2
πn
(1.7)
possı́veis alinhamentos globais entre duas seqüências de tamanho n [33]. Computacionalmente é inviável enumerar todos estes alinhamentos, mesmo para pequenos
valores de n.
Dado um sistema de pontuação aditiva, o algoritmo para encontrar os alinhamentos ótimos da maneira que descrevemos utiliza-se da técnica de programação
dinâmica. Algoritmos de programação dinâmica são o centro da análise computacional de seqüências [33]. Todos os algoritmos descritos neste capı́tulo utilizam as
técnicas da programação dinâmica. Os algoritmos de programação dinâmica garantem encontrar o alinhamento ou conjunto de alinhamentos com a pontuação ótima
[33]. Em muitos casos os métodos heurı́sticos têm sido desenvolvidos para executar
os mesmos tipos de busca. Estes podem ser muito rápidos, mas eles fazem suposições
adicionais e perderão o melhor casamento de alguns pares de seqüências. Também
veremos um pouco sobre os métodos heurı́sticos mais adiante nesse capı́tulo.
O esquema de pontuação como taxa logaritmica da probabilidade foi adotado porque melhores alinhamentos terão pontuação maiores, assim maximizamos a
pontuação para encontrar o alinhamento ótimo. Às vezes as pontuações são determinados por outros meios e interpretadas como custos ou distâncias editadas, onde
queremos minimizar o custo do alinhamento. Ambas aproximações foram usadas
na literatura de comparação de seqüências biológicas. Algoritmos de programação
dinâmica aplicam-se tanto a um como ao outro; as diferenças são trocas triviais de
23
Capı́tulo 1. Fundamentação
mı́nimo para máximo.
Serão mostrados com maiores detalhes dois tipos básicos de alinhamentos. O
tipo de alinhamento que precisamos dependerá da origem das seqüências as quais
queremos alinhar. Para cada tipo de alinhamento há um algoritmo de programação
dinâmica um pouco diferente. Nessa seção, descreve-se somente o alinhamento para-par para pontuações de gaps lineares, com custo γ por resı́duo de gap. Modelos
de gaps mais complexos podem ser facilmente estendidos dos algoritmos descritos
nessa seção.
Para exemplificar os vários métodos de alinhamento, considere duas pequenas seqüências de aminoácido, x = HEAGAW GHEE e y = P AW HEAE. Para
pontuar o alinhamento, utilizaremos a matriz de pontuação BLOSUM50 (descrita na
seção 1.2.3), e um custo de gap por resı́duo não-alinhado de γ
= −8.
A Figura 1.7 mostra uma matriz pij de pontuação local p(xi , yj ) usada para alinhar cada par de resı́duo das duas seqüências exemplo. Pares de resı́duos idênticos
ou conservados estão destacados em negrito. Conseqüentemente, a meta de um
algoritmo de alinhamento é incorporar o máximo destes pares positivamente pontuados quanto possı́vel dentro do alinhamento, enquanto minimiza o custo de pares
de resı́duos não conservados, gaps, e outras restrições.
H
E
A
P
-2 -1 -1
A
-2 -1
W
-3 -3 -3
H
10
E
0
A
E
0 -2
A
W
G
H
E
E
-2 -1
-4
-2
-2
-1
-1
-3
0
-2
-1
-1
15 -3
-3
-3
-3
0
5
-3 -3
-2
-2
-3 -2
10
0
0
6 -1 -3
-1
-3 -3
0
6
6
0
5
-3
0
-2
-1
-1
6 -1 -3
-1
-3 -3
0
6
6
-2 -1
0
5
G
5
Figura 1.7: Duas seqüências usadas para ilustrar os algoritmos de programação
dinâmica. Elas estão arranjadas por par de resı́duos alinhados de forma
a mostrar os valores correspondentes da matriz BLOSUM50. As pontuações positivas estão em negrito.
24
Capı́tulo 1. Fundamentação
Alinhamento Global:
Algoritmo de Needleman e Wunsch
Considere primeiramente o alinhamento global ótimo entre duas seqüências
permitindo gaps. O algoritmo de programação dinâmica para resolver este problema
é conhecido na análise de seqüência biológica como o algoritmo de Needleman e
Wunsch [81], porém a versão mais eficiente descrita a seguir é a apresentada por
Gotoh [91].
A idéia é construir um alinhamento ótimo usando soluções anteriores do alinhamento ótimo ou subseqüências menores. Construı́mos uma matriz F com um
ı́ndice para cada seqüência, i e j, onde o valor F (i, j) é a pontuação do melhor
alinhamento entre o segmento inicial x1...i de x1 até xi e o segmento inicial y1...j
de y1 até yj . Podemos construir F (i, j) recursivamente. Nós começamos iniciando
F (0, 0) = 0, depois preenchemos a matriz vindo do canto superior esquerdo da matriz até o canto inferior direito. Se F (i − 1, j − 1), F (i − 1, j) e F (i, j − 1) são
conhecidos, é possı́vel calcular F (i, j). Existem três possı́veis caminhos de se obter
a melhor pontuação para F (i, j) de um alinhamento até xi , yj : xi pode ser alinhado
a yj , neste caso F (i, j) = F (i − 1, j − 1) + s(xi , yj ); ou xi é alinhado com um
gap, neste caso F (i, j) = F (i − 1, j) − γ; ou yj é alinhado com um gap, neste caso
F (i, j) = F (i, j − 1) − γ (veja a Figura 1.8). A melhor pontuação até (i, j) será o
maior valor destas três opções. Então, teremos



 F (i − 1, j − 1) + s(xi , yi ),
F (i, j) = max F (i − 1, j) − γ,


 F (i, j − 1) − γ.
(1.8)
Esta equação é aplicada repetidamente para preencher valores na matriz F (i, j),
calculando os valores do canto inferior direito de cada quadrado de quatro células obtidos de um dos três valores (superior esquerdo, esquerdo ou acima) como mostrado
na Figura 1.9.
25
Capı́tulo 1. Fundamentação
I
G
A
xi
A
I
G
L
G
V
yj
G
V
yj
A
xi
G A
xi
S
G
L
V
yj
Figura 1.8: Três caminhos possı́veis para o alinhamento até (i, j): xi alinhado com
yj , xi alinhado com um gap e yj alinhado com um gap.
...
...
...
··
·
..
.
..
.
F (i − 1, j − 1)
F (i, j − 1)
+s(xi , yi )
−γ
F (i − 1, j)
−γ
..
.
Z
Z
~ ?
Z
- F (i, j)
..
.
··
·
...
...
...
Figura 1.9: F (i, j) obtido a partir dos três valores possı́veis.
Conforme preenchemos os valores na F (i, j), também deixamos um ponteiro
em cada célula apontando para a célula de onde F (i, j) foi derivado, como mostrado
no exemplo completo da matriz da programação dinâmica na Figura 1.10.
Para que possamos completar nossa especificação do algoritmo, algumas condições
de limite devem ser consideradas. Na primeira linha da matriz, onde j = 0, os valores F (i, j −1) e F (i−1, j −1) não são definidos, assim os valores F (i, 0) precisam ser
especialmente tratados. Os valores F (i, 0) representam alinhamentos de um prefixo
de x para todos os gaps em y, assim nós podemos definir F (i, 0) = −i γ. Da mesma
forma, na primeira coluna da matriz, definimos F (0, j) = −j γ.
O valor na célula final da matriz, F (i = n, j = m), é por definição a melhor
pontuação de um alinhamento de x1...n para com y1..m , o qual é o que nós queremos: o valor da melhor pontuação do melhor alinhamento global de x para com y.
Para encontrar o próprio alinhamento, precisamos encontrar o caminho das escolhas
(Equação 1.8) que conduziu-nos a este valor final. O procedimento que faz isto é
conhecido como um traceback (traço de volta). Ele trabalha construindo o alinhamento invertido, iniciando da célula final e seguindo o ponteiro que armazenamos
quando construı́mos a matriz. Em cada passo no processo de traceback, voltamos
26
Capı́tulo 1. Fundamentação
da célula corrente (i, j) para uma das células (i − 1, j − 1), (i − 1, j) ou (i, j − 1) da
qual o valor F (i, j) foi derivado. Ao mesmo tempo, adicionamos um par de sı́mbolos
na frente do alinhamento corrente:



 (xi , yj ), se o passo foi para (i − 1, j − 1)
,
(χi , ψj ) =
(xi , ‘ ), se o passo foi para (i − 1, j)

 ,

(‘ , yj ), se o passo foi para (i, j − 1)
No fim alcançaremos o inı́cio da matriz, F (i = 0, j = 0). Note que χi e ψj são as
seqüências alinhadas de trás para frente, isto é, χn..1 e ψm..j é o alinhamento que
procuramos (Figura 1.11). Observe também que o processo do traceback descrito
aqui encontrou justamente o alinhamento com pontuação ótima, mas se houvessem
dois valores ótimos iguais seria feita uma escolha arbitrária entre as duas opções.
O algoritmo de traceback pode ser facilmente modificado de forma a obter
mais de um alinhamento ótimo, caso exista.
0
P
A
W
H
E
A
E
-8
↑
-16
↑
-24
↑
-32
↑
-40
↑
-48
↑
-56
H
⇐= -8 ⇐=
-2
↑ -10
↑
-18
-14
↑ -22
↑
-30
↑
-38
E
-16 ←
-9
-3
↑ -11
-18
A
G
-24 ← -32 ←
-17 ⇐= -25
-4 ← -12
-6
-7
-13
-8
↑ -8
-16
-16
↑ -16
-3
-11
↑
↑ -24
-11
-6
A
W
G
H
E
E
-40 ← -48 ← -56 ← -64 ← -72 ← -80
-33 ← -42 ← -49 ← -57
-65
-73
-20 ← -28 ←
-15
-5 ⇐=
↑ -9
-13
-9
-12
-11
-12
-12
-14
-36 ← -44 ← -52 ← -60
-13 ← -21 ←
-7
-3 ←
↑ -15
-7
↑
-12
-15
-15
-12
-29 ← -37
-11 ←
3
⇑ -5
-9
-19
-5
2
1
Figura 1.10: Matriz da programação dinâmica global. As setas mais largas, apontando para valores (em negrito) do alinhamento ótimo, representam os
ponteiros do traceback. O valor no canto inferior direito da matriz é a
pontuação total do alinhamento ótimo.
Resumidamente, o algoritmo trabalha somando a pontuação das partes inde27
Capı́tulo 1. Fundamentação
pendentes, assim a melhor pontuação até um ponto z no alinhamento será a melhor
pontuação até um passo antes deste ponto z, mais o incremento da pontuação do
novo passo. Além disso, a ordem de complexidade do algoritmo é de O(nm), tanto
para o tempo computacional quanto para o requisito de armazenagem de dados.
Considerado um algoritmo um pouco lento (quando n ≈ m, O(n2 )), é utilizado
para seqüências não muito longas [33]. Uma versão paralelizada deste algoritmo é
descrita na referência [35].
H
–
E
–
A
P
G
–
A
A
W
W
G
–
H
H
E
E
–
A
E
E
Figura 1.11: Alinhamento obtido a partir do processo de traceback da Figura 1.10 e
posterior inversão das seqüências χ e ψ.
28
Capı́tulo 1. Fundamentação
Alinhamento Local: Algoritmo de Smith e Waterman
Até agora, assumimos quais seqüências queremos alinhar e procuramos pelo
melhor casamento entre elas. Uma situação muito mais comum é procurar pelo
melhor alinhamento entre subseqüências de x e y. Isto aparece, por exemplo, quando
suspeita-se que duas seqüências protéicas compartilham um domı́nio comum, ou
quando comparamos seções estendidas da seqüência genômica do DNA. É também
usualmente a mais sensitiva maneira de detectar similaridade quando comparamos
duas seqüências altamente divergentes, até quando elas possivelmente compartilham
uma origem evolucionária ao longo de todo comprimento delas. Isto ocorre porque
em tais casos somente partes da seqüência foram sujeitas a intensa seleção para
preservar similaridade detectável; o resto da seqüência terá acumulado tanto ruı́do
por mutação que não será mais alinhável. O alinhamento de subseqüências x e y
com pontuação mais elevada é chamado de melhor alinhamento local.
O algoritmo para encontrar o alinhamento local ótimo está relacionado com
o algoritmo de alinhamento global, descrito na seção anterior. Há duas diferenças.
Primeira, em cada célula na matriz, uma possibilidade extra é adicionada a Equação
1.8, permitindo F (i, j) = 0 se todas as outras opções possuem valores menores do
que 0:


0,



 F (i − 1, j − 1) + s(x , y ),
i i
F (i, j) = max

F (i − 1, j) − γ,




F (i, j − 1) − γ.
(1.9)
Adotar a opção 0 corresponde iniciar um novo alinhamento. Se o melhor alinhamento
até um ponto qualquer z tem uma pontuação negativa, é melhor iniciar um novo ao
invés de continuar o atual. Observe que uma conseqüência do 0 é que a primeira
linha e primeira coluna são preenchidos com 0s de forma que
F (i, j = 0) = 0
ao invés de
F (i = 0, j) = −j γ
e
F (i = 0, j) = 0
F (i, j = 0) = −i γ
e
como
no alinhamento global.
A segunda diferença é que agora um alinhamento pode terminar em qualquer
29
Capı́tulo 1. Fundamentação
0
H
0
E
0
A
0
G
0
A
0
W
0
G
0
H
0
E
0
E
0
P 0
0
0
0
0
0
0
0
0
0
0
A 0
0
0
5
0
0
0
0
0
0
-
5
W 0
0
0
0
2
0
H 0
E 0
A 0
E 0
10 ← 2
0
0
0
↑ 2
16 ← 8
0
0
↑ 0
8
21 ← 13
5
↑ 0
6
13
18
12
20 ⇐= 12
4
0
0
↑ 12
18
22 ← 14 ← 6
↑
↑ 4
10
18
28
20
↑
↑ 0
4
10
20
27
← 4
0
4
16
26
Figura 1.12: Matriz da programação dinâmica local. Alinhamento ótimo local com
pontuação 28.
A
A
W
W
G
–
H
H
E
E
Figura 1.13: Alinhamento obtido a partir do processo de traceback da Figura 1.12 e
posterior inversão das seqüências χ e ψ.
lugar da matriz, ao invés de levar o valor no canto inferior direito F (i = n, j = m).
Para encontrar a melhor pontuação, devemos procurar pelo maior valor na matriz
e iniciar o traceback a partir daı́. O traceback termina quando é encontrado uma
célula com o valor 0 o qual representa o inı́cio do alinhamento. Um exemplo é dado
pelas Figuras 1.12 e 1.13. Neste caso o alinhamento local é um subconjunto do
alinhamento global, mas nem sempre é o caso.
A versão local do algoritmo de programação dinâmica para o alinhamento de
seqüências foi desenvolvido por volta de 1980. Ele é conhecido como algoritmo de
Smith e Waterman [83]. Gotoh [91] formulou a eficiente versão discreta de custo de
gap que é normalmente usada.
30
Capı́tulo 1. Fundamentação
Pareamentos Repetidos, Sobrepostos e Condições Hı́bridas
Apresentaremos a seguir, de forma superficial, três outras metodologias envolvidas no alinhamento de seqüências. A primeira refere-se quando precisamos encontrar pareamentos repetidos ao invés de apenas o melhor pareamento local como
visto anteriormente. Se uma ou ambas seqüencias são longas é muito provável que
existam muitos diferentes alinhamento locais com pontuação significante, e em muitas casos, estes são muito importantes. Um exemplo seria onde há muitas cópias
de um domı́nio ou motif
5
repetido numa proteı́na. Esse problema foi resolvido por
Waterman e Eggert [88, 90].
A segunda refere-se ao pareamento sobreposto, apropriada quando supomos
que uma seqüência contém a outra, ou que elas estão sobrepostas. Isto frequentemente ocorre quando fazemos comparações entre fragmentos de seqüências de DNA
genômico, ou em grandes seqüências cromossomais. Vários tipos diferentes de sobreposição podem ocorrer (Figura 1.14). Esta metodologia surgiu da adaptação do
algoritmo global [84].
x
x
y
y
Figura 1.14: Tipos de sobreposição dos pares de seqüência x e y.
A terceira refere-se ao pareamento com condições hı́bridas, a qual mostra claramente que é possı́vel formular uma gama de variedades diferentes do algoritmo
de programação dinâmica para o alinhamento de seqüências. Todos os métodos de
alinhamento dados anteriormente são expressos em termos da matriz F (i, j), com
diversas e diferentes condições de limites e regras de repetição para gaps. Podemos obter algoritmos hı́bridos a partir de um modelo comum. Uma aplicação, por
exemplo, seria uma seqüência repetitiva y que tende a ser encontrada em cópias
seguidas não separadas por gaps. Outro exemplo, poderia ser quando observamos o
pareamento que começa no inı́cio de ambas seqüências e termina em qualquer ponto.
5
motif = tema, motivo, idéia principal, assunto principal
31
Capı́tulo 1. Fundamentação
Existem modelos mais complexos onde a programação dinâmica atua como:
• alinhamentos com pontuações de gaps discretas;
• autômatos de estado finito;
e também algoritmos de alinhamento heurı́sticos como as versões rápidas do algoritmo de Smith e Waterman:
• BLAST - Basic Local Alignment Search Tool [79];
• FASTA (FAST-ALL) - Fast Alignment for All Sequences [80].
Quando fazemos uma busca de similariedade devemos sempre considerar quais
tipos de pareamento estamos observando, e utilizar o algoritmo mais apropriado.
Na prática, há boas implementações disponı́veis para poucos casos padrões, e é mais
conveniente utilizá-los e depois pós-processar os pareamentos resultantes.
Alguns dos problemas computacionais são abordados nas referências [33, 89].
32
Capı́tulo 1. Fundamentação
1.2.5
Significância das Pontuações
Agora que sabemos como encontrar um alinhamento ótimo, como podemos
avaliar a significância de sua pontuação? Quer dizer, como decidimos se o alinhamento é biologicamente significante dando evidência à homologia, ou se é o melhor
alinhamento entre duas seqüências completamente desassociadas? Existem duas
aproximações possı́veis:
Bayesiana baseada na comparação de modelos diferentes. Um exemplo importante
é quando procuramos por um grande número de diferentes alinhamentos para
um pareamento significante. Isto é uma situação tı́pica de procura em banco
de dados;
Clássica baseada na tradicional aproximação estatı́stica de calcular a chance da
pontuação de um pareamento ser maior que um valor observado, assumindo
um modelo nulo, onde as seqüências subjacentes estão desassociadas. A Aproximação Clássica é particularmente útil administrando dados grandes com
dependências múltiplas onde as regras estão claras e explı́citas.
Nesta aproximação, olhamos a distribuição de N emparelhamentos pontuados como seqüências aleatórias independentes. Se é pequena a probabilidade
deste máximo ser maior que a melhor pontuação, então a observação é considerada significante.
No caso simples de um alinhamento sem gaps, a pontuação de um emparelhamento para uma seqüência aleatória é a soma de muitas variáveis aleatórias
semelhantes, sendo aproximada por uma distribuição normal. A distribuição
assintótica do máximo Mn de uma série de N variáveis aleatórias normais
independentes são conhecidas, e tem a forma:
λ(x−µ)
P (Mn ≤ x) ' e−KN e
.
(1.10)
Esta forma de distribuição limitada é chamada de Distribuição de Valor Extremo (DVE). Nós podemos usar a Equação 1.10 para calcular a probabilidade
do melhor emparelhamento ter maior pontuação que a máxima observada S,
33
Capı́tulo 1. Fundamentação
a partir da busca de um número grande de N seqüências não-relacionadas. Se
esta pontuação é menor que alguns valores pequenos, como 0.05 ou 0.01, então
podemos concluir que é improvável que a seqüência que dá origem à pontuação
máxima está não-relacionada, ou seja, é provável que tenha relação [33].
Com um estudo mais detalhado destas aproximações poderemos avaliar melhor a pontuação esperada num determinado alinhamento aplicando os algoritmos
descritos anteriormente [82, 85, 86, 87, 92, 26].
Algumas referências de trabalhos de análises estatı́sticas e análises de seqüências
biológicas são dadas em [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 28, 25].
34
Capı́tulo 1. Fundamentação
1.3
Algoritmos Genéticos
Neste capı́tulo será tratada a definição do que vem a ser Algoritmos Genéticos
e também de como pode ser aplicado no alinhamento de seqüências biológicas.
1.3.1
Introdução
Algoritmos Genéticos (AG) são algoritmos de busca e de metodologia de otimização de soluções baseados no mecanismo de seleção e genética naturais. Eles
combinam sobrevivência entre estruturas de seqüências “saudáveis” com uma estrutura de troca de informação aleatória. Estes algoritmos também se valem de
informações históricas para investigar um novo ponto de busca com um esperado
resultado melhorado.
Se por um lado um sistema artificial é mais robusto, por outro a sua flexibilidade e readequação é muito trabalhosa. A eficiência e a eficácia necessários
podem ser adquiridos simplesmente adaptando o AG aos sistemas, e se isso for feito
de maneira a alcançar altos nı́veis de adaptação, estes sistemas poderão executar
funções mais complexas. Caracterı́sticas como: auto-reparo, autodirecionamento
e reprodução são as regras nos sistemas biológicos, considerando que elas apenas
existam nos sistemas artificiais mais sofisticados.
Os AG são teoricamente e empiricamente comprovados para prover procura
robusta em universos complexos. O primeiro trabalho sobre o tópico foi Adaptation
in Natural and Artificial Systems [29]. Muitos artigos e dissertações estabeleceram
a validade das técnicas em funções de otimização e aplicações de controle [37, 38].
Na referência [30] deste trabalho encontra-se um endereço na Internet para um laboratório que exemplifica bem esse fato, onde 1000 computadores estão ligados e
executando AG paralelamente para resolver inúmeros problemas. As razões por trás
do número crescente de aplicações estão claras. Estes algoritmos são computacionalmente simples e ainda sim poderosos na sua busca por melhoria. Além disso, eles não
são fundamentalmente limitados por suposições restritivas sobre o universo de busca
(suposições concernentes à continuidade, existência de derivadas, unimodalidade, e
35
Capı́tulo 1. Fundamentação
outros assuntos).
Muitos trabalhos atuais utilizando AG no problema de alinhamento estão voltado para o multialinhamento [95, 96, 107, 108].
A tentativa de aplicar o AG ao problema de multialinhamento surgiu em 1993
quando Ishikawa [98] publicou um AG hı́brido que não tentava otimizar diretamente
o alinhamento mas a ordem na qual as seqüências deveriam ser alinhadas usando
programação dinâmica. Claro, isto limita o algoritmo à função objetiva que pode ser
usada com programação dinâmica. Mesmo que, os resultados obtidos daquele modo
estavam fomentando o desenvolvimento do uso de AGs em análise de seqüências
biológicas [97].
O primeiro AG capaz de trabalhar com seqüências numa maneira mais geral foi
descrito uns poucos anos depois por Notredame e Higgins [99], imediatamente antes
de um trabalho similar por Zhang [101]. Neste dois AGs, uma população é feita
de multialinhamentos completos de seqüências e os operadores têm acesso direto às
seqüências alinhadas: eles inserem e movimentam gaps numa maneira aleatória ou
semi-aleatória.
Durante os anos seguintes, foram introduzidas pelo menos três novas estratégias
de multialinhamento de seqüências baseado em algoritmos evolutivos [102, 103, 104].
Cada um destes conta com um princı́pio similar ao SAGA: uma população de alinhamentos múltiplos desenvolvem-se por seleção, combinação e mutação. A população
é feita de alinhamentos e as mutações programas de processamento strings
6
que
misturam os gaps usando modelos complexos. A diferença principal entre o SAGA
e estes algoritmos recentes tem sido o projeto de melhores operadores de mutação
que melhoram a eficiência e a exatidão dos algoritmos. O SAGA utiliza um esquema de escalonamento automático que controla o uso de 22 operadores diferentes
para combinar alinhamentos ou mutações entre suas gerações. Quando usado para
aperfeiçoar as somas bem conhecidas de funções objetivas, o SAGA executa melhor do que alguns dos pacotes alternativos extensamente utilizados. Isto é devido
à habilidade de alcançar uma solução ótima e também à precisão do alinhamento
6
String (em informática): série de caracteres que são processados como uma unidade de in-
formação.
36
Capı́tulo 1. Fundamentação
comparando-o com alinhamentos de referência baseados em seqüências de estruturas terciárias conhecidas. A principal atração da aproximação é a habilidade de
aperfeiçoar qualquer função objetiva aplicada a ela [99].
Outros trabalhos interessantes podem ser encontrados nas referências: [100,
110, 109, 106, 105, 111, 112, 113, 114].
37
Capı́tulo 1. Fundamentação
1.3.2
Definição e Funcionamento
Num ambiente competitivo onde os indivı́duos mais fortes são os prováveis
vencedores, é possı́vel determinar o melhor através de critérios especı́ficos.
Em AG, presume-se que a solução potencial de qualquer problema é um indivı́duo que pode ser representado por um conjunto de parâmetros. Estes parâmetros
são vistos como um gene de um cromossomo e podem ser estruturados por uma
seqüência (string) com valores binários. Um valor, conhecido por valor de aptidão
(obtido através de uma função de aptidão7 ), é usado para refletir o grau de “qualidade” do cromossomo utilizando-se de critérios especı́ficos [45]. Por exemplo, num
problema envolvendo máximos e mı́nimos, é possı́vel encontrar uma solução ótima
onde
cada
ponto
(Xi , f (Xi ))
é
interpretado
em
AG
como
sendo
0
(i − esimo indivíduo, valor da avaliação dos critérios).
Na evolução genética, processo iterativo do AG, o indivı́duo mais apto (com
maior fitness) tem a tendência a gerar como frutos, descendentes de boa qualidade, melhorando a cada geração o material genético da população (conjunto de
indivı́duos). Numa aplicação prática de AG, precisa-se estabelecer uma população
de indivı́duos e estes podem ser iniciados com valores aleatórios. O tamanho da
população varia de um problema a outro ainda que algumas linhas de direção sejam
dadas em [39]. Em cada ciclo de operação genética, uma geração subseqüente é
criada a partir dos cromossomos da população atual. Estes podem somente suceder
se um grupo destes cromossomos, chamados “pais”, é selecionado por uma rotina
de seleção especı́fica (estratégia de seleção). Os genes dos pais são misturados e recombinados para a produção de descendentes na próxima geração. A partir disto, é
esperado, deste processo evolutivo (manipulação de genes), que o “melhor” cromossomo criará o maior número de descendentes, e assim obtenha uma grande chance de
sobrevivência nas gerações subseqüentes, simulando o mecanismo da seleção natural.
O ciclo de evolução é repetido até um determinado critério de término. Este
critério pode ser o número de ciclos de evolução, ou a soma de variações de indivı́duos
entre gerações diferentes, ou um valor de fitness pré-definido.
7
ou valor fitness: obtido através de uma função fitness
38
Capı́tulo 1. Fundamentação
Duas operações fundamentais são utilizadas para facilitar o ciclo de evolução:
cruzamento (crossover) e mutação, embora a rotina de seleção (ou reprodução) possa
ser considerada como outra operação.
A seguir, na Figura 1.15, é exemplificado o mecanismo de cruzamento entre
dois cromossomos em apenas uma posição. Nesta operação, uma posição ao longo da
seqüência é fixado aleatoriamente para cruzamento e as partes dos dois cromossomos
além deste ponto serão trocadas para formar a descendência como à direita na Figura
1.15. Uma variável, chamada de probabilidade de cruzamento pc , é utilizada para
controlar a freqüência de ocorrência do cruzamento, que na prática tem um valor
tı́pico entre 60% e 100% [32] 8 .
Figura 1.15: Cruzamento de dois cromossomos em apenas uma posição.
Já na mutação (Figuras 1.16 e 1.17), ela se aplica individualmente a cada
descendência após o cruzamento. Nesse mecanismo altera-se aleatoriamente uma
posição da seqüência com uma probabilidade de mutação pm que normalmente está
abaixo de 1% [32] 9 . Esta probabilidade pm é responsável pelo aumento da variabilidade da população. Tratando dos extremos, se utilizarmos um valor muito baixo
para pm significa que queremos uma busca mais refinada, ou seja, convergência; já
um valor muito alto para pm , sugere uma busca aleatória.
Na implementação do AG, a escolha de pm e pc , assim como os outros parâmetros de controle pode ser um problema de otimização não-linear difı́cil de ser resol8
9
Sabe-se também que na genética natural pode haver mais de um ponto de cruzamento [71].
Da mesma forma que no cruzamento, pode haver mais de um ponto de mutação [71].
39
Capı́tulo 1. Fundamentação
Figura 1.16: Mutação em uma posição do cromossomo biológico.
Figura 1.17: Mutação em uma posição do cromossomo binário.
vido. Além disso, a configuração deles é extremamente dependente sob a natureza
da função de aptidão [32]. DeJong, Spears e Grefenstette [40, 41] sugerem valores
para pm e pc conforme o tamanho da população, mas intuitivamente podemos pensar, numa aplicação simples de maximização ou minimização, da seguinte forma:
quando a população é relativamente pequena, de tamanho 30, utilizamos taxas pm e
pc maiores, 1% e 90% respectivamente; e quando a população é grande, de tamanho
100, utilizamos pm e pc menores, 0.1% e 60% respectivamente.
Quando a homogeneidade (falta de diversidade/heterogeneidade) é um problema, aumenta-se o valor de pm para que no processo crie-se divergências nas
gerações futuras. Uma outra questão importante é a escolha do tamanho da população, se escolhermos um tamanho muito pequeno para a população, esta será “pobre” devido à quantidade insuficiente de amostras (indivı́duos); já uma população
grande conterá representantes de um vasto número de hiperplanos. Um dos resultados da utilização de uma grande população é a não convergência prematura para
uma solução sub-ótima (ótimo local). Por outro lado, o processo fica lento, pois há
mais processamento por gerações, tornando a convergência mais lenta [5].
A Figura 1.18 é um fluxograma de um algoritmo genético que começa definindo
um cromossomo como uma seqüência de parâmetros valorados a serem aperfeiçoados.
40
Capı́tulo 1. Fundamentação
Já a Figura 1.19 é um esqueleto do algoritmo genético básico do ponto de vista da
implementação.
Figura 1.18: Fluxograma para exemplificar o algoritmo genético.
41
Capı́tulo 1. Fundamentação
Algoritmo Genético ( . . . ) {
// Iniciando as variáveis
t ← 0;
terminado ← falso;
P ← Objeto Populaç~
ao(...);
// Gerando a populaç~
ao inicial, usualmente com valores aleatórios
P.inicia populacao();
// Calcula o fitness da populaç~
ao inicial
P.calc fitness();
// Ciclo evolutivo
enquanto n~
ao terminado faça
// seleciona uma sub-populaç~
ao para produç~
ao de descententes
P’ ← P.selecionaPais();
// recombina os "genes" dos pais selecionados
P’.recombina();
// perturbar a populaç~
ao emparelhada estocasticamente
P’.muta();
// calcula os novos fitness
P’.calc fitness();
// seleciona os sobreviventes através do fitness
P.adicione(P’);
P.sobreviventes();
// incrementa o contador
t ← t + 1;
// verifica término
terminado ← (t = número ciclos máximos) ou
(P.melhor fitness() >= fitness máximo) ou (...);
fim enquanto;
}
Figura 1.19: Estrutura convencional do algoritmo genético.
42
Capı́tulo 1. Fundamentação
1.3.3
Algoritmo Genético Paralelo
Para melhorar a eficiência do AG a fim de aplicá-lo a problemas mais complexos ou que exigem um processamento computacional maior, é necessário explorar e
aproveitar suas caracterı́sticas intrı́nsecas. Como visto anteriormente, a técnica do
AG é fácil de entender e de utilizar, e em poucos casos, é necessário desenvolvê-lo a
partir de formulações matemáticas complexas [32]. Estas não são as únicas razões
que fazem do AG uma técnica de otimização poderosa, ela também é atrativa pelas
seguintes caracterı́sticas:
• Fácil implementação em arquitetura paralela;
• Direcionado à problemas multiobjetivos;
• Capaz de tratar problemas com restrições e regras;
• Podem resolver problemas multimodelos, não-diferenciáveis, não-contı́nuos ou
até mesmo NP-completa
10
[42].
Como o AG possui arquitetura intrı́nseca paralela [32], não há um esforço extra
para construir um modelo computacional paralelo.
Dependendo da maneira em que o paralelismo é explorado na estrutura populacional e mecanismo de recombinação do AG, podemos classificar os métodos
11
como: Global, Migração e Difusão. Alguns trabalhos relacionados ao AG paralelo:
[56, 57].
10
Problemas NP-completa: são os que têm a questão da complexidade ou tratabilidade não
resolvida, pois não se sabe se existe ou não algoritmo polinomial que o resolva [2].
11
Existe um número de métodos paralelos baseados em AG para melhorar a velocidade computacional [43, 104].
43
Capı́tulo 1. Fundamentação
AG Global
Pode ser implementado num computador com múltiplos processadores e memória compartilhada (SMM - Shared Memory Multiprocessor) ou num computador
com memória distribuı́da (DSM - Distributed Shared Memory). Num SMM, os
cromossomos são armazenados na memória compartilhada e cada processo acessa
um cromossomo e devolve seu valor de aptidão sem qualquer conflito. Obviamente
é necessário uma sincronização entre as gerações e também um balanceamento computacional para melhor utilização de cada processador.
Num DSM, a população pode ser armazenada em um único processador para
simplificar
as
operações
genéticas.
Este
é
baseado
na
arquitetura
fazendeiro-trabalhador/mestre-escravo (farmer-worker/master-slave), como mostrado na Figura 1.20. O processador fazendeiro (PF) é responsável por enviar cromossomos aos processadores trabalhadores (PT) que avaliam a aptidão destes cromossomos. O PF também coleta seus resultados e aplica as operações genéticas para a
criação da próxima geração. Uma desvantagem deste método é que os PTs esperam
enquanto o PF está executando seu trabalho [45, 46, 47].
AG Fazendeiro
Seleção
Agregação do Fitness
:
»»»
»»»
»
»»
»
9»
6
?
Trabalhador 1
Trabalhador 2
Recombinação
Recombinação
Mutação
Mutação
Cálculo do Fitness
Cálculo do Fitness
yX
X
XXX
XXX
XXX
z
Trabalhador k
s s s
Recombinação
Mutação
Cálculo do Fitness
Figura 1.20: AG Global em Arquitetura DSM.
44
Capı́tulo 1. Fundamentação
AG Migração
Outro mecanismo de processamento paralelo é o AG Migração (Coarse Grained Parallel GA), que divide a população em subpopulações as quais são tratadas
como unidades separadas de procriação. Neste processo, indivı́duos com bom material genético migram entre subpopulações de tempo em tempo com o propósito de
aumentar a heterogeneidade. Um pseudo-código é mostrado na Figura 1.21
Em cada nódo (AG):
enquanto n~
ao terminado faça
// Seqü^
encial:
Seleç~
ao;
Reproduç~
ao;
Cálculo Fitness;
// Paralelo:
Enviar Emigrantes;
Receber Imigrantes;
fim enquanto;
Figura 1.21: Pseudo-código do AG Migração [32].
As Figuras 1.22,1.23 e 1.24 mostram diferentes topologias de migração. A Figura 1.22 mostra a topologia de migração em anel, onde indivı́duos são transferidos
entre subpopulações adjacentes unidirecionalmente. A Figura 1.23 mostra a topologia de migração da vizinhança, onde a migração pode ser feita entre subpopulações
vizinhas mais próximas de maneira bidirecional. Por fim, a Figura 1.24 descreve uma
migração irrestrita, onde uma sub-população migra para outra. Alguns parâmetros
devem ser analisados para se obter uma estratégia de seleção que torne o processo
de migração bem-sucedido. São eles:
Taxa de Migração para administrar o número de indivı́duos na migração;
Intervalo de Migração para administrar a freqüência de migrações.
45
Capı́tulo 1. Fundamentação
Normalmente estes parâmetros são pré-definidos, porém [48, 49] introduz a
ocorrência de migração uma vez que a sub-população tenha convergido.
Figura 1.22: Topologia de Migração em Anel ou Unidirecional.
Figura 1.23: Topologia de Migração da Vizinhança ou Bidirecional.
46
Capı́tulo 1. Fundamentação
Figura 1.24: Topologia de Migração Irrestrita ou Multidirecional.
47
Capı́tulo 1. Fundamentação
AG de Difusão
O AG de Difusão (Fine Grained Parallel GA), Figura 1.25, é a arquitetura que
pode ser usada como um processador parelalo de AG. Ele considera a população
como uma estrutura única e contı́nua. Cada indivı́duo é designado a uma localização
geográfica numa superfı́cie populacional e usualmente colocada numa disposição 2D
(bidimensional). Esta é a função da topologia do processamento de elementos em
muitos computadores paralelos que são construı́dos nesta forma. Outras topologias
estudadas podem ser encontradas em [50, 51].
Figura 1.25: Topologia AG de Difusão.
É permitido aos indivı́duos a procriação com outras subpopulações próximas a
48
Capı́tulo 1. Fundamentação
sua vizinhança. Esta vizinhança é comumente adjacente, devido à restrições de comunicações entre computadores paralelos. Um pseudo-código é mostrado na Figura
1.26.
Em cada nódo (Ii,j ):
Iniciar;
enquanto n~
ao terminado faça
// Seqü^
encial:
Cálculo Fitness;
// Paralelo:
Enviar Indivı́duo ao Vizinho;
Receber Indivı́duo do Vizinho;
Selecionar Parceiro;
Reproduzir;
fim enquanto;
Figura 1.26: Pseudo-código do AG de Difusão [32].
Manderick e Spiessens [52] introduziram uma arquitetura paralela de AG
com uma população distribuı́da numa topologia 2D. Seleção e emparceiramento
eram somente possı́veis com indivı́duos vizinhos. Em acréscimo, [53, 54] introduziram um AG paralelo assı́ncrono, ASPARAGOS (Asynchronous Parallel Genetic
Optimization Strategy) system. Nesta configuração, o AG era implementado numa
rede escada conectada (ladder network) usando Transputers
12
com um indivı́duo
por processador. As aplicações práticas do AG de Difusão têm sido relatadas em
[55] para resolver problemas de empacotamento binomiais 2D (problema de otimização) [59, 60], e a mesma técnica tem sido usada para cuidar de um problema
de sincronização de tarefas [61, 58].
12
Famı́lia de microprocessadores Inmos com processadores interligados, programável numa lin-
guagem Occam.
49
Capı́tulo 2
Métodos e Materiais
Trataremos neste capı́tulo dos métodos e técnicas utilizados para o alinhamento
de seqüências biológicas e no próximo capı́tulo abordaremos os resultados obtidos.
2.1
Ambiente de Simulação
2.1.1
Linguagens de Programação Utilizadas
Para que houvesse portabilidade e clareza no algoritmo, primeiramente implementou-se em Java (Java Virtual Machine - JVM), porém o Java necessita de muita
memória e a velocidade de execução do algoritmo era muito lenta. Para resolver o
problema da velocidade e ainda manter a portabilidade o algoritmo, este foi convertido para a linguagem C++. Também foram utilizados scripts do shell do Linux
para facilitar a compilação, execução e coleta dos resultados.
Problemas Encontrados na Conversão do Programa
Um dos problema da conversão de um algoritmo escrito em Java para um
outro escrito em C++ está no tratamento das instâncias dos objetos quando estas
devem ser descartadas. No Java existe o Coletor de Lixo (Garbage Colector) que
se encarrega das instâncias dos objetos não mais utilizadas (referenciadas), já em
50
Capı́tulo 2. Métodos e Materiais
C++ este mecanismo automático não existe e é o programador que define quando
as instâncias são criadas e apagadas.
A versão do algoritmo em C++ para o AG Serial funcionou tanto no Linux
(RedHat 9, RedHat Enterprise Server e Fedora Core 1) quanto no Windows XP. A
versão paralela do AG não foi testada no Sistema Operacional Windows XP.
Problemas Encontrados no Desempenho do Programa
Mesmo após a conversão do algoritmo, o processo ainda era lento. Foi adotada
uma caracterı́stica presente no SAGA [99] que é a do fitness exclusivo, onde a população é totalmente heterogênea e cada indivı́duo possui um único valor de fitness.
O que realmente melhorou em muito a eficiência do algoritmo foi a reestruturação
dos indivı́duos da população (seqüências em processo de alinhamento), onde os gaps
alinhados foram deslocados para o final do alinhamento. Maiores detalhes serão
discutidos nas seções subseqüentes e no próximo capı́tulo.
2.1.2
Estrutura das Máquinas Utilizadas
As máquinas utilizadas para o processamento dos algoritmos foram:
• 1 Dual Intel Xeon 3.06GHz com: 4Gb de RAM e 120Gb de HD;
• 1 Athlon MP 2000 1.6GHz com: 4Gb de RAM e 60Gb de HD;
• 5 Athlon XP 2600 2.1GHz com: 500Mb de RAM e 60Gb de HD.
• Switch Planet Gigabit Ethernet: computadores interligados a 100Mbps FullDuplex.
51
Capı́tulo 2. Métodos e Materiais
2.2
Alinhamento Biológico Através do Algoritmo
Genético
Esta seção propõe um método alternativo baseado em Algoritmo Genético
para achar o alinhamento par-a-par ótimo [62, 63]. Este alinhamento de seqüências
é descrito como um cromossomo, onde cada cromossomo é associado a uma função de
aptidão baseado na matriz de substituição BLOSUM50. Para cada geração alguns
pares de cromossomo são aleatoriamente escolhidos para cruzamento. O próximo
passo é a mutação da descendência, levando-se em consideração a taxa de mutação.
O último passo é selecionar os cromossomos com maiores valores obtidos através
da função de aptidão. Este ciclo é repetido até que um critério de término seja
alcançado. Este critério também pode ser fixado pelo número de ciclos de evolução,
ou a quantidade de variação de indivı́duos entre diferentes gerações, ou um valor
pré-definido de aptidão. Neste trabalho foi escolhido o número de ciclos de evolução
(execuções computacionais). É descrito a seguir os detalhes desta implementação e
seus resultados.
2.2.1
Aproximação AG
Nesta seção é mostrado as estruturas de dados utilizadas e suas operações.
Estrutura de Dados
Para ilustrarmos esta aproximação, usaremos duas pequenas seqüências de
aminoácidos, S1 = HEAGAWGHEE e S2 = PAWHEAE, onde cada aminoácido é descrito na
Tabela 1.1. Dois possı́veis alinhamentos são mostrados nas Figuras 2.1 e 2.2.
S1 H E A G A W G H E E - - - - - - S2 - - - - - - - - - - P A W H E A E
Figura 2.1: Um possı́vel alinhamento.
Como mostra a Figura 2.3, o cromossomo é formado por 34 bits, onde os
primeiros 17 bits representam S1 , e os últimos 17 bits S2 . Este número é obtido
52
Capı́tulo 2. Métodos e Materiais
S1 H - E - A - G - A - W - G - H E E
S2 - P - A - W - H - E - A - E - - Figura 2.2: Outro possı́vel alinhamento.
devido à quantidade de aminoácido em S1 (10) e S2 (7), logo é possı́vel no máximo
17 aminoácidos e 17 gaps. Observe que os alinhamentos mostrados nas Figuras 2.1 e
2.2 são apenas dois de muitos alinhamentos possı́veis com o pior fitness, f (S1 , S2 ) =
−8 ∗ 17 = −1361 , devido ao número máximo de pareamento entre os aminoácidos e
gaps de ambas seqüências.
H - E - A - - G A - W G H E - - E P - - - A W H - E - A E - - - - 1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0
Figura 2.3: Descrição da configuração cromossômica binária.
Um dado importante é quanto a disposição dos aminoácidos no alinhamento a
qual deve ser respeitada, porque para a realização do alinhamento, os aminoácidos
devem ser apenas deslocados de suas posições e não trocados ou alterados, respeitando sempre a ordem original da seqüência. Portanto, o alinhamento é uma relação
apenas entre as seqüências envolvidas, isto é, se tomamos as duas seqüências S1 e S2 ,
e encontramos um alinhamento ótimo, isto não alterará as seqüência S1 e S2 quanto
à ordem de seus aminoácidos.
1
considerando a penalidade para gaps igual a −8.
53
Capı́tulo 2. Métodos e Materiais
Avaliação da Função de Aptidão
Para a avaliação da função de aptidão, utilizaremos um subconjunto da matriz
de substituição BLOSUM50 Tabela 2.12 .
Tabela 2.1: Subconjunto da matriz de substituição BLOSUM50.
H E A G A W G H E E
P
-2 -1 -1
-2
-1
-4
-2
-2
-1
-1
A
-2 -1
5
0
5
-3
0
-2
-1
-1
W
-3 -3 -3
-3
-3
15 -3
-3
-3
-3
H
10
0 -2
-2 -2
-3
-2
10
0
0
E
0
6
-1
-3
-1
-3
-3
0
6
6
-2 -1
5
0
5
-3
0
-2
-1
-1
-1
-3
-1
-3
-3
0
6
6
A
E
0
6
A Figura 2.4 ilustra como os valores de aptidão das seqüências S1 e S2 são
determinados considerando-se cada metade do cromossomo na aproximação AG, a
matriz de substituição BLOSUM50, e os gaps. A avaliação da função de aptidão
neste caso é: f (S1 , S2 ) = −2 − 8 + 5 − 8 − 8 − 8 − 1 − 8 + 0 + 0 − 8 − 8 = −54.
H
E
A
-
-
G
A
W
G H
E
E
P
-
A
W
H
-
E
-
A
E
-
-
-2
-8
5
-8
-8
-8 -1
-8
0
0
-8 -8
Figura 2.4: Função de aptidão (fitness function).
A Figura 2.5 mostra um cromossomo representando um alinhamento.
2
como mostrado na Seção 1.2.3 - Tabela 1.4.
54
Capı́tulo 2. Métodos e Materiais
H - E - A - - GA - WGHE - - E. - - PA - - - W - HE - - - A - E
1 0 1 0 1 00 1 1 0 1 1 1 1 00 1 .00 1 1 000 1 0 1 1 000 1 0 1
ou
H - E - A - - G A - WGHE - - E
- - PA - - - W - H E - - - A - E
1 0 1 0 1 00 1 1 0 1 1 1 1 0 0 1
0 0 1 1 0 00 1 0 1 1 0 0 0 1 0 1
Figura 2.5: Representação de um alinhamento na aproximação AG.
55
Capı́tulo 2. Métodos e Materiais
Cruzamento
A operação de cruzamento mescla ambos cromossomos (metade/metade) gerando duas descendências. As Figuras 2.6, 2.7 e 2.8 descrevem este processo.
H - E - A - - G A - W G H E - - E
- - P A - - - W - H E - - - A - E
1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1
0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1
- H - E - A G - A W - G - H - E E
- - P A - - - W - H E - - - A - E
0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1
0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1
Figura 2.6: Pais selecionados para a operação de cruzamento na aproximação AG.
H - E - A - - G A - W G H E - - E
- - P A - - - W - H E - - - A - E
1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1
0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1
k´
3́
Q
´
+́Q
s
- H - E - A G - A W - G - H - E E
- - P A - - - W - H E - - - A - E
0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1
0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1
Figura 2.7: Operação de cruzamento na aproximação AG.
H - E - A - - G A - W G H E - - E
- - P A - - - W - H E - - - A - E
1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1
0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1
- H - E - A G - A W - G - H - E E
- - P A - - - W - H E - - - A - E
0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1
0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1
Figura 2.8: Filhos gerados após a operação de cruzamento na aproximação AG. As
duas primeiras linhas representam um filho e as duas últimas o outro.
56
Capı́tulo 2. Métodos e Materiais
2.2.2
Mutação
Há uma sutil diferença na operação de mutação AG devido ao número de
aminoácidos no cromossomo que deve ser sempre o mesmo. Dessa forma, se a
mutação ocorre em qualquer bit 1 alterando-o para bit 0, o próximo bit 0 (bit
complementar) será modificado para bit 1, dentro de cada metade do cromossomo,
garantindo que a quantidade de aminoácidos da seqüência original seja sempre a
mesma. Este mesmo procedimento é aplicado no caso da mutação ocorrer em qualquer bit 0. Caso a mutação ocorra no último bit da primeira metade, a busca do
próximo bit complementar é iniciado a partir do inı́cio da seqüência; já no caso de
ocorrer no último bit da segunda metade, a busca pelo bit complementar é feita a
partir do inı́cio da segunda metade da seqüência.
As Figuras 2.9, 2.10 e 2.11 mostram um exemplo simples de como opera a
mutação. Outro exemplo mais detalhado é dado pelas Figuras 2.12, 2.13 e 2.14.
As posições selecionadas para mutação estão marcadas de vermelho, os bits complementares estão marcados de azul (para conservar a cadeia de aminoácidos), e as
posições marcadas de verde mostram o deslocamento sofrido pela seqüência devido
à mutação.
H - E - A - - GA - WGHE - - E.P - - A - - - W - HE - - - A - E
1 0 1 0 1 00 1 1 0 1 1 1 1 00 1 . 1 00 1 000 1 0 1 1 000 1 0 1
Figura 2.9: Mutação AG: 2 pontos de mutação selecionados aleatoriamente.
H - - - A - - GA - WGHE - - E.P - - AW - - W - HE - - - A - E
1 000 1 00 1 1 0 1 1 1 1 00 1 . 1 00 1 1 00 1 0 1 1 000 1 0 1
Figura 2.10: Mutação AG: executando a mutação nos 2 pontos selecionados.
H - - EA - - GA - WGHE - - E.P - - AW - - - - HE - - - A - E
1 00 1 1 00 1 1 0 1 1 1 1 00 1 . 1 00 1 1 0000 1 1 000 1 0 1
Figura 2.11: Mutação AG: alterando outras posições para manter o mesmo número
de aminoácidos.
57
Capı́tulo 2. Métodos e Materiais
H - - EA - - GA - WGHE - - E.P - - AW - - - - HE - - - A - E
1 00 1 1 00 1 1 0 1 1 1 1 00 1 . 1 00 1 1 0000 1 1 000 1 0 1
Figura 2.12: Mutação AG: 2 pontos de mutação selecionados aleatoriamente.
H - - EA - - GA - W - HE - - E.P - - AW - - - - HE - - - A - 1 00 1 1 00 1 1 0 1 0 1 1 00 1 . 1 00 1 1 0000 1 1 000 1 00
Figura 2.13: Mutação AG: executando a mutação nos 2 pontos selecionados.
H - - EA - - GA - W - GHE - E.PA - WH - - - - EA - - - E - 1 00 1 1 00 1 1 0 1 0 1 1 1 0 1 . 1 1 0 1 1 0000 1 1 000 1 00
Figura 2.14: Mutação AG: alterando outras posições para manter o mesmo número
de aminoácidos.
58
Capı́tulo 2. Métodos e Materiais
Resumo da Aproximação AG
Na operação AG uma seleção de subseqüências é feita a partir dos cromossomos
da população atual. Os pais (50%) são selecionados aleatoriamente e seus genes são
misturados, recombinados, e alterados (mutação) para a produção de descendentes
na próxima geração. A escolha dos membros sobreviventes é baseada nos maiores
valores da função de aptidão para manter o mesmo tamanho da população (não há
fitness repetido na população). Este processo é repetido em cada ciclo ou geração
até atingir o número de ciclos de evolução (execuções computacionais). As Figuras
2.15 e 2.16 ilustram essa aproximação.
59
Capı́tulo 2. Métodos e Materiais
Figura 2.15: Fluxograma da aproximação AG.
60
Capı́tulo 2. Métodos e Materiais
Algoritmo Genético ( . . . ) {
// iniciando as variáveis
t ← 0;
terminado ← falso;
P ← Objeto Populaç~
ao(...);
Pt ← Objeto Populaç~
ao(...);
// gerando a populaç~
ao inicial, usualmente com valores aleatórios
P.inicia populacao();
// calcula o fitness da populaç~
ao inicial
P.calc fitness();
// ciclo evolutivo
enquanto n~
ao terminado faça
// reinicia variáveis auxiliares
Pt.inicia populacao();
j ← 0;
// gera 50% de indivı́duos
para i ← 0 até P.tamanhoPopulacao() passo 4 faça
// seleciona uma sub-populaç~
ao
P’(j) ← P.selecionaPais();
// recombina os "genes" dos pais selecionados
P’(j).recombina();
// perturbar a populaç~
ao
P’(j).muta();
// calcula os novos fitness
P’(j).calc fitness();
// acrescenta os novos numa populaç~
ao temporária
Pt.adicione(P’(j));
// incrementa o contador
j ← j + 1;
fim para;
// acrescenta os novos na populaç~
ao atual
P.adicione(Pt);
// seleciona os sobreviventes através do fitness
P.sobreviventes();
// incrementa o contador
t ← t + 1;
// verifica término
terminado ← (t = número ciclos máximos) ou
(P.melhor fitness() >= fitness máximo);
fim enquanto;
}
Figura 2.16: Algoritmo da aproximação AG.
61
Capı́tulo 2. Métodos e Materiais
2.2.3
Dados Utilizados no AG Serial
A Tabela 2.2 mostra as seqüências utilizadas nas simulações. Mais detalhes sobre cada uma das seqüências podem ser encontrados no site do NCBI
(http://www.ncbi.nlm.nih.gov/ [70]) através do código da proteı́na. As seqüências
SEQex1 e SEQex2 foram utilizadas apenas para testar os algoritmos.
Tabela 2.2: Seqüências utilizadas nas simulações
Código da Proteı́na Descrição
Qtd.Nucleot.
NCBI
SEQex1
Seqüencia de teste 1
30
Não
SEQex2
Seqüencia de teste 2
21
Não
P69905
Hemoglobin Alpha Chain
138
Sim
P68871
Hemoglobin Beta Chain
135
Sim
P02185
Myoglobin
459
Sim
SMHY1C
Metallothionein I - Chinese hamster
183
Sim
SMRT1
Metallothionein I - Rat
183
Sim
O tamanho da população é constante (durante as gerações) com 600 indivı́duos.
Cada indivı́duo da população possui um fitness exclusivo e aleatório, obviamente
cada indivı́duo é único. A taxa de cruzamento foi fixada em pc = 50%. A população
inicial relativa a cada alinhamento estudado foi sempre a mesma. A condição de parada foi estabelecida para 1000, porque mais do que 1000 gerações torna o algoritmo
ineficiente.
Também distingüiremos duas versões do algoritmo genético:
Reestruturada (RE): que remove os gaps alinhados, ou seja, desloca os gaps
alinhados para o final do alinhamento;
Não-reestruturada (NRE): que permite os gaps entre os resı́duos de um alinhamento.
62
Capı́tulo 2. Métodos e Materiais
Para cada análise feita foi necessário um conjunto de mostras. O critério para
obtenção destas amostras foi o seguinte:
• 100 amostras quando: 20% < variância;
• 50 amostras quando: 10% < variância ≤ 20%;
• 20 amostras quando: variância ≤ 10%.
63
Capı́tulo 2. Métodos e Materiais
2.3
Alinhamento Biológico Através do Algoritmo
Genético Paralelo
Nesta seção abordaremos outras técnicas para a aplicação do AG, só que agora
em paralelo. Conforme a topologia: Global [64].
2.3.1
Computação Distribuı́da
Muitos dos problemas computacionais relacionados com tempo de resposta,
simulações e outros trabalhos que exigem processamento intensivo estão sendo resolvidos com a utilização dos sistemas distribuı́dos [7]. Se um processo pode ser
divido em tarefas independentes, então poderá ser processado por um único sistema (batch processing - processamento em lote); ou então serem processadas duas
ou mais tarefas ao mesmo tempo caso haja mais processadores disponı́veis; ou estas tarefas podem ser distribuı́das entre alguns sistemas (computação distribuı́da).
Se um trabalho não pode ser dividido em tarefas independentes é necessário processá-lo em um sistema único, em paralelo se houver mais processadores disponı́veis
(multithreading - multitarefa), ou um sistema distribuı́do confiável com memória e
armazenamento compartilhados. Estes conceitos estão ilustrados na Figura 2.17.
Tipos de Computação Distribuı́da
A seguir são descritos brevemente cada um dos tipos de computação distribuı́da
mais conhecidos.
Balanceamento de carga. É o mais simples e comum de ser usado para o processamento em lote. Um sistema central recebe comandos o qual decide onde
eles devem ser executados, dependendo da disponibilidade e carga do sistema.
Fila é um sistema livremente disponı́vel que controla processamento em lote
simples e balanceamento de carga;
Computação pela Web. Depende de um servidor que disponibiliza serviços on64
Capı́tulo 2. Métodos e Materiais
Figura 2.17: Visão estratégica computacional [65].
um cı́rculo completo representa uma tarefa independente;
um semi-cı́rculo representa uma subtarefa;
a cor cinza escura indica que a tarefa (ou subtarefa) está sendo executada.
65
Capı́tulo 2. Métodos e Materiais
line processado via Common Gateway Interface - (CGI). Os resultados são
devolvidos como uma página web ou por correio eletrônico (eletronic mail email);
Computação homóloga. É descrita por uma rede descentralizada onde cada computador compartilha recursos como arquivos, impressoras, ou aplicações com
estados iguais. Assim, qualquer computador pode ser um servidor provendo
serviços ou um cliente solicitando serviços;
Computação através de Cluster. Clusters são coleções de computadores conectados por uma rede local rápida (fast local area network - fast LAN) que
distribuem tarefas com balanceamento de software, ou pela criação e uso
de aplicações paralelas com bibliotecas de troca/passagem de mensagens tais
como: a Máquina Virtual Paralela (Parallel Virtual Machine - PVM) ou Multicomputador Local (Local Area Multicomputer - LAM), uma implementação
do padrão de Interface de Troca de Mensagem (Message Passing Interface MPI);
Computação através de Grid. Grids são recursos computacionais distribuı́dos
geograficamente, como os supercomputadores, clusters e sistemas de armazenamento conectados por uma rede dedicada ou através da Internet. Estes
recursos podem ser gerenciados por diferentes organizações;
Computação através de Objeto Distribuı́do . São objetos alocados em diversas máquinas numa rede e gerenciados de forma a trabalharem transparentemente como um só servidor. Quando uma requisição por um objeto é recebida
num dos computadores desta rede, este encaminha para o servidor onde reside
tal objeto, este servidor por sua vez devolve uma resposta ao computador que
encaminhou a requisição para que por fim responda à requisição inicial;
CORBA. A especificação Common Object Request Broker Architecture (CORBA)
sobre o Object Management Group (OMG) é um padrão para criação e utilização de objetos distribuı́dos. Ele especifica seu próprio protocolo, o Internet
Inter-ORB Protocol (IIOP);
66
Capı́tulo 2. Métodos e Materiais
DCOM e .NET. Microsoft’s Distributed Component Object Model (DCOM) é baseada em seu Component Object Model (COM), no protocolo Distributed Computing Environment (DCE) e no protocolo Remote Procedure Call (RPC).
COM provê um conjunto de interfaces a clientes e servidores para se comunicarem de forma idêntica. Um cliente DCOM chama métodos de um servidor
de objetos DCOM primeiro adquirindo um ponteiro para uma de suas interfaces e então usando-o como se fosse um objeto local. DCOM tem recentemente
se tornado parte do novo sistema .NET da Microsoftr ;
Java RMI. A tecnologia Java RMI da Sunr trabalha com servidores de objetos que
definem uma interface, na qual pode ser usada para acessar os objetos externos
à Máquina Virtual Java (Java Virtual Machine - JVM) corrente em JVM de
outras máquinas. RMI provê um serviço de nomeação para localizar servidores
de objetos. Um cliente adquire um objeto referência para um servidor de
objetos fazendo busca por uma referência de servidor de objetos, a partir daı́
ele pode invocar métodos sobre o servidor de objetos como se ele reside-se no
espaço de endereçamento do cliente. Esta tecnologia conta com a capacidade
do Java converter objetos num fluxo de dados e transmiti-lo. Então, ambos
servidor e cliente de objetos são escritos em Java. Java RMI pode ser usado
sobre qualquer plataforma com uma implementação JVM;
EJB. A especificação Enterprise Java Bean’s (EJB) define uma arquitetura para
o desenvolvimento e posicionamento estratégico de servidor secundário (de
apoio), componentes de software transacionais e distribuı́dos. Estes componentes chamados enterprise beans são objetos distribuı́dos que estão hospedados num recipiente EJB (EJB container) e provêm serviços remotos a clientes
distribuı́dos por toda uma rede. O recipiente (container) cuida de tarefas de
gerenciamentos complexos tais como: segurança, transações, persistência, concorrência e gerenciamento de recursos. No EJB, o recipiente, não a classe bean,
implementa a estrutura para as interfaces remota e local. Isto é para assegurar que todo método invocado sobre este tipo de referência por uma aplicação
cliente é primeiro tratado pelo recipiente e então delegado à instância bean.
O recipiente precisa interceptar estas requisições cuja intenção seja em relação
67
Capı́tulo 2. Métodos e Materiais
ao bean, de forma que ele pode aplicar persistência, transação e controle de
acesso automaticamente. Os servidores EJB precisam suportar ou o Java
Remote Method Protocol (JRMP) ou CORBA’s Internet Inter-ORB Protocol
(IIOP). O bean e o programador de aplicação somente enxergam a classe bean
e sua interface remota; os detalhes de comunicação da rede são escondidos.
Organizações podem construir seus próprios componentes ou comprá-los de
terceiros;
Computação Distribuı́da através da Internet. Organizações que requerem poder computacional intensivo, mas que não desejam investir nos equipamentos necessários, podem fazer uso de computadores de mesa pouco usados ou
fora de linha dentro de suas organizações ou mesmo computadores externos
conectados na Internet. Devido à largura de banda da Internet ser muito
limitada, esta estratégia somente trabalha para os assim chamados problemas “embaraçosamente paralelos”, isto é, problemas que podem ser divididos
em pequenos problemas altamente independentes. Muitos projetos avançados
usam a computação distribuı́da na Internet obtendo seu poder de processamento através de voluntários. Outros oferecem incentivos tais como: listas de
classificação, apostas em corridas de cavalos (sweepstakes) ou mesmo pequenos
pagamentos. Participantes são tipicamente requeridos para baixarem e instalarem um programa que então executa despercebidamente (sem atrapalhar)
em segundo plano (background), como por exemplo um protetor de tela. O
programa então baixa automaticamente e processa pequenas unidades de trabalho até que seja interrompido pelo usuário, e o ponto em que a unidade de
trabalho está em processamento, se possı́vel, é gravado ou então descartado.
68
Capı́tulo 2. Métodos e Materiais
2.3.2
AG no Ambiente Distribuı́do
Na implementação do AG paralelo [65] é necessário utilizar múltiplos processos,
onde cada um é alocado em um processador distinto, além troca de informações entre
eles. Assim, há uma necessidade de um método pelo qual se possa transferir dados
entre estes processos. A Interface de Passagem (ou troca) de Mensagem (Messaging
Passing Interface - MPI) e a Máquina Paralela Virtual (Parallel Virtual Machine PVM [11]) [8, 9, 10] provêm um meio de transferir estes dados entre os processos 3 .
MPI e PVM são especificações de bibliotecas de comunicação (passagem/troca de
mensagem) que podem escrever programas paralelos portáveis, deixando o funcionamento interno do protocolo de comunicação transparente ao código de chamada.
A biblioteca MPI foi escolhida para o desenvolvimento deste trabalho. Não
houve um estudo comparativo entre MPI e PVM quanto ao desempenho do AG
paralelo, pois ambas bibliotecas (MPI e PVM) são portáveis e executam arquivos
binários diferentes num sistema paralelo, no caso de programas MIMD (Multiple
Instruction Stream, Multiple Data Stream) [1]. Enquanto o MPI cria e conecta os
processos, o PVM necessariamente precisa de um daemon (provedor de serviços)
para cada usuário e em cada máquina para criar e manter a comunicação entre
os processos. Outras diferenças entre MPI e PVM podem ser encontradas nas referências [8, 9, 10].
O MOSIX (Multicomputer Operating System for Unix) [12, 13] por sua vez faz
o balanceamento de carga. Com ele, o sistema gerencia um conjunto de máquinas
como se fossem uma só, operando de maneira transparente ao usuário. Se um
programa é executado numa máquina gerenciada pelo MOSIX e houver a necessidade
de um maior processamento, o MOSIX calcula os custos de comunicação e recursos
de cada máquina do cluster (conjunto de computadores interligados) e a partir daı́
transfere parte do processamento para a máquina mais apta. O MPI e o MOSIX
podem trabalhar juntos para melhorar o desempenho do cluster.
A transferência de dados usando a MPI é feita através de uma chamada de
3
DCE (Distributed Computing Enviroment): também é uma opção para processamento dis-
tribuı́do [14]
69
Capı́tulo 2. Métodos e Materiais
função da biblioteca. Além da comunicação ponto-a-ponto, a MPI suporta comunicação coletiva e em grupos. Isto permite uma redução no envio elevado de
informações a um grupo (broadcast) e no recebimento de um grupo (gather) de
processos [6]. Esta idéia é ilustrada na Figura 2.18 4 .
MPI é, portanto, uma biblioteca para transmissão de dados num ambiente
de memória distribuı́da, máquinas paralelas massivas, rede de estações (Network of
Workstation - NOWs) e redes heterogêneas [3] além de suporte para máquinas com
processamento simétrico (Symetric MultiProcessing - SMP). MPI possui mais de
120 procedimentos e funções onde apenas 6 são suficientes para resolver a maioria
dos problemas existentes atualmente [4]. No presente trabalho foram utilizados
apenas estes seis procedimentos/funções, mais duas variantes e outras duas funções.
Estes procedimentos são MPI Init, MPI Comm size, MPI Comm rank, MPI Send,
MPI Rec, MPI Irecv, MPI Isend, MPI Wait, MPI Test, MPI Finalize. A versão
MPI 1.2.6 utilizada assume que todos os processos estão estaticamente alocados,
ou seja, o número de processos é configurado no inı́cio do programa em execução e
nenhum processo adicional é criado durante a execução. A cada processo é atribuı́do
um único inteiro (integer rank) na faixa de 0, 1, ..., p − 1, onde p é o número de
processos.
Processo 0
Processo 1
Processo 2
Processo p − 1
...
Mestre
Escravo 1
Escravo 2
Escravo p − 1
...
Figura 2.18: Esquema de processos MPI.
Como a biblioteca MPI é multiplataforma, a portabilidade de um programa
paralelo para outro sistema operacional não requer nenhuma mudança nas chamadas
de comunicação. Os desenvolvedores da biblioteca MPI tiveram o cuidado com os
detalhes de hardware, deixando por conta do programador apenas a preocupação
com a implementação do programa. Esta complexidade embarcada numa biblioteca
permite ao MPI transcender plataformas.
4
A topologia é definida pelo programador e esta em particular foi adotada neste trabalho.
70
Capı́tulo 2. Métodos e Materiais
2.3.3
Aproximação AG Paralela
AG paralelo global possui um mestre e seis escravos. O mestre envia 100
cromossomos para cada escravo fazer a recombinação, mutação e calcular o valor
da função de aptidão. Após isto, cada escravo envia os novos cromossomos gerados
(50) para o mestre que escolhe os primeiros 600 melhores alinhamentos par-a-par
(valor de aptidão). As Figuras 2.19,2.20,2.21,2.22 e 2.23 ilustram esta aproximação.
Figura 2.19: Fluxograma da aproximação AG paralelo - processo mestre.
71
Capı́tulo 2. Métodos e Materiais
Figura 2.20: Fluxograma da aproximação AG paralelo - processo escravo.
72
Capı́tulo 2. Métodos e Materiais
Algoritmo Genético ( . . . ) {
// iniciando MPI
MPI Inicia();
// iniciando as variáveis
t ← 0;
P ← Objeto Populaç~
ao(...);
P.inicia populacao(...);
terminado ← falso;
// envia informaç~
oes de controle a cada processo escravo
ametros de configuraç~
ao...);
MPI Envia(...par^
// calcula o fitness da populaç~
ao inicial
P.calc fitness();
// Ciclo evolutivo
enquanto n~
ao terminado faça
// envia uma sub-populaç~
ao a cada processo escravo
para i ← 1 até No Escravos faça
¯
// divide a populaç~
ao e envia
subpopul ← P.subpopul(No Escravos,i);
¯
MPI Envia(...subpopul...);
fim para;
// recebe uma sub-populaç~
ao de cada processo escravo
para i ← 1 até No Escravos faça
¯
MPI Recebe(...subpopul...);
// acrescenta os novos na populaç~
ao atual
P.adicione(subpopul);
fim para;
// seleciona os sobreviventes através do fitness
P.sobreviventes();
// incrementa o contador
t ← t + 1;
// verifica término
terminado ← (t = número ciclos máximos) ou
(P.melhor fitness() >= fitness máximo);
MPI Envia(...terminado...);
fim enquanto;
// terminando MPI
MPI Termina();
}
Figura 2.21: Algoritmo da aproximação AG paralelo - processo mestre.
73
Capı́tulo 2. Métodos e Materiais
Algoritmo Genético ( . . . ) {
// iniciando MPI
MPI Inicia();
// recebe informaç~
oes de controle do processo mestre e inicia variáveis
t ← 0;
terminado ← falso;
MPI Recebe(...par^
ametros de configuraç~
ao...);
P ← Objeto Populaç~
ao(...);
Pt ← Objeto Populaç~
ao(...);
// Ciclo evolutivo
enquanto n~
ao terminado faça
// recebe uma sub-populaç~
ao do processo mestre
MPI Recebe(...subpopul...);
P.inicia populacao(..subpopul...);
// n~
ao precisa calcular o fitness da populaç~
ao inicial, o servidor envia
// reinicia variáveis auxiliares
Pt.inicia populacao();
j ← 0;
// Gera 50% de indivı́duos
para i ← 0 até P.tamanhoPopulacao() passo 4 faça
// seleciona uma sub-populaç~
ao
P’(j) ← P.selecionaPais();
// recombina os "genes" dos pais selecionados
P’(j).recombina();
// perturbar a populaç~
ao
P’(j).muta();
// calcula os novos fitness
P’(j).calc fitness();
// acrescenta os novos numa populaç~
ao temporária
Pt.adicione(P’(j));
// incrementa o contador
j ← j + 1;
fim para;
// acrescenta os novos na populaç~
ao atual
P.adicione(Pt);
// seleciona os sobreviventes através do fitness
P.sobreviventes();
// envia a populaç~
ao e os fitness ao processo mestre
MPI Envia(...subpopul...);
// incrementa o contador
t ← t + 1;
// verifica término
MPI Recebe(...terminado...);
fim enquanto;
// terminando MPI
MPI Termina();
}
Figura 2.22: Algoritmo da aproximação AG paralelo - processo escravo.
74
Capı́tulo 2. Métodos e Materiais
Figura 2.23: Funcionamento do AG Paralelo.
.........
Fluxo de dados Mestre → Escravo
.........
Fluxo de dados Escravo → Mestre
———–
Fluxo de controle Mestre → Escravo
75
Capı́tulo 2. Métodos e Materiais
2.3.4
Dados Utilizados no AG Paralelo
As seqüências utilizadas na simulação do AG serial são as mesmas para o
AG paralelo. Para facilitar a leitura a Tabela 2.2 será mostrada novamente na
Tabela 2.3.
Tabela 2.3: Seqüências utilizadas nas simulações
Código da Proteı́na Descrição
Qtd.Nucleot.
NCBI
SEQex1
Seqüencia de teste 1
30
Não
SEQex2
Seqüencia de teste 2
21
Não
P69905
Hemoglobin Alpha Chain
138
Sim
P68871
Hemoglobin Beta Chain
135
Sim
P02185
Myoglobin
459
Sim
SMHY1C
Metallothionein I - Chinese hamster
183
Sim
SMRT1
Metallothionein I - Rat
183
Sim
O tamanho da população é constante (durante as gerações) com 600 indivı́duos
no total, sendo 100 indivı́duos para cada um dos 6 processos que executam a evolução
da população. A taxa de cruzamento foi fixada em pc = 50%. Cada processo executa
100 ciclos evolutivos antes de devolver o produto da evolução da população ou antes
da imigração/emigração. Cada indivı́duo da população possui um fitness exclusivo
e aleatório. A população inicial relativa a cada alinhamento estudado foi sempre a
mesma. A condição de parada foi pré-estabalecida para 100, o que dá um tempo
razoável a para convergência do alinhamento ótimo.
76
Capı́tulo 3
Resultados
Antes de analisarmos os resultados obtidos pelos algoritmos serial e paralelo,
abordaremos alguns pontos relativos ao desempenho. Depois mostraremos os resultados obtidos pela aplicação dos algoritmos nas seqüências (conforme Tabelas 2.2 e
2.3) sem esquecermos dos parâmetros de execução como, por exemplo, probabilidade
de mutação e cruzamento.
77
Capı́tulo 3. Resultados
3.1
Análise de Desempenho do AG Serial Proposto
Nesta análise, consideraremos o tempo despendido pelo algoritmo nas diferen-
tes versões, RE (com reestruturação dos alinhamentos) e NRE (sem reestruturação
dos alinhamentos), para convergir ao valor máximo do alinhamento calculado através
do modelo de pontuação (Matriz de Pontuação, Seção 1.2.3).
As seqüências analisadas foram: SEQex1 com SEQex2 e P69905 com P68871.
Estas seqüências foram selecionadas porque as duas primeiras são menores e as duas
seguintes maiores. Também foi analisado o tempo de manipulação das instâncias
dos objetos comparado com o tempo de processamento total. Os resultados são
mostrados nas subseções à seguir.
78
Capı́tulo 3. Resultados
3.1.1
Análise de Desempenho: Seqüencias SEQex1 e SEQex2
A Tabela 3.1 contém a média dos tempos das Figuras 3.1-3.4 por probabilidade
de mutação. Todas as simulações convergiram. Observe que o valor que está em
negrito na Tabela 3.1 é a menor média de tempo gasto para os algoritmos obterem
o melhor alinhamento. Comparando-se a menor média do algoritmo NRE (sem
reestruturação dos alinhamentos) que está em 80% com a média do algoritmo com
RE (com reestruturação) que está em 80% (note que não é a menor média do
algoritmo com RE), obteremos:
Desempenho =
0.476N RE
100 = 192.71%
0.247RE
(3.1)
onde o valor 192.71% representa o quanto o algoritmo AG serial RE foi melhor
em relação ao AG serial NRE.
Tabela 3.1: Tempo médio de processamento (Figuras 3.1-3.4) por probabilidade de
mutação.
Prob. Mutação
Tempo (s)
Prob. Mutação
Tempo
0.25%
0.476
50%
0.366
1%
0.712
60%
0.350
10%
0.525
70%
0.372
20%
0.395
80%
0.315
30%
0.494
90%
0.336
40%
0.366
10%
0.398
79
Capı́tulo 3. Resultados
Figura 3.1: Desempenho do AG Serial sem RE (NRE) por probabilidade de mutação.
Figura 3.2: Desempenho do AG Serial com RE apenas uma vez.
80
Capı́tulo 3. Resultados
Figura 3.3: Desempenho do AG Serial com RE a cada 10 gerações.
Figura 3.4: Desempenho do AG Serial com RE.
81
Capı́tulo 3. Resultados
3.1.2
Análise de Desempenho: Seqüencias P69905 e P68871
A Tabela 3.2 contém a média dos tempos das Figuras 3.5-3.6 por probabilidade de mutação. As versões do algoritmo NRE e 1RE para as seqüências P69905
e P68871 não convergiram antes de 1000 gerações, portanto, seus resultados foram
desprezados. Já os ı́ndices de convergência para as demais simulações são mostrados
nas Figuras 3.7 e 3.8. Observe que o valor que está em negrito na Tabela 3.2 é a
menor média de tempo gasto para os algoritmos obterem o melhor alinhamento.
Comparando-se a menor média do algoritmo g10RE (reestruturação dos alinhamentos a cada 10 gerações) que está em 10% com a média do algoritmo com RE que
está em 10% (note que não é a menor média do algoritmo com RE), obteremos:
Desempenho =
2.318g10RE
100 = 211.54
1.096RE
(3.2)
onde o valor 211.54% representa o quanto o algoritmo AG serial RE foi melhor
em relação ao AG serial g10RE.
Tabela 3.2: Tempo médio de processamento (Figuras 3.5-3.6) por probabilidade de
mutação.
Prob. Mutação
Tempo (s)
Prob. Mutação
Tempo
0.25%
1.868
50%
2.387
1%
1.877
60%
2.464
10%
1.707
70%
2.724
20%
2.374
80%
3.122
30%
2.103
90%
3.155
40%
2.107
10%
2.989
82
Capı́tulo 3. Resultados
Figura 3.5: Desempenho do AG Serial com RE a cada 10 gerações.
Figura 3.6: Desempenho do AG Serial com RE.
83
Capı́tulo 3. Resultados
Figura 3.7: Índice de convergência do AG Serial com RE a cada 10 gerações.
Figura 3.8: Índice de convergência do AG Serial com RE.
84
Capı́tulo 3. Resultados
3.1.3
Tempo de Manipulação de Instâncias de Objetos versus Tempo de Processamento
As Figuras 3.9 e 3.10 mostram uma estimativa do tempo gasto com a manipulação de estruturas de dados (construtor e destrutor de objetos) durante a
execução do algoritmo (1000 ciclos evolutivos). Conclui-se facilmente que é possı́vel
melhorar o desempenho do algoritmo evitando a instanciação dinâmica dos objetos
(alocação dinâmica de memória). Assim, é necessário reimplementar todo o algoritmo para que no inı́cio de sua execução seja alocado toda a memória necessária.
Só para se ter uma idéia do problema, em média são instanciados, a cada ciclo evolutivo, 7.698 novos objetos.
Figura 3.9: Tempo de Processamento x (RE e NRE com 50% e 100% de probabilidade de mutação). Seqüências: SEQex1 e SEQex2.
85
Capı́tulo 3. Resultados
Figura 3.10: Tempo de Processamento x (RE e NRE com 50% e 100% de probabilidade de mutação). Seqüências: P69905 e P68871.
86
Capı́tulo 3. Resultados
3.2
Comparação dos Resultados do AG Serial
Proposto com o Algoritmo de Needleman e
Wunsch
Para que possamos avaliar a eficiência do AG serial, compararemos o tempo
gasto pelos algoritmos: clássico (Needleman e Wunsch) e AG serial RE, para alinhar
as seqüências da Tabela 2.2. O algoritmo clássico foi escrito na linguagem Java e
obtido na internet no endereço mostrado na referência [36]. A escolha do AG serial
RE foi devida ao melhor desempenho, além disso, a versão original do algoritmo
(AG serial NRE) tinha um ı́ndice de convergência muito abaixo do AG serial RE.
Os resultados obtidos são mostrados nas Tabelas 3.3 e 3.4.
Tabela 3.3: Resultados obtidos pelo algoritmo clássico de Needleman e Wunsch, e
o algoritmo genético. O algoritmo clássico não realiza E/S (entrada/saı́da) de dispositivo, enquanto que o AG serial RE faz E/S.
Seqüências
T1 (s)
T2 (s)
Tx
Observação
SEQex1 e SEQex2
0,0016
0,2900
181.25
convergência: 100%
P69905 e P68871
0.0004
1,9640
4910.00
população1 , convergência: 32%
P69905 e P68871
0.0004
1,7614
4403.50
população2 , convergência: 46%
SMHY1C e SMRT1
0,0096
5,4467
567.36
população1 , convergência: 100%
SMHY1C e SMRT1
0,0096
0,0303
3.15
população2 , convergência: 100%
P02185 e P69905
0,0026
1,9390
745.77
população1 , convergência: 100%
P02185 e P69905
0,0026
0,0225
8.65
população2 , convergência: 100%
P02185 e P68871
0,0310
1,9390
62.55
população1 , convergência: 100%
P02185 e P68871
0,0310
0,0225
0.73
população2 , convergência: 100%
T1 : tempo médio (em segundos) de processamento do algoritmo clássico;
T2 : tempo médio (em segundos) de processamento do AG serial RE;
Tx : (Tx = T2 /T1 ) quantas vezes o algoritmo clássico é mais rápido que o
AG Serial RE.
As Figuras 3.11-3.19 mostram a evolução das populações das seqüências da
87
Capı́tulo 3. Resultados
Tabela 3.4: Resultados obtidos pelo algoritmo clássico de Needleman e Wunsch, e o
algoritmo genético. O algoritmo clássico realiza E/S (entrada/saı́da)
de dispositivo, enquanto que o AG serial RE faz E/S.
Seqüências
T1 (s)
T2 (s)
Tx
Observação
SEQex1 e SEQex2
0,0269
0,2900
10.78
convergência: 100%
P69905 e P68871
3.4365
1,9640
0.57
populacao1 , convergência: 32%
P69905 e P68871
3.4365
1,7614
0.51
populacao2 , convergência: 46%
SMHY1C e SMRT1
13,058
5,4467
0.42
populacao1 , convergência: 100%
SMHY1C e SMRT1
13,058
0,0303
0.002
populacao2 , convergência: 100%
P02185 e P69905
4,0968
1,9390
0.47
populacao1 , convergência: 100%
P02185 e P69905
4,0968
0,0225
0.005
populacao2 , convergência: 100%
P02185 e P68871
4,7436
1,9390
0.41
populacao1 , convergência: 100%
P02185 e P68871
4,7436
0,0225
0.005
populacao2 , convergência: 100%
T1 : tempo médio (em segundos) de processamento do algoritmo clássico;
T2 : tempo médio (em segundos) de processamento do AG serial RE;
Tx : (Tx = T2 /T1 ) quantas vezes o algoritmo clássico é mais rápido que o
AG Serial RE.
88
Capı́tulo 3. Resultados
Tabela 3.3.
Os tempos do algoritmo clássico (Java com E/S), descritos na Tabela 3.4,
foram obtidos no ambiente Linux, porém no Windows os tempos são bem menores e
próximo aos da Tabela 3.3. Observe que agora o tempo gasto pelo algoritmo clássico
é muito maior (Tabela 3.4), o que nos leva a pensar que o problema pode estar no
plug-in do Java para Linux. Entretanto, não podemos desconsiderar a E/S feita
pelo algoritmo AG serial RE.
Figura 3.11: Fitness máximo (normalizado) no processo evolutivo das seqüências:
SEQex1 e SEQex2.
89
Capı́tulo 3. Resultados
Figura 3.12: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P69905 e P68871 (populacao1 ).
Figura 3.13: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P69905 e P68871 (populacao2 ).
90
Capı́tulo 3. Resultados
Figura 3.14: Fitness máximo (normalizado) no processo evolutivo das seqüências:
SMHY1C e SMRT1 (populacao1 ).
Figura 3.15: Fitness máximo (normalizado) no processo evolutivo das seqüências:
SMHY1C e SMRT1 (populacao2 ).
91
Capı́tulo 3. Resultados
Figura 3.16: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P69905 (populacao1 ).
Figura 3.17: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P69905 (populacao2 ).
92
Capı́tulo 3. Resultados
Figura 3.18: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P68871 (populacao1 ).
Figura 3.19: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P68871 (populacao2 ).
93
Capı́tulo 3. Resultados
3.3
Comparação dos Resultados do AG Paralelo
Proposto com o Algoritmo de Needleman e
Wunsch
A seguir, compararemos o tempo gasto pelos algoritmos clássico (Needleman
e Wunsch) e o AG paralelo RE para alinhar as seqüências da Tabela 2.3 (idêntica
à Tabela 2.2), a fim de avaliar a eficiência do AG paralelo. O AG paralelo RE
converge mais rápido e eficientemente em relação à sua versão original do algoritmo
(AG paralelo NRE) o qual tinha um ı́ndice de convergência muito abaixo do AG
paralelo RE. Os resultados obtidos são mostrados nas Tabelas 3.5 e 3.6.
Tabela 3.5: Resultados obtidos pelo algoritmo clássico de Needleman e Wunsch, e o
algoritmo genético proposto. O algoritmo clássico não realiza E/S
(entrada/saı́da) de dispositivo, enquanto que o AG serial RE faz E/S.
Seqüências
T1 (s)
T2 (s)
Tx
Observação
SEQex1 e SEQex2
0,0016
3.6051
2253
convergência: 100%
P69905 e P68871
0.0004
24.336
60840
populacao1 , convergência: 20%
P69905 e P68871
0.0004
20.469
51172
populacao2 , convergência: 30%
SMHY1C e SMRT1
0,0096
53.319
5554
populacao1 , convergência: 100%
SMHY1C e SMRT1
0,0096
1.3936
P02185 e P69905
0,0026
24.404
P02185 e P69905
0,0026
1.2662
487 populacao2 , convergência: 100%
P02185 e P68871
0,0310
22.221
716 populacao1 , convergência: 50%
P02185 e P68871
0,0310
19.144
617 populacao2 , convergência: 60%
145 populacao2 , convergência: 100%
9386
populacao1 , convergência: 100%
T1 : tempo médio de processamento do algoritmo clássico;
T2 : tempo médio de processamento do AG paralelo RE;
Tx : (Tx = T2 /T1 ) quantas vezes o algoritmo clássico é mais rápido que o
AG Paralelo RE.
As Figuras 3.20-3.28 mostram a evolução das populações das seqüências da
Tabela 3.5.
94
Capı́tulo 3. Resultados
Tabela 3.6: Resultados obtidos pelo algoritmo clássico de Needleman e Wunsch, e o
algoritmo genético. O algoritmo clássico realiza E/S (entrada/saı́da)
de dispositivo, enquanto que o AG serial RE faz E/S.
Seqüências
T1 (s)
T2 (s)
Tx
Observação
SEQex1 e SEQex2
0,0269
3.6051
134.02
convergência: 100%
P69905 e P68871
3.4365
24.336
7.08
populacao1 , convergência: 20%
P69905 e P68871
3.4365
20.469
5.96
populacao2 , convergência: 30%
SMHY1C e SMRT1
13,058
53.319
4.08
populacao1 , convergência: 100%
SMHY1C e SMRT1
13,058
1.3936
0.10
populacao2 , convergência: 100%
P02185 e P69905
4,0968
24.404
5,96
populacao1 , convergência: 100%
P02185 e P69905
4,0968
1.2662
0.31
populacao2 , convergência: 100%
P02185 e P68871
4,7436
22.221
4.68
populacao1 , convergência: 100%
P02185 e P68871
4,7436
19.144
4.04
populacao2 , convergência: 100%
T1 : tempo médio de processamento do algoritmo clássico;
T2 : tempo médio de processamento do AG paralelo RE;
Tx : (Tx = T2 /T1 ) quantas vezes o algoritmo clássico é mais rápido que o
AG Paralelo RE.
Figura 3.20: Fitness máximo (normalizado) no processo evolutivo das seqüências:
SEQex1 e SEQex2.
95
Capı́tulo 3. Resultados
Figura 3.21: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P69905 e P68871 (populacao1 ).
Figura 3.22: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P69905 e P68871 (populacao2 ).
96
Capı́tulo 3. Resultados
Figura 3.23: Fitness máximo (normalizado) no processo evolutivo das seqüências:
SMHY1C e SMRT1 (populacao1 ).
Figura 3.24: Fitness máximo (normalizado) no processo evolutivo das seqüências:
SMHY1C e SMRT1 (populacao2 ).
97
Capı́tulo 3. Resultados
Figura 3.25: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P69905 (populacao1 ).
Figura 3.26: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P69905 (populacao2 ).
98
Capı́tulo 3. Resultados
Figura 3.27: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P68871 (populacao1 ).
Figura 3.28: Fitness máximo (normalizado) no processo evolutivo das seqüências:
P02185 e P68871 (populacao2 ).
99
Capı́tulo 4
Conclusão
O trabalho mostra que o método alternativo baseado na técnica do Algoritmo
Genético (AG) [29] encontra com boa eficiência o alinhamento ótimo entre duas
seqüências de nucleotı́deos. Já o AG paralelo ainda não mostrou resultados satisfatórios.
O algoritmo também pode encontrar mais de um alinhamento ótimo, caso
exista. Dessa forma, quando o biologista alinha duas ou mais seqüências, ele estará
poupando tempo em suas análises.
4.1
Conclusão dos Resultados do AG Serial
A partir dos resultados mostrados na seção 3.2, verificamos que o algoritmo AG
serial converge eficientemente para soluções ótimas, mas o algoritmo clássico ainda
é mais eficiente. Note que é possı́vel encontrar mais do que um alinhamento ótimo,
e isto depende das seqüências analisadas, da população inicial e das probabilidades
de cruzamento e mutação.
É possı́vel melhorar o desempenho do algoritmo evitando a instanciação dinâmica dos objetos (alocação dinâmica de memória). Assim, é necessário reimplementar
todo o algoritmo para que no inı́cio de sua execução seja alocado toda a memória
necessária.
100
Capı́tulo 4. Conclusão
Um dos problemas encontrados foi a conseqüente homogeneidade da população
que tornou a convergência lenta. Algumas técnicas foram estudadas para resolver
este problema, como:
• melhor controle da taxa de mutação;
• melhor controle do tamanho da população, isto é, custo versus benefı́cio;
• indivı́duos com fitness exclusivo (baseado no SAGA - seção 1.3.1);
• reestruturação dos alinhamentos (indivı́duos), movendo os gaps alinhados para
o final do alinhamento.
Com estas técnica o algoritmo aumentou a performance e o baixı́ssimo ı́ndice
de convergência que nos piores casos era em torno de 0% (até 1000 gerações) e agora
passou a 30%.
Outras técnicas podem ser aplicadas para melhorar ainda mais o desempenho
do algoritmo, como:
• aprimoramento do algoritmo acrescentando outros métodos heurı́sticos;
• otimização do código do algoritmo;
• 90% das amostras que não convergiram, chegaram a 95% do fitness máximo.
Portanto, o procedimento de mutação deve ser revisto e testado com outros
métodos.
101
Capı́tulo 4. Conclusão
4.2
Conclusão dos Resultados do AG Paralelo
Na seção 3.3 abordamos a aproximação AG paralelo com o intuito de diminuir
o tempo de convergência do alinhamento ótimo entre duas seqüências. Na seção 3.1
mostramos algumas otimizações possı́veis e lembramos do estudo e desenvolvimento
de novos métodos heurı́sticos. Uma análise de tempo de comunicação e processamento também é necessária. Foi utilizado o MRTG (Multi Router Traffic Grapher),
porém não foi possı́vel obter uma análise precisa do fluxo de dados.
Os resultados obtidos mostraram que mesmo o AG serial sendo eficiente, é
necessário ainda algumas modificações para melhorar sua eficiência. Conseqüentemente, melhorar a eficiência do AG paralelo.
102
Capı́tulo 4. Conclusão
4.3
Trabalhos Futuros
É possı́vel melhorar o desempenho do AG serial e do AG paralelo, através do
estudo da complexidade de algoritmo destas implementações para otimizar o código
e as estruturas de dados. O MOSIX, como comentado no capı́tulo 2, terá um papel
fundamental nesta otimização.
A latência da rede (custo x benefı́cio → comunicação x processamento no AG
paralelo) foi apenas estimada observando o fluxo de dados do servidor (utilizando
o tcpdump, nmap, netstat e mrtg; todos utilitários do Linux), isto porque os computadores estão interligados por um Switch. Um cálculo mais apurado estimará
melhor este fluxo para que seja obtida uma melhor eficiência do algoritmo.
Um trabalho interessante seria a aplicação do AG para resolver o multialinhamento (alinhamento de mais de duas seqüências de nucleotı́deos) serial e paralelo.
Outro trabalho envolvendo o alinhamento de seqüências maiores, poderia explorar o poder computacional dos Grids e da Computação Distribuı́da através da
Internet (CDI) para resolvê-lo. No caso da CDI, uma infinidade de outras aplicações
podem ser resolvidas da mesma forma, desde que os algoritmos possam ser interrompidos e continuados (gravando e restaurando seus estados de execução).
103
Referências Bibliográficas
[1] TANENBAUM, Andrew S. MODERN OPERATIONG SYSTEMS. New Jersey
- USA: Prentice Hall, 1992. ISBN: 0-13-588187-0.
[2] 2a ESCOLA REGIONAL DE ALTO DESEMPENHO - ERAD, 2002. São Le¯
opoldo - Porto Alegre. Anais.
Editores: Tiarajú A. Diverio, Gerson G.
H. Cavalheiro - SBC/Instituo de Informática da UFRGS/UNISINOS/ULBRA,
2002. 298p.
[3] PACHECO, Peter S. PARALLEL PROGRAMMING WITH MPI. San Francisco - USA: Morgan Maufmann. 1996. 418p. ISBN: 1558603395.
[4] ARGONNE, National Laboratory, MISSISSIPI, State University of. MPI Message Passing Interface - Documentation and Download. Argonne - Illinois
- USA. Disponı́vel na internet no endereço: http://www.mcs.anl.gov/mpi/ em
novembro/2004.
[5] CURLEY B.E., Bernadette. Dissertation: System Identification using Neural
Networks Optimised with Genetic Algorithms. Dublin City University, Ireland:
Scholl of Eletronic Engineering. August-2002.
[6] KARNIADAKIS, George Em; KIRBY II, Robert M. Parallel Scientific Computing in C++ and MPI. Cambridge University Press, 2003. 628p. ISBN:
0521520800.
[7] CUERVO, Carlos Hermán Vargs. Dissertação de Mestrado: Otimização do
Cálculo de Parâmetros no Processo de Ajuste de Históricos de Produção usando
PVM. Dpto. Eng. de Petróleo - FEM - Unicamp - São Paulo - SP. Março-1997.
104
REFERÊNCIAS BIBLIOGRÁFICAS
[8] GROPP, William; LUSK, Ewing. PVM and MPI Are Completely Different. Disponı́vel na internet no endereço: http://citeseer.ist.psu.edu/573977.html(1997)
em novembro/2004.
[9] GROPP, William; LUSK, Ewing. Goals Guiding Design: PVM and MPI. Disponı́vel na internet no endereço: http://citeseer.ist.psu.edu/568858.html(2002)
em novembro/2004.
[10] GROPP, William; LUSK, Ewing.
ferent?
Why Are PVM and MPI So Dif-
Argonne - Illinois - USA. Technical Report PREPRINT
ANL/MCS-P667-0697, Mathematics and Computer Science Division, Argonne National Laboratory, June 1997. Disponı́vel na internet no endereço:
http://citeseer.ist.psu.edu/gropp97why.html em novembro/2004.
[11] GEIST, Al; BEGUELIN, Adam; DONGARRA, Jack; JIANG, Weicheng;
MANCHEK, Robert; SUNDERAM, Vaidy. PVM - Parallel Virtual Machine: A
User’s Guide and Tutorial for Network Parallel Computing. London - England:
The MIT Press, Cambridge, Massachusetts. 1994. Disponı́vel na internet no endereço: http://www.netlib.org/pvm3/book/pvm-book.ps em novembro/2004.
[12] BARAK, Amnon; SHILOH, Amnon. MOSIX: Cluster Managment System.
1999-2004. Disponı́vel na internet no endereço: http://www.mosix.org/ em novembro/2004.
[13] BARAK, Amnon; LA’ADAN, Oren. The MOSIX Multicomputer Operating
System for High Performance Cluster Computing. journal Future Generation
Computer Systems, Vol: 13, No 4-5, 1998. 361-372p. Disponı́vel na internet no
¯
endereço: http://citeseer.ist.psu.edu/barak98mosix.html em novembro/2004.
[14] IBM; Hewlett-Packard; Entegrity; Penn State; Chalmers. The Open Group
Debuts Open Source Licensing of DCE Source Code. 1995-2005. Disponı́vel na
internet no endereço: http://www.opengroup.org/dce/ em março/2005.
[15] WATERMAN, M. S.; WHITEMAN, D. E. Estimation of probability densities
by empirical density functions. INT. J. MATH. EDUC. SCI. TECHNOL., 1978,
VOL. 9, NO. 2, 127-137p.
105
REFERÊNCIAS BIBLIOGRÁFICAS
[16] MARTZ Jr., H. F.; WATERMAN, M. S. A Bayesian Model for Determining
the Optimal Test Stress for a Single Test Unit. TECHNOMETRICS, VOL. 20,
No 2, MAY-1978.
¯
[17] SMITH, T.F.; WATERMAN, M.S.; FITCH, W.M. Comparative Biosequence
Metrics. Journal of Molecular Mubon. 1981.
[18] SMITH, Temple F.; WATERMAN, Michael S. Comparison of Biosequences.
Advances in Applied Mathematics 2, 1981. 482-489p.
[19] SMITH, Temple F.; WATERMAN, Michael S. Overlapping Genes and Information Theory. Journal of Theory Biology. 1981. 91,379-380.
[20] SMITH, Temple F.; WATERMAN, Michael S. Identification of Common Molecular Subsequences. Journal of Molecular Biology. 1981. 147, 195-197p.
[21] WATERMAN, Michael S. Sequence alignments in the neighborhood of the optimum with general application to dynamic programming. USA: Applied Mathematical Sciences - Proc. Natl. Acad. Sci. Vol. 80, May-1983. 3123-3124p.
[22] WATERMAN, Michael S. Frequencies of restriction sites. Nucleic Acids Research. Volume 11 No 24. 1983.
¯
[23] SMITH, Temple F.; WATERMAN, Michael S.; LIPMAN, D.J.; WILBUR, W.
J. On the statistical significance of nucleic acid similarities. Nucleic Acids
Research. Volume 12 No 1. 1984.
¯
[24] VEERASSAMY, Shalini; SMITH, Andrew; TILLIER, Elisabeth R. M. A Transition Probability Model For Amino Acid Substitutions From Blocks. Journal
Computational Biology. 2003. 997-1010p.
[25] APOSTOLICO, Alberto; GIANCARLO, Raffaele. Sequence Alignment in Molecular Biology. Journal of Computational Biology, 1998. 173-196p.
[26] PAPOULIS, Athanasios. Probability, Random Variables, and Stochastic Processes. 3a Singapore: Ed. McGraw-Hill Book Co. 1991. ISBN: 0-07-048477-5.
¯
106
REFERÊNCIAS BIBLIOGRÁFICAS
[27] WHEELER, David. Weight Matrices for Sequence Similarity Scoring. USA:
Houston - Texas, Baylor College of Medicine: Department of Cell Biology. Version 2. May-1996. e-mail: [email protected]. Disponı́vel na internet no endereço: http://www.techfak.uni-bielefeld.de/bcd/Curric/PrwAli/nodeD.html
em janeiro/2005.
[28] HUGHEY, Richard; KARPLUS, Kevin; KROGH, Anders. SAM: Sequence
Alignment and Modeling Software System. Disponı́vel na internet no endereço:
http://www.cse.ucsc.edu/research/compbio/sam.html em novembro/2004.
[29] R. the and S. Research and G. University and o Department and o Science and
H. in and n artificial and A. Arbor and T. University and M. Press. Report
of the Systems Analysis Research Group SYS: Report of the Systems
Analysis Research Group SYS–1/92, University of Dortmund, Department of
Computer Science. Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: The University of Michigan Press. 1975. URL:
citeseer.ist.psu.edu/the75adaptation.html.
[30] KOZA, John; BENNETT III, Forrest H.; STIFFELMAN, Oscar.
lelization of Genetic Programming.
Paral-
Disponı́vel na internet no endereço:
http://www.genetic-programming.org/ em junho/2004.
[31] WOLFSON,
son.
Haim.
Disponı́vel
Biological
na
internet
no
Sequence
endereço:
gamba.math.tau.ac.il/Education/CS99b/class notes/class2.html
Comparihttp://pcem
ju-
nho/2004.
[32] MAN, K.F.; TANG, K.S.; KOWNG, S. Genetic Algorithms: concepts and
designs. London - Great Britain: Springer-Verlag, 1999. ISBN: 1852330724.
[33] DURBIN, Richard; EDDY, R.; KROGH, Anders; Mitchison, G. Biological
Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. United
Kingdom: Cambridge University Press, 1998. ISBN: 0-521-62041-4.
[34] PEVSNER, Jonathan. Bioinformatics and Functional Genomics. USA: By
Wiley-Liss, 2003. ISBN: 0-471-21004-8.
107
REFERÊNCIAS BIBLIOGRÁFICAS
[35] BARKAN, David. A parallel implementation of the Needleman-Wunsch algorithm for global gapped pair-wise alignment. USA: The Consortium for Computing in Small Colleges - Journal of Computing Sciences in Colleges: Vol. 17
Issue 6 Pag.239-239, 2002.
[36] SESTOFT, PETER. Implementation of some algorithms for pairwise alignment from Durbin: Biological Sequence Analysis, CUP 1998, chapter 2. version 1.4. Department of Mathematics and Physics, Royal Veterinary and Agricultural University - Denmark. 20-04-2003. e-mail: [email protected]. Disponı́vel na internet no endereço: http://www.dina.kvl.dk/ sestoft/bsa.html em
março/2005.
[37] BOICULESE L. Genetic algorithm in the control optimization. Rev Med Chir
Soc Med Nat Iasi, 103:176-81, Jan-Jun-1999.
[38] SUMIDA, B.H.; HOUSTON, A.I.; McNAMARA, J.M.; HAMILTON W.D. Genetic algorithms and evolution. Journal Theory Biology, 7-nov-1990. 59-84p.
[39] MAHFOUD, S.W. Population sizing for sharing methods. Urbana - USA:
IlliGAL Report Nøo 94005, Departament of Computer Science - University of
Illinois at Urbana-Champaign, 1994.
[40] DeJONG, K.A.; SPEARS, W.M. An analysis of the interacting roles of population size and crossover in genetic algoritms. Berlin: Proc. First Workshop
Parallel Problem Solving from Nature, Springer Verlag-1990. 38-47.
[41] GREFENSTETTE, JJ. Optimization of control parameters for genetic algoritms. IEEE Trans Systems, Man, and Cybernetics, 1986. SMC-16(1), 122-128.
[42] GAREY, M.R.; Johnson, D.S. Computers and intractability: a guide to the
theory of NP-completeness. San Francisco - USA: Freeman, 1979.
[43] CANTÚ-PAZ, E. A summary of research on parallel genetic algorithms. Urbana - USA: Illigal Report No 95007 - Illinois Genetic Algorithms Laboratory
¯
- University of Illinois at Urbana-Champaign, 1995.
108
REFERÊNCIAS BIBLIOGRÁFICAS
[44] CHIPPERFIELD, A.J.; FLEMING, P.J. Parallel genetic algorithms: A survey.
United Kingdom: ACSE Research Report No 518 - University of Sheffield, 1994.
¯
[45] GOLDBERG, David E. Genetic Algorithms in search, optimization and machine learning. USA: Ed. Addison-Wesley, 1989. ISBN: 0201157675.
[46] DAVIES, R.; CLARKE, T. Parallel implementation of a genetic algorithm.
Control Engineering Practice. Elsevier Science Publisher. Vol. 3. 1995. 11-19p.
ISSN: 0967-0661.
[47] DODD, N.; MACFARLANE, D.; MARLAND, C. Optimization of Artificial
Neural Network Structure Using Genetic Techniques Implemented on Multiple
Transputers. Transputing ’91, 1991. 687-700p.
[48] BRAUN, H. On solving travelling salesman problems by genetic algorithms.
Berlim: Proc. First Workshop Parallel Problem Solving from Nature, Springer
Verlag, 1990. 129-133p.
[49] MUNETOME, M.; TAKAI, Y.; SATO, Y. An efficient migration scheme for
subpopulation-based asynchronously parallel genetic algorithms. Proc. 5th Int.
Conf. Genetic Algorithms, 1993. 649p.
[50] ANDERSON, E.J.; FERRIS. M.C. A genetic algorithm for the assembly line
balancing problem. USA: Technical Report TR 926, Computer Sciences Departament, University of Wisconsin-Madison, , 1990.
[51] BALUJA, S. Structure and performance of fine-grain parallelism in genetic
search. Proc. 5th Int. Conf. Genetic Algorithm. 1993.
[52] MANDERICK, B.; SPIESSENS, P. Fine-grained parallel genetic algorithms.
Proc. 3rd. Int. Conf. Genetic Algorithms. 1989. 428-433p.
[53] GORGES-SCHLEUTER, M. ASPARAGOS: An asynchronous parallel genetic
optimization strategy. Proc. 3rd Int. Conf. Genetic Algorithms. 1989. 422-427p.
109
REFERÊNCIAS BIBLIOGRÁFICAS
[54] MÜHLENBEIN, H. Parallel genetic algorithms, population genetics and combinatorial optimizaation. Parallelism, Learning, Evolution, Springer-Verlag. 1989.
398-406p.
[55] KRÖGER, B.; SCHWENDERLING, P.; VORNBERGER, O. Parallel genetic
packing on transputers. Parallel Genetic Algorithms: Theory and Applications,
Amsterdam: IOS Press. 1993. 151-185p.
[56] CANTÚ-PAZ, Erick. A Survey of Parallel Genetic Algorithms. Urbana - USA:
University of Illinois at Urbana-Champaign. 1997. Disponı́vel na internet em
http://tracer.lcc.uma.es/tws/cEA/documents/cant98.pdf
[57] HERRERA, Francisco; LOZANO, Manuel .
Coded Genetic Algorithms.
Gradual Distributed Real-
IEEE - Transactions on Evolutionary Com-
putation, Vol. 4, no 1, April-2000. Disponı́vel na internet no endereço:
¯
http://sci2s.ugr.es/docencia/doctobio/graduales.pdf em novembro/2004.
[58] MASTROLILLI, Monaldo; GAMBARDELLA, Luca Maria. Effective Neighborhood Functions for the Flexible Job Shop Problem. Lugano - Switzerland:
IDSIA - Istituto Dalle Molle di Studi sull’Intelligenza Artificiale. 31-Jan-2000.
[59] HOPPER, E.; TURTON, B. C. H. A Review of the Application of MetaHeuristic Algorithms to 2D Strip Packing Problems. USA: School of Engineering, Cardiff University - Artificial Intelligence Review, Vol. 16, 2001. 257-300p.
Disponı́vel na internet no endereço: http://www.inf.utfsm.cl/ mcriff/EA/evaspace-planning/ht01.pdf em novembro/2004.
[60] WEI, Zheng; LEONG, H. W. Enhanced Packing Algorithms for iPACK Progress
Report. Singapore: School of Computing, National University of Singapore. 31Mar-2002.
[61] TAMAKI, H.; NICHIKAWA, Y. A parallel genetic algorithm based on a neighborhood model and its application to job shop scheduling. Parallel Problem
Solving from Nature, Vol. 2, 1992. 573-582p.
110
REFERÊNCIAS BIBLIOGRÁFICAS
[62] SILVA, Paulo Eduardo M. da; SHINODA, Ailton Akira; MACIEL, Carlos
Dias. . Ribeirão Preto-SP: 1st International Conference on Bioinformatics
and Computational Biology. May 14th - 16th 2003. Disponı́vel na internet no
endereço: http://www.vision.ime.usp.br/ cesar/programa/pdf/27.pdf em novembro/2004.
[63] SILVA, Paulo Eduardo M. da; SHINODA, Ailton Akira; MACIEL, Carlos Dias.
Finding the Best Biological Pairwise Alignment Through Genetic Algorithm.
Revista Semina. Ciências exatas e tecnológicas. Londrina - PR: , v.25, 2004.
[64] SILVA, Paulo Eduardo M. da; SHINODA, Ailton Akira; MACIEL, Carlos Dias.
Finding the Best Biological Pair-wise Alignment Through Genetic and Parallel
Algorithm. Palhoça-SC-Brasil: I Workcomp UNISUL - Universidade do Sul de
Santa Catarina. (12-14)-Maio-2004.
[65] JAIN, Eric. Distributed computing in bioinformatics. Open Mind Journals
Limited - Applied Bioinformatics. 2002. 13-20p.
[66] LAMBERT, Christophe; CAMPENHOUT, Jean-Marc Van; DeBOLLE, Xavier;
DEPIEREUX, Eric. Review of Common Sequence Alignment Methods: Clues
to Enhance Reliability. Bentham Science Publishers: Current Genomics. 2003.
Vol. 4 - no 2. p131-146.
¯
[67] PERTSEMLIDIS, Alexander;
FONDON III, John W.
Tutorial Ha-
ving a BLAST with bioinformatics (and avoiding BLASTphemy)..
oMed Central Ltd:
Publicado
em:
Genome Biology 2001,
27-09-2001.
Disponı́vel
na
Bi-
2:reviews2002.1-2002.10.
internet
no
endereço:
http://genomebiology.com/2001/2/10/reviews/2002 em janeiro/2005.
[68] CHIAROMONTE, F.; YAP, V.B.; MILLER, W. Scoring Pairwise Genomic
Sequence Alignments. Singapore: Pac Symp Biocomput. 2002. p. 115-26. [PubMed - indexed for MEDLINE: 11928468].
[69] SNUSTAD, D. Peter; SIMMONS, Michael J. Principles of Genetics. 2a Ed.
¯
USA: John Wiley & Sons Inc. 2000. ISBN: 0-471-29800-X.
111
REFERÊNCIAS BIBLIOGRÁFICAS
[70] U.S. GOVERNMENT: National Library of Medicine. National Center for Biotechnology Information. U.S. National Library of Medicine, 8600 Rockville
Pike, Bethesda, MD 20894. http://www.ncbi.nlm.nih.gov/ em janeiro/2005.
[71] ZAHA, Arnaldo. Biologia Molecular Básica. 2a Edição. Porto Alegre - Brasil:
¯
Editora Marcado Aberto. 2000. ISBN: 85-280-0283-7.
[72] VOGEL, Friedrich; MOTULSKY, Arno G. Genética Humana - Tradução. Rio
de Janeiro - RJ - Brasil: Editora Guanabara Koogan S.A. 2000.
[73] WEAVER, Robert F.; HEDRICK, Philip W. Genetics. 3a Edição. Dubuque ¯
IA - USA: WCB (Wm. C. Brown) Publishers, Kerper Boulevard. 1997. ISBN:
0-697-16000-9.
[74] DARBRE, Philippa D. Basic Molecular Biology. 1a Edição. USA: John Wiley
¯
& Sons Inc. 1999. IBSN: 0-471-97705-5.
[75] PNAS (Proceedings of the National Academy of Sciences). Identification of
a new malaria susceptibility locus (Char4) in recombinant congenic strains
of mice.
Disponı́vel na internet no endereço:
http://www.pnas.org em
agosto/2004.
[76] POWELL, Jeffrey R.; MORIYAMA, Etsuko N. Colloquium Paper: Evolution
of codon usage bias in Drosophila. Proc. Natl. Acad. Sci. USA, Vol. 94, July
1997. 7784-7790p.
[77] LARSSON, Jan; SVENSSON, Malin J.; STENBERG, Per; MÄKITALO, Maria. Painting of fourth in genus Drosophila suggests autosome-specific gene regulation. Published online before print as 10.1073/pnas.0400978101. Vol. 101.
2004. 9728-9733p.
[78] ÁVILA,
leculares
forme.
Mariana
das
B.
G.
de;
SOMA,
Hemoglobinopatias
Disponı́vel
na
internet
com
no
Mithitaka.
ênfase
na
endereço:
Bases
Anemia
moFalci-
http://www.puc-
campinas.edu.br/pesquisa/i semana cientifica/tcc resumos/63F1A5CF-BD824558-B49A-5ADDC6E8F.pdf em novembro/2004.
112
REFERÊNCIAS BIBLIOGRÁFICAS
[79] ALTSCHUL, S.F.; GISH , W.; MILLER, W.; MYERS, E.W.; LIPMAN, D.J.
Basic local alignment search tool. Journal of Molecular Biology, Vol. 215. 1990.
403-410p.
[80] PEARSON, W.R.; LIPMAN D.J. Improved tools for biological sequence comparison. Proc. Natl. Acad. Sci. USA, Vol. 85, 1988. 2444-2448p.
[81] NEEDLEMAN, S.B.; WUNSCH, C.D. A general method applicable to the search
for similarities in the amino acid sequence of two proteins. Journal of Molecular
Biology, Vol. 48. Mar-1970. 443-453p.
[82] SMITH, T.F.; WATERMAN, M.S.; FITCH W.M. Comparative biosequence
metrics. Journal of Molecular Evolution, Vol. 18. 1981. 38-46p.
[83] SMITH, T.F.; WATERMAN, M.S. Identification of common molecular subsequences. Journal of Molecular Biology, Vol. 25. Mar-1981. 147:195p-7.
[84] SMITH, T.F.; WATERMAN, M.S. Overlapping genes and information theory.
Journal of Theory Biology, Vol. 91. 21-Jul-1981. 379-380p.
[85] SMITH, T.F.; WATERMAN, M.S. Comparison of biosequences. Adv. Appl.
Math., Vol. 2. 1981. 482-489p.
[86] WATERMAN, M.S. Frequencies of restriction sites. Nucleic Acids Research,
Vol. 11. 1983. 8951-8956p.
[87] WATERMAN, M.S. Sequence alignments in the neighborhood of the optimum
with general application to dynamic programming. Proc. Natl. Acad. Sci - USA,
Vol. 80. l983. 3123-3124p.
[88] WATERMAN, M.S.; EGGERT, M. A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons Journal of Molecular Biology, Vol. 197. 20-Oct-1987. 723-728p.
[89] CHAO, K.M.; HARDISON, R.C.; MILLER W. Recent developments in linearspace alignment methods: a survey. Journal of Comput. Biology, Vol. 1. Winter1994. 271-291p.
113
REFERÊNCIAS BIBLIOGRÁFICAS
[90] NUSSINOV, R. Efficient algorithms for searching for exact repetition of nucleotide sequences. Journal of Molecular Evolution. Vol. 19(3-4). 1983. 283-285p.
[91] GOTOH, O. An improved algorithm for matching biological sequences. Journal
of Molecular Biology, Vol. 15;162(3). Dec-1982. 705-708p.
[92] LIPMAN, D.J.; WILBUR, W.J.; SMITH, T.F.; WATERMAN, M.S. On the
statistical significance of nucleic acid similarities. Nucleic Acids Research, Vol.
12. 1984. 215-226p.
[93] GIBSON TOBY; RAMU, CHENNA; GEMÜND, CHRISTINE. BIOCCELERATOR at EMBL: Bioccelerator Web server by Sequence Analysis Service.
Heidelberg, Germany: European Molecular Biology Laboratory. Disponı́vel na
internet no endereço: http://eta.embl-heidelberg.de:8000/misc/mat/ em fevereiro/2005.
[94] ALTSCHUL, S.F. Amino acid substitution matrices from an information theoretic perspective. Journal of Molecular Biology, Vol. 219. 1991. 555-565p.
[95] THOMSEN, RENÉ; FOGEL, GARY B.;
provement
of
Clustal-Derived
nary Algorithms.
gress
1507pp.
on
Piscataway,
Evolutionary
Disponı́vel
na
Sequence
Alignments
with
Im-
Evolutio-
NJ: Proceedings of the 2003 Con-
Computation,
internet
KRINK, THIEMO.
no
IEEE
endereço:
Press.
2003.
1499-
http://www.natural-
selection.com/Library/2003/03CEC Improvement Clustal.pdf
em
ja-
neiro/2005.
[96] PINTO, ADRIANO KIYOSHI OGATA; DELBEM, ALEXANDRE CLÁUDIO
BOTAZZO. MULTIALINHAMENTO DE SEQÜÊNCIAS BIOLÓGICAS UTILIZANDO ALGORITMOS GENÉTICOS. Instituto de Ciências Matemáticas
e de Computação - Universidade de São Paulo: IX Simpósio de Teses e
Dissertações. 19 e 20-novembro-2004. Disponı́vel resumo na internet no endereço: http://www.icmc.usp.br/ std2004/Resumos/akogata alexandre.pdf em
janeiro/2005.
114
REFERÊNCIAS BIBLIOGRÁFICAS
[97] CHOUDHURY, RAHUL. Application of Evolutionary Algorithms for Multiple
Sequence Alignment. Computational Molecular Biology. Biochemistry 218/
Medical Information Sciences 231. 2003. Disponı́vel na internet no endereço:
http://cmgm.stanford.edu/biochem218/Projects%202003/choudhury.pdf
em
janeiro/2005.
[98] ISHIKAWA, M.; TOYA, T.; TOKOTI, Y. Parallel Iterative Aligner with Genetic Algorithm. Cambery - France: Artificial Intelligence and Genome Workshop
- 13th International Conference on Artificial Intelligence. 1993. 13-22p.
[99] NOTREDAME, CÉDRIC; HIGGINS, DESMOND G. SAGA: Sequence Alignment by Genetic Algorithm. Oxford University Press: Nucleic Acids Research.
1996. Vol. 24. No 8. 1515-1524p.
¯
[100] NOTREDAME, CÉDRIC; O’BRIEN, EMMET A.; HIGGINS, DESMOND
G. RAGA: RNA Sequence Alignment by Genetic Algorithm. Oxford University
Press: Nucleic Acids Research. 1997. Vol. 25. No 22. 4570-4580p.
¯
[101] ZHANG, C.; WONG, A. K. A Genetic Algorithm for Multiple Molecular
Sequence Alignment. Comput. Appl. Biosci. 1997. Vol. 13. 565-581p.
[102] GONZALEZ, R. R. Multiple Protein Sequence Comparison by Genetic Algorithms. SPI-98. 1999.
[103] CAI, L.; JUEDES, D.; LIAKHOVITCH, E. Evolutionary Computation Techniques for Multiple Sequence Alignmente. Congress on Evolutionary Computation. 2000. 829-835p.
[104] CHELLAPILLA, K.; FOGEL, G. B. Multiple Sequence Alignment Using Evolutionary Programming. Congress on Evolutionary Computation. 1999. 445452p.
[105] RIAZ, TARIQ; WANG, YI; LI, KUO-BIN.
Multiple Sequence Alignment
Using Tabu Search. Dunedin, New Zealand. Australian Computer Society Publisher. Second Asia-Pacific Bioinformatics Conference (APBC). Vol. 29. 18
115
REFERÊNCIAS BIBLIOGRÁFICAS
to 22-January-2004. 223-232p. ISBN 1-920682-11-2. Disponı́vel na internet no
endereço: http://crpit.com/confpapers/CRPITV29Riaz.pdf em janeiro/2005.
[106] THOMSEN, RENÉ; BOOMSMA, WOUTER. Multiple Sequence Alignment
Using SAGA: Investigating the Effects of Operator Scheduling, Population Seeding, and Crossover Operators. Applications of Evolutionary Computing, EvoBIO - 2o European Workshop on Evolutionary Bioinformatics. 2004. 113-122p.
¯
[107] YOKOYAMA, TSUTOMU; WATANABE, TAKUMI; TANEDA, AKITO;
SHIMIZU, TOSHIO. A Web Server for Multiple Sequence Alignment Using
Genetic Algorithm. Genome Informatics Series No 12. 17-december-2001. 382¯
383p. ISBN: Paper: 4-946443-72-X.
[108] NGUYEN, HUNG DINH; YOSHIHARA, IKUO; YAMAMORI, KUNIHITO;
YASUNAGA, MORITOSHI. Aligning Multiple Protein Sequences by Parallel
Hybrid Genetic Algorithm. Genome Informatics Series No 13. 13-december¯
2002. 123-132p. ISBN: Paper: 4-946443-79-7.
[109] NOTREDAME, CÉDRIC. Recent progresses in multiple sequence alignment:
a survey. Technology Report: Pharmacogenomics. Ashley Publications Ltd.
2002. ISSN: 1462-2416.
[110] NOTREDAME, CÉDRIC.
Utilisation des Algorithmes Genetiques pour
L’analyse de Sequences Biologiques. Université Paul Sabatier - France: Doctorat en Bio-informatique. Directeur De Thèse: Prof. François Amalric. Février1998.
[111] CHOI,
JEONG-HYEON;
KIM, SUN.
ches.
CHOI,
KWANGMIN;
CHO,
HWAN-GUE;
Multiple Genome Alignment by Clustering Pairwise Mat-
University of Bologna Residential Center Bertinoro (Forlı̀) - Ber-
tinoro - Italy:
2o RECOMB Comparative Genomics Satellite Workshop
¯
(RCG’04). 16-19 October 2004. Disponı́vel na internet no endereço:
http://platcom.informatics.indiana.edu/platcom/workgroup/Kwangmin.Choi/
publication/rcg2004.pdf em fevereiro/2005.
116
REFERÊNCIAS BIBLIOGRÁFICAS
[112] PRESTWICH, STEVEN; HIGGINS, DES; O’SULLIVAN, ORLA. PseudoBoolean Multiple Sequence Alignment.
University College Cork. Tenth
Workshop on Automated Reasoning. 2003. Disponı́vel na internet no endereço:
http://4c.ucc.ie/web/upload/publications/inProc/arw03.pdf ou arw03.ps em
fevereiro/2005.
[113] LUQUE, GABRIEL; ALBA, ENRIQUE; KHURI, SAMI. Assembling DNA
Fragments with a Distributed Genetic Algorithm. Seminars: Algoritmos Bioinspirados y Biocomputación. Universidad de Granada - España. 9-december2004. Disponı́vel na internet no endereço:
http://neo.lcc.uma.es/radi-
aeb/docs/sem10-Dic-04/doc4-1.pdf
[114] ZHONG, WEIWEI. Using Traveling Salesman Problem Algorithms to Determine Multiple Sequence Alignment Orders. University of Georgia - USA: Master
of Science. 2003.
117