Aplicando o problema do Caixeiro Viajante num … · Foi utilizado um algoritmo com a t´ecnica de branch and bound para resolver o problema. E conclu´ımos que a complexidade do

GABRIEL AUGUSTO GONCALVES SOBRAL

Aplicando o problema do Caixeiro Viajante num metodo de

construcao de Arvores Filogeneticas

CURITIBA

26 de Fevereiro de 2012

GABRIEL AUGUSTO GONCALVES SOBRAL

Aplicando o problema do Caixeiro Viajante num metodo de

construcao de Arvores Filogeneticas

Trabalho apresentado para conclusao do Curso

de Ciencia da Computacao da Universidade

Federal do Parana.

Orientador : Andre Luiz Pires Guedes.

CURITIBA

26 de Fevereiro de 2012

Resumo

O problema do caixeiro viajante tem varias aplicacoes praticas em areas multidisciplinares.Na biologia computacional ele pode ser aplicado a construcao de arvores filogeneticas. Nabiologia ela e usada para inferir informacoes sobre unidades de classificacao biologico. Uma desuas aplicacoes na genetica e determinar funcao e estrutura de sequencias.

O estudo da construcao de arvores filogeneticas vai desde o alinhamento de sequencias,funcoes de escore e o proprio problema em si. Fizemos uma serie de definicoes e problemasda biologia em termos computacionais. E a partir deles usamos solucoes computacionais jaconhecidas para resolve-los.

E tambem fizemos uma analise do algoritmo CircTree[1], que resolve o problema construcaode arvores filogeneticas. Ele usa em parte de sua solucao um algoritmo que resolve o problemado caixeiro viajante . Foi utilizado um algoritmo com a tecnica de branch and bound pararesolver o problema. E conclumos que a complexidade do problema do caixeiro viajante e quemdetermina a eficiencia do CircTree.

Palavras Chave : Caixeiro Viajante, Arvores Filogeneticas e Algoritmo.

Conteudo

Lista de Figuras

Lista de Tabelas

1 Introducao p. 7

2 Alinhamento de Sequencias p. 8

2.1 Alinhamento global . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 9

2.2 Funcoes de Escore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 14

2.2.1 Matriz de Escore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 14

2.3 Significado do resultado do Alinhamento . . . . . . . . . . . . . . . . . . . . . . p. 15

2.4 Alinhamento Multiplo de Sequencias(MSA) . . . . . . . . . . . . . . . . . . . . p. 16

2.4.1 Soma de Pares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 16

2.4.2 Soma circular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 17

3 Construcao de Arvores Filogeneticas p. 19

3.1 Problema de Construcao de Arvores Filogeneticas . . . . . . . . . . . . . . . . . p. 19

3.2 Relacao MSA e construcao de filogenia . . . . . . . . . . . . . . . . . . . . . . . p. 20

3.3 Ordem Circular e o problema do Caixeiro Viajante . . . . . . . . . . . . . . . . p. 22

4 Problema do Caixeiro Viajante p. 24

4.1 Ordem circular e instancias do caixeiro viajante . . . . . . . . . . . . . . . . . . p. 24

4.2 Algoritmo de Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . p. 25

4.2.1 Subdivisao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 25

4.2.2 Estrutura da Solucao Parcial . . . . . . . . . . . . . . . . . . . . . . . . p. 26

4.2.3 Metodos de Corte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 26

4.2.4 Algoritmo TSP-BB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27

4.2.5 Implementacao e testes do algoritmo TSP-BB . . . . . . . . . . . . . . . p. 28

5 Metodos Numericos para Construcao de Filogenias p. 30

5.1 Calculo da Matriz de Distancia . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 30

5.1.1 Atualizacao da Matriz de Distancia . . . . . . . . . . . . . . . . . . . . . p. 32

5.2 Usando ordem circular para determinar a topologia . . . . . . . . . . . . . . . . p. 33

5.2.1 Limite do erro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 34

5.3 Algoritmo CircTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 36

6 Conclusao p. 43

Referencias p. 46

Lista de Figuras

1 Matriz preenchida pelo algoritmo de alinhamento global . . . . . . . . . . . . . p. 11

2 Relacao do resultado do alinhamento com a distancia evolutiva . . . . . . . . . p. 15

3 Exemplo de Arvores Filogenetica . . . . . . . . . . . . . . . . . . . . . . . . . . p. 19

4 Uso da medida SP na arvore . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 21

5 Uso da medida CO na arvore . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 21

Lista de Tabelas

1 Exemplo de alinhamento entre duas sequencias. . . . . . . . . . . . . . . . . . . p. 8

2 Exemplo de Matriz de Similaridade . . . . . . . . . . . . . . . . . . . . . . . . . p. 14

3 Exemplo de matriz de distancia para soma circular . . . . . . . . . . . . . . . . p. 18

4 Burma14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 28

5 Ulysses16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29

6 Ulysses22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29

7 Distribuicao das arestas das instancias . . . . . . . . . . . . . . . . . . . . . . . p. 29

8 Matriz de MS para construcao de filogenia. . . . . . . . . . . . . . . . . . . . . p. 38

7

1 Introducao

A computacao tem um papel muito importante na biologia porque podemos usar problemas

computacionais para resolver problemas da biologia. E com isso criarmos programas de compu-

tador para melhorar uma tarefa, especialmente na area da genetica. Na computacao aplicada a

biologia a operacao dita como basica e o alinhamento de sequencias geneticas. E dela e possvel

extrair informacoes estruturais, como relacoes de parentesco.

Uma maneira de entender o funcionamento e estrutura das sequencias e compara-las por

um alinhamento. As arvores filogeneticas servem para agrupar as sequencias similares de forma

a terem um ancestral em comum. E a partir da arvore e que podemos inferir informacoes sobre

um conjunto de sequencias.

Iremos usar o problema computacional do caixeiro viajante para determinar a topologia de

uma arvore de um dado conjunto de sequencias. O estudo comeca por formalizar alguns conceitos

da biologia em termos computacionais. Depois sao estudados os problemas de alinhamento global

e multiplo de sequencias. A relacao entre o resultado dos alinhamentos com a topologia da arvore

e formulacoes do problema de construcao de arvores filogeneticas. Uma solucao para o problema

do caixeiro viajante usando a tecnica de bracnh and bound. E por fim um algoritmo que resolve o

problema de construcao de arvores filogeneticas usando as informacoes do alinhamento multiplo

de sequencias.

E e analisado do ponto de vista computacional a tratabilidade do problema usando o caixeiro

viajante, levando em conta o contexto biologico dele.

8

2 Alinhamento de Sequencias

O alinhamento de sequencias e uma operacao basica na biologia computacional pois a partir

dela e que podemos fazer uma serie de estudos. Desde o reconhecimento de regioes especficas

numa sequencia biologica ate a predicao de estrutura de uma protena. Iremos estuda-la porque

ela tambem e usada na construcao de arvores filogeneticas. Para isso iremos fazer uma serie de

definicoes[7], que seguem abaixo :

Definicao 1. Uma bio-sequencia e um sequencia s tal que s , onde pode ser =

{A,C, T,G} (DNA), = {A,C,U,G} (RNA) ou e o conjunto de todos os aminoacidos.

Uma observacao importante e que serao usada as palavras sequencia e cadeia como sinonimo

de bio-sequencia. Iremos considerar uma subsequencia por uma sequencia contida em outra.

Definicao 2. O alinhamento da sequencias s com s, denotado por a, a, e uma busca de uma

serie de caracteres por comparacao. Ela e feita por organizar as sequencias s, s em linhas. Isto

e, os aminoacidos sao alinhados ou posicionados nas colunas da seguinte forma. Quando eles

sao iguais, como A com A por exemplo, eles sao sempre alinhados na mesma coluna. Caso sejam

diferentes o alinhamento pode ser identificado como erro ou inserido um buraco, denotado por

. Um erro e alinhado em qualquer coluna e um buraco nunca alinha com outro.

No alinhamento nao e feito a combinacao A com T ou C com G. Na verdade procuramos

fazer a combinacao por aminoacidos iguais. Um buraco pode ser visto como uma lacuna, um

espaco entre as subsequencias dentro de uma sequencia. Ele pode ter sido originado pela insercao

ou remocao de uma base nucleotdea ou aminoacido. Abaixo temos um exemplo de alinhamento

entre duas sequencias s = AACG e s = TCG :

Tabela 1: Exemplo de alinhamento entre duas sequencias.s AACGs T CG

Definicao 3. A identidade entre dois elementos de sequencias distintas e a igualdade entre

bases ou aminoacidos numa determinada posicao das sequencias.

Com isso dizemos que uma sequencia s e similar a s se k% das bases ou aminoacidos de s

tem identidade com s. Onde k precisa ser um valor razoavel.

9

Definicao 4. Considere duas sequencias s e s pertencentes a com |s| = n, |s| = m e

i, j N, tal que 0 i < n e 0 j < m. A pontuacao do alinhamento de s[i] com s[j] e dado

por um esquema de pontuacao p. A pontuacao final do alinhamento e obtida pelas somas de

todas p(s[i], s[j]) e e denominada de pontuacao do alinhamento entre s e s.

Abaixo temos um exemplo de um esquema de pontuacao bem simples.

p(s[i], s[j]) =

k Z+ se s[i] = s[j]

k Z se s[i] 6= s[j]

k Z se s[i] = ou se s[j] =

Os valores de k, k e k sao ajustaveis de acordo com o seu estudo, e eles tambem sao

chamados de parametros[7]. Vale apena observar que existe varios esquemas de pontuacao que

podem ser desde funcoes, como mostrado acima, ate matrizes. Tendo em vista a definicao de

pontuacao de alinhamento vamos definir o que e um alinhamento otimo.

Definicao 5. Um alinhamento otimo entre as sequencias s e s e aquele que tem a pontuacao

maxima, ou maior similaridade.

Tendo em base os conceitos apresentados acima podemos estudar o problema de alinhamento

global de duas sequencias.

2.1 Alinhamento global

O alinhamento global tem por finalidade de obter a similaridade entre duas sequencias s e

s. Isto e, determinar o alinhamento otimo a, a entre s e s. E em termos computacionais

podemos formular o problema como :

Problema de Alinhamento Global

Instancia Dada duas bio-sequencias s, s e um esquema de pontuacao p.Pergunta Encontre um valor de pontuacao k para um alinhamento entre s e s tal

que k e maximo, ou seja o alinhamento otimo.

Iremos usar o algoritmo de Needleman-Wunsch[7, 10] para o estudo do problema de alinha-

mento global de sequencias, que e baseado no conceito de similaridade. O algoritmo utiliza a

tecnica de programacao dinamica para resolver o problema. A recursao que resolve os subpro-

blemas e feita a partir de tres possibilidades de alinhamento que sao :

O alinhamento de caracteres iguais ou diferentes de s[i] com s[j], ou vice-versa.

O alinhamento de s[i] com um buraco em s[j];

10

O alinhamento de s[j] com um buraco em s[i];

Como mostrado na definicao de pontuacao de alinhamento, podemos definir o esquema de

pontuacao por uma funcao, que e a seguinte :

p(s[i], s[j]) =

1 Z+ se s[i] = s[j]

1 Z se s[i] 6= s[j]

2 Z se s[i] = ou se s[j] =

Tendo em vista o valor do resultado dessas tres possibilidades, a que tiver maior pontuacao

e escolhida, por motivos de otimizacao. O caso base dessa recursao e o alinhamento de uma

sequencia com uma outra sequencia vazia. Esse e o caso em que atingimos uma das extremidades

da sequencia. E nele sao inseridos quantos buracos necessarios para igualar os tamanhos delas.

E importante dizer que solucao e construda de forma incremental e primeiro ndice para ambas

as sequencias e o 1. Com base nisso segue abaixo o algoritmo de Needleman-Wunsch :

Algoritmo 1: Sim(s, s)

Entrada: Duas bio-sequencias s e s, onde |s| = n e |s| = mSada: Uma matriz de A[m,n] com um ou mais alinhamentos otimosincio

para i 0 ate m facaA[i, 0] i2

fim

para j 0 ate n facaA[0, j] 02

fim

para i 1 ate m facapara j 1 ate n faca

A[i, j] max(A[i 1, j] 2, A[i 1, j 1] + p(s[i], s[j]), A[i, j 1] 2)fim

fim

retorna A[m,n]fim

A execucao do algoritmo acima gera uma matriz A[m,n], devido ao fato de usar programacao

dinamica para resolver o problema. Com relacao a sua estrutura podemos dizer que cada

elemento a[i, j] da matriz A[m,n] corresponde ao alinhamento de maior pontuacao na posicao

i e j. Os casos base estao nas posicoes a[0, j], com j ate n, e a[i, 0], com i ate m, valendo

respectivamente j 2 e i2.

Como o resultado e feito de forma incremental cada percurso na matriz corresponde a uma

possibilidade de alinhamento. Cada elemento a[i, j] de A[m,n] e calculado pelo maior valor das

tres possibilidades abaixo :

11

Alinhamento de s com s a[i 1, j 1] + p(s[i], s[j])

Alinhamento de em s a[i 1, j] 2

Alinhamento de em s a[i, j 1] 2

Por questoes de simplificacao iremos nos referir aos elementos de A[m,n] acima apenas

pelos seus ndices. Abaixo e mostrado o sentido de preenchimento da matriz, isto e, como sao

determinados os valores de a[i, j], onde a[i, j] = max(a[i 1, j], a[i, j 1], a[i 1, j 1]) :

Figura 1: Matriz preenchida pelo algoritmo de alinhamento global

Como o algoritmo de Needleman-Wunsch retorna uma matriz A[m,n], com os calculos dos

alinhamentos, precisamos extrair o resultado dela. E isso e feito pelo procedimento Alin(A, i,

j, s, s t)[7]. Os ndices i e j correspondem tanto a dimensao da matriz A quanto os tamanhos

das sequencias s e s, respectivamente. Isso significa que os ndices i e j devem ser inicializados

com os valores de n e m.

E por fim, o resultado de um dos alinhamentos otimos sao guardados nos vetores alin1 e

alin2. Ambos os vetores sao indexados por t e o seu valor e tambem o tamanho do resultado do

alinhamento. O preenchimento dos vetores alin1 e alin2 e feito recursivamente.

Na decida da recursao e feito um percurso na matriz A[m,n] para descobrir se ocorreu um

alinhamento entre caracteres ou caractere com buraco. A recursao comeca no ultimo elemento

da matriz que e a[m,n], e verifica qual tipo de alinhamento ocorreu. Isso e feito por analisar os

valores dos elementos da diagonal, linha e coluna de a[i, j] da seguinte forma :

1. O alinhamento de s[i] com buraco em s[j] ocorre se a[i, j] = a[i 1, j] 2(elemento da

mesma coluna de a[i, j]).

2. O alinhamento de s[i] com s[j] ocorre se a[i, j] = a[i 1, j 1] + p(s[i], s[j])(elemento da

diagonal de a[i, j]).

3. O alinhamento de buraco em s[i] com s[j] ocorre se a[i, j] = a[i, j 1] 2(elemento da

coluna de a[i, j]).

Os testes acima sao aplicados na ordem que estao e eles indicam como e feito o percurso na

matriz A[m,n]. A base da recursao e quando chegamos no elemento a[0, 0]. O percurso indica,

12

de tras pra frente, como o alinhamento foi realizado para cada elemento das duas sequencias.

Na volta da recursao preenchemos os vetores alin1 e alin2 correspondendo com os alinhamentos

entre s e s. Como e possvel fazer mais de um percurso, e retorna apenas um deles, que

corresponde a um alinhamento otimo[7]. Abaixo segue o algoritmo Alin(A, i, j, s, s, t) :

Algoritmo 2: Alin(A, i, j, s, s, t)

Entrada: Recebe uma matriz A com os alinhamento entre duas sequenciasSada: Um alinhamento otimo entre duas sequencias em alin1 e alin2incio

se i = 0 e j = 0 entaot 0

senao se i > 0 e a[i, j] = a[i 1, j] 2 entaoAlin(A, i 1, j, s, s, t)t t+ 1alin1[t] s[i]alin2[t]

senao se i > 0 e j > 0 e a[i, j] = a[i 1, j 1] + p(s[i], s[j]) entaoAlin(A, i 1, j 1, s, s, t)t t+ 1alin1[t] s[i]alin2[t] s

[j]

senao se j > 0 e a[i, j] = a[i, j 1] 2 entaoAlin(A, i, j 1, s, s, t)t t+ 1alin1[t] alin2[t] s

[j]

fim

fim

Vamos a um exemplo para entender melhor como o algoritmo de alinhamento global funci-

ona. Para isso considere duas sequencias s e s que sao s = AAC e s = AC.

A C

Preenchimento do caso base.0 -2 -4

A -2A -4C -6

A CAlinhando s[1] com s[1]. Onde as possibilidades de pontuacao dosalinhamentos sao : A[0, 0] = 0 + p(s[1], s[1]) = 0 + 1 = 1,A[0, 1] = 2 2 = 4, A[1, 0] = 2 2 = 4

0 -2 -4A -2 1A -4C -6

13

A CAlinhando s[1] com s[2]. Onde as possibilidades de pontuacao dosalinhamentos sao : A[0, 1] = 2 + p(s[1], s[2]) = 2 1 = 3,A[0, 2] = 4 2 = 6, A[1, 1] = 1 2 = 1

0 -2 -4A -2 1 -1A -4C -6


0 -2 -4A -2 1 -1A -4 -1C -6


0 -2 -4A -2 1 -1A -4 -1 0C -6


0 -2 -4A -2 1 -1A -4 -1 0C -6 -3


0 -2 -4A -2 1 -1A -4 -1 0C -6 -3 0

E importante observar que as sequencias foram indexadas a partir de 1. Enquanto os

elementos da matriz sao indexados a partir do ndice 0. E o valor do alinhamento otimo na

posicao i, j esta em negrito.

Apesar de um dos alinhamento otimo retornado pelo algoritmo de Needleman-Wunsch ser

A C, temos outro alinhamento com a mesma pontuacao que e AC. Do ponto de vista

biologico o segundo alinhamento seria o mais adequado. Pois buracos nas extremidades indicam

que uma sequencia era maior do que a outra, ou vice-versa. Enquanto que buracos no meio de

uma sequencia significa divergencias entre elas. A maneira de fazer com que o algoritmo prefira

o segundo ao primeiro alinhamento e por modificar o esquema de pontuacao, que sera abordado

na secao de Funcoes de Escore.

Com relacao a complexidade de tempo do algoritmo Sim(s, s)[7], as partes de inicializacao

da matriz, que e o preenchimento dos casos base, levam (n) e (m). Ja no calculo do res-

tante da matriz e proporcional ao tamanho dela que e de O(mn), tanto para o espaco quanto

para complexidade de tempo. No pior caso, que seria a maior matriz possvel para m e n, a

complexidade e de O(n2). Existem algumas otimizacoes para reduzir o espaco requerido pelo

algoritmo, por utilizar a tecnica de dividir e conquistar. Mas para a finalidade de estudar a

construcao de arvore filogeneticas conhecer o algoritmo de Needleman-Wunsch ja e o suficiente,

sobre alinhamento global.

14

2.2 Funcoes de Escore

As funcoes de escore sao usadas nos esquemas de pontuacao com a finalidade de pontuar o

alinhamento. Como mostrado anteriormente ela pode ser definida de uma maneira bem simples

como uma funcao[7], por exemplo. Apesar desse metodo apresentar resultados interessantes ele

tem alguns problemas. Um exemplo disso e no alinhamento entre AAC com AC onde dois

alinhamentos otimos possveis sao : AAC com A C ou AAC com AC. Do ponto de

vista biologico o segundo e mais interessante por nao mutilar a sequencia. Para deixar a funcao

de escore p mais precisa considere as modificacoes[7] abaixo :

Nao penalizar buracos na extremidade das sequencias.

Penalizar os buracos de dois pontos de vista :

Insercao de um buraco;

Estender um buraco ja existente.

Agora a penalizacao de buracos e dada pela expressao a + lb [1], aonde a e o valor para

inserir um buraco, b e penalidade para estende-lo e l e o seu tamanho. Alem das tradicionais

funcoes de escore1 temos outros esquemas de pontuacao que levam em consideracao a troca de

uma base ou aminoacido por outro, elas sao chamadas de Matriz de Escore[10, 8].

2.2.1 Matriz de Escore

Foi observado que as funcoes de escore acabam por nao levar em conta as propriedade fsico-

qumicas, por penalizar igualmente as trocas de uma base ou aminoacido por outro[10]. E por

isso foram desenvolvidas as matrizes de escore. Dentre elas temos a matriz de similaridade que

pontua uma troca de uma base da linha i pelo o da coluna j, quanto maior o escore melhor e o

alinhamento. Abaixo temos um exemplo dela :

Tabela 2: Exemplo de Matriz de SimilaridadeA G C T

A 10 -1 -3 -4G -1 7 -5 -3C -3 -5 9 0T -4 -3 0 8

Alem das matrizes similaridade existem tambem as matrizes de substituicao que descrevem

a taxa de substituicao de aminoacidos ou bases ao longo do tempo. Elas sao baseadas na taxa

de substituicao tanto de bases ou aminoacidos por outros e servem para descrever a distancia

1Tambem e possvel usar distancia de edicao mas os seus resultados sao equivalentes[7].

15

evolutiva. Existem basicamente duas matrizes que sao a BLOSUM e PAM[10, 7, 6]. Os escores

produzidas por elas sao o contrario da matriz de similaridade, isto e, quanto menor o escore

melhor o alinhamento.

A matriz PAM e uma matriz probabilstica baseada na hipotese de que as mutacoes2 sao

reversveis. Isso significa que para uma dada sequencia e possvel fazer mutacoes e obter a

sua sequencia ancestral. Por exemplo, considere as sequencias s e s, a comparacao entre

elas implica que existe uma sequencia ancestral s. Alem disso podemos realizar mutacoes a

partir de s ate obter s ou s. E importante observar que a distancia de e simetrica, pois

segundo a hipotese, de mutacao reversvel, e possvel obter s de s e depois s de s. A distancia

entre s e s e calculada por primeiro computar uma matriz -PAM e depois normaliza-la.

O indica que sao esperados mutacoes para transformar s em s numa certa quantidade

de aminoacidos3. A matriz e indexada pelos aminoacidos tanto na linha quanto na coluna,

indicando a comparacao para cada par. A distancia final e o resultado das somas dos escores de

cada alinhamento. A matriz PAM pronta para calculo do alinhamento pode ser obtida do site

http://www.bioinformatics.nl/tools/pam.html.

A matriz BLOSUM e baseada em alinhamentos locais onde foi estimado probabilidade de

substituicao de aminoacidos em determinadas regioes. Uma matriz ser BLOSUM significa que

os blocos observados sao menor de de identidade.

2.3 Significado do resultado do Alinhamento

Um alinhamento serve para determinar a funcao, estrutura e informacoes evolutivas sobre

sequencias. E o quanto mais similar uma sequencia for da outra a probabilidade que elas tenham

funcoes semelhantes e grande[10]. Alem disso o escore do alinhamento entre s e s pode ser

interpretado como uma relacao de parentesco. Isto e uma sequencia ancestral s que foi sofrendo

insercoes e remocoes de aminoacidos, ou bases, ate dar origem as sequencias s e s[10, 6].4

Figura 2: Relacao do resultado do alinhamento com a distancia evolutiva

2As mutacoes consideradas sao aquelas selecionadas pela selecao natural[10].3Quando = 1 a taxa e de 100 aminoacidos, para valores maiores essa taxa e aumentada4Essa e a ideia da distancia evolutiva.

http://www.bioinformatics.nl/tools/pam.html

16

2.4 Alinhamento Multiplo de Sequencias(MSA)

O problema de alinhamento multiplo de sequencias tem uma grande relacao com a cons-

trucao de arvores filogeneticas. Pois o seu resultado e usado para obter as informacoes necessarias

para constru-la[5, 6]. Basicamente a relacao entre os dois problemas esta na ordem em que as

sequencias sao alinhadas. Tendo em vista o problema de alinhamento global de sequencias vamos

generaliza-lo para termos mais de duas sequencias como entrada do problema. E iremos deno-

tar o alinhamento de mais uma sequencia por [[a0, a1, . . . , an1]] onde ai corresponde a i-esima

sequencia alinhada.

Problema de Alinhamento Multiplo de Sequencias

Instancia Dado uma colecao de sequencias S = (s0, s1, . . . , sl2, sl1) e um es-quema de pontuacao P .

Pergunta Encontre um alinhamento multiplo MS = [[a0, a1, . . . , an1]] dassequencias de S tal que P (MS) e otimo.

Um problema e avaliar o alinhamento entre as sequencias. Antes com apenas duas bastava

encontrar o alinhamento global otimo entre elas. Como agora temos mais de duas sequencias,

precisamos de um metrica P que diga qual e o melhor alinhamento considerando o melhor

alinhamento de cada uma com todas[4]. As funcoes de escore para alinhamento multiplo de

sequencias[4, 5, 6] servem para otimizar o escore de MS , que e formado pelos escores de cada

ai, aj. Podemos fazer isso por pontuar cada par de sequencias que e a sum of pairs. Ou

determinar um valor de uma ordem em que as sequencias sao alinhadas que e a circular sum.

2.4.1 Soma de Pares

A soma de pares[4, 5, 6], sum of pairs, consiste na soma de cada par do alinhamento

multiplo MS , de um conjunto de sequencias S. Isto e, para cada par ai, aj e a calculado por

um esquema de pontuacao p, assim como foi feito no problema de alinhamento global. Abaixo

temos a conta[4, 5, 6] para computar a soma de pares de um alinhamento multiplo :

SP (MS) =

n1

i=0

n1

j>i

p(ai, aJ)

Para mostrar como SP e calculada vamos considerar um exemplo com um conjunto de

sequencias S = (s0 = AAC, s1 = AC, s2 = AGC, s3 = TC), um esquema de pontuacao p onde

caracteres iguais e 1 e caso contrario e 0. Seja o alinhamento multiplo MS = [[a0, a1, a2, a3]] ,

17

calculamos SP (MS) por :

Somando os escores de a0 para os demais alinhamentos

a0 : AAC

a1 : AC p(a0, a1) = 2

a2 : AGC p(a0, a2) = 2

a3 : T C p(a0, a3) = 13

j>0

p(a0, aj) = 5


a1 : AC

a2 : AGC p(a1, a2) = 1

a3 : T C p(a1, a3) = 13

j>1

p(a1, aj) = 2


a2 : AGC

a3 : T C p(a2, a3) = 13

j>2

p(a2, aj) = 1

Somando os resultados temos SP (MS) = 5 + 2 + 1 = 8.

2.4.2 Soma circular

A soma circular[4, 5, 6], circular sum, e feita a partir de uma estrutura chamada de ordem

circular. Uma ordem circular e basicamente um percurso em que as sequencias sao visitadas

numa arvore, onde as suas folhas sao as sequencias. Esse percurso e determinada por um caminho

que comeca numa determinada sequencia, vai percorrendo as demais ate voltar a inicial. A soma

circular dessa ordem e computada da seguinte forma[4, 5, 6] :

CS(MS) =1

2

n1

i=0

p(aCi , aCi+1) onde aCn = aC0

Denotamos aCi pela i-esima sequencia da ordem circular C ou C(T ) numa arvore T . E

CS(MS) pela soma circular de um alinhamento multiplo MS de um conjunto de sequencias S.

Vamos usar um exemplo para mostrar como a soma circular e computada, para isso considere

arvore T abaixo, a matriz de distancia entre cada folha e a ordem circular C(T ) = A,B,C,D

18

:

Tabela 3: Exemplo de matriz de distancia para soma circularA B C D

A 0 2 8 10B 2 0 11 13C 8 11 0 3D 10 13 3 0

Iremos usar a matriz de distancia acima como esquema de pontuacao, onde p(aCi , aCi+1) =

valor da linha i pela coluna i+ 1. Com isso temos que a soma circular e :

CS(MS) = 1/2(p(A,B) + p(B,C) + p(C,D) + p(D,A)) = 1/2(26) = 13

19

3 Construcao de Arvores Filogeneticas

As arvores filogeneticas ou filogenias servem para descrever as relacoes evolutivas, sejam elas

sobre especies ou sequencias de aminoacidos[7, 10, 8]1. Alem de construir a historia evolutiva

ela e um meio de comparar unidades de mesma classificacao biologica. E determinar as suas

funcionalidades e estrutura que e um fato bastante util no estudo de sequencias de aminoacidos.

Abaixo temos um exemplo de um arvore filogenetica.

Figura 3: Exemplo de Arvores Filogenetica

A estrutura da arvore pode ser vista como uma arvore binaria[7, 10] onde as folhas sao as

sequencias, ja conhecidas, e os nos internos sao os ancestrais. E importante observar que um

ancestral pode ser conhecido ou nao, pois nao temos toda a historia evolutiva de um taxon2.

3.1 Problema de Construcao de Arvores Filogeneticas

Na construcao de uma arvore filogenetica temos basicamente dois metodos[7]. Um deles que

usa uma matriz de caractersticas em que cada linha representa um conjunto de caractersticas,

tendo ela dois ou mais valores possveis. E outro que usa dados numericos representando os

valores dos resultados dos alinhamentos entre sequencias, e nesse contexto sera chamado de

distancia. Podemos ter arvores com raiz ou nao, mas estaremos considerados a montagem de

1Na verdade sobre qualquer unidade de classificacao, isto e, unidade taxonomica.2E uma unidade taxonomica, ou seja, uma unidade de classificacao biologica.

20

arvores com raiz. Formalmente podemos definir arvore filogenetica e o problema de construcao

de filogenias por[1] :

Definicao 6. Uma arvore filogenetica e uma arvore binaria T = (V,E), onde V sao os vertices

e E as arestas. O conjunto L e subconjunto de V e denota todas as folhas de T . Uma arvore T

formada pelo conjunto de folhas L e denotado por T (L).

Problema de Construcao de Arvores Filogeneticas

Instancia Dado um conjunto S com n unidades taxonomicas.Pergunta Existe uma arvore onde todos os elementos de S sao folhas.

Acima esta formulado o problema geral de construcao de arvores filogeneticas. Como es-

tamos usando metodos numericos podemos atribuir valores as arestas da arvore. E com isso

podemos dizer que o valor de uma arvore T e a soma de todas as suas arestas. Formulando o

problema do ponto de vista numerico temos :

Problema de Construcao de Arvores Filogeneticas para metodo numerico

Instancia Dado um conjunto S com n unidades taxonomicas.Pergunta Existe uma arvore onde todos os elementos de S sao folhas tal que a

soma das arestas de T (S) e mnima.

3.2 Relacao MSA e construcao de filogenia

O resultado de um alinhamento multiplo esta extremamente ligado ao problema de cons-

trucao arvores filogeneticas[1, 10, 4]. Pois e necessario saber quais sequencias sao mais proximas

das outras. Assim agrupando as sequencias mais semelhantes e determinando as relacoes de

parentesco.

Como visto anteriormente temos duas medidas que auxiliam na construcao de um alinha-

mento multiplo que sao a SP e CS. Agora vamos analisa-las do ponto de vista evolutivo. Para

isso vamos observar a ordem em que as sequencias sao agrupadas para calcular cada medida.

Consideremos entao um conjunto de sequencias S = (A,B,C,D,E) e a arvore T (S) abaixo :

Se para cada par de sequencia agrupada pelo SP fizermos um traco em cada aresta que ele

visita teremos a seguinte arvore resultante :

21

Figura 4: Uso da medida SP na arvore

Acima esta representado, na arvore, cada etapa do calculo ate o final da metrica SP. Do

ponto de vista evolutivo nao existe justificativa para diferentes ramos da arvore serem visitados

mais vezes do que outros. E por isso o metodo SP e considerado ineficiente[1, 4]para dar o escore

do MSA e construir filogenias. Devido a esse fato foi criado a ordem circular, circular order, e

podemos defini-la por[1] :

Definicao 7. Uma ordem circular C(T ) de um conjunto de sequencias S e qualquer tour numa

arvore T (S), tal que cada aresta e percorrida duas vezes, e cada sequencia uma unica vez. Uma

ordem circular e denotada por C(T ) = sC0 , sC1 , . . . , sCn1.

No exemplo abaixo uma ordem circular em T (S) seria C(T ) = A,B,C,D, e temos o

seguinte resultado :

Figura 5: Uso da medida CO na arvore

Isso significa que comecamos o percurso da C(T ) no no A, passamos para B, depois C, ate

chegar a D e voltar ao no A. Do ponto de vista evolutivo a ordem circular e um metodo melhor

para construir arvores filogeneticas, pois visita cada uma das arestas duas vezes. Isso significa

que da a mesma relevancia para todos os eventos evolutivos[10, 1]. Podemos definir o problema

de encontrar a ordem circular como sendo[5, 4] :

Problema de Encontrar uma Ordem Circular

Instancia Dado uma arvore T (S) formada pelo conjunto S com n sequencias e asdistancias

(|S|2

), onde elas sao obtidas por um esquema de pontuacao p.

Pergunta Existe uma ordem C(T ) tal que cada s S e visitado uma unica vez. Etoda aresta do tour formado pela C(T ) e visitada duas vezes.

Um fato importante de uma ordem circular e que ela e o menor percurso numa arvore[4, 1].

Para demostrar esse fato, primeiro vamos considerar uma arvore T com duas folhas. E facil de

22

verificar que existe apenas um unico percurso em que todas as arestas sao visitadas duas vezes,

pois apenas uma aresta que liga as duas folhas. Com isso obrigando o menor percurso, entre as

duas folhas, passar pela aresta duas vezes, fazendo o caminho de ida e volta.

Agora considere T uma arvore com n nos. Podemos subdividir T , em qualquer ponto, em

subarvores. Sejam Ta, Tb subarvores de T , x uma aresta que conecta Ta a Tb e a ordem circular

C = l, . . . , i, . . . , j, . . . , k nas folhas mais a direita l, j e mais a esquerda i, k, respectivamente,

de Ta e Tb.

Ao realizarmos o percurso C a aresta x e visitada duas vezes. Pois samos de Ta para Tb e

voltamos de Tb para Ta, passando por x novamente. Logo como divisao em subarvores pode ser

feita em qualquer lugar. Entao podemos subdividir, em subarvores, Ta e Tb de forma a verificar

que os caminhos de C, nas novas subarvores, sao percorridos da mesma forma que samos de Ta

para Tb e voltamos de Tb a Ta, fazendo uma ordem circular. Portanto nao existi um percurso

menor na arvore T do que a ordem circular C em T , visitando todas as folhas e todas arestas

duas vezes.

Com esse resultado temos que se C e uma ordem circular incorreta entao ela passa por uma

aresta mais de duas vezes[4, 1]. Pois considerando a mesma subdivisao de uma arvore T em

Ta e Tb. Ao realizarmos o percurso desta ordem circular C = l, . . . , j, . . . , i, . . . , k podemos

verificar que fazermos duas idas e voltas entre Ta e Tb. E consequentemente passando por x

quatro vezes. Portanto uma ordem circular incorreta C visita pelo menos uma aresta quatro

vezes.

3.3 Ordem Circular e o problema do Caixeiro Viajante

A relacao entre o problema de encontrar a ordem circular e o caixeiro viajante esta no tour

que e feito nas folhas da arvore. Se considerarmos um conjunto de sequencias S e uma arvore

T (S), em que cada par de distancia s, s S representa a distancia total entre s e s. Isto e, o

valor de todo percurso de s passando por nos internos ate s. Entao as distancias(|S|2

)formam

um grafo que representa os percursos entre as folhas.

Iremos denotar o ciclo hamiltoniano de menor custo por Amin. Se resolvermos o caixeiro

viajante tendo como instancia um grafo G com o conjunto de vertices sendo S e as arestas por(|S|2

). Temos entao um Amin em G que e, a princpio, contem os menores percursos entre as

23

folhas de S. E como a menor distancia de s para qualquer outra s representa o menor percurso

na arvore T (S)[4]. Entao Amin em G nos garante que contem o menores percursos em T (S),

passando por todas as folhas S. E como sao os menores percursos logo visitamos todas as aresta

de T (S) duas vezes, entao teramos uma ordem circular.

Na verdade precisamos de mais um fato para afirmarmos que Amin realmente e uma ordem

circular correta. Mas, por enquanto, iremos considerar que Amin e uma ordem circular correta,

ou seja, visita todas as folhas S e cada aresta de T (S) duas vezes.

24

4 Problema do Caixeiro Viajante

O problema do caixeiro viajante e tradicionalmente definido por um conjunto de cidades

com distancias, ou custo, entre cada par delas. O objetivo e encontrar o tour de menor custo

visitando todas as cidades, apenas uma unica vez, e retornando a cidade inicial. Em termos

computacionais podemos definir o problema do caixeiro viajante por[3] :

Problema do Caixeiro Viajante

Instancia Dado um grafo completo G = (V,E) e uma funcao custo : E Z+.Pergunta Encontrar um circuito hamiltoniano X de G tal que custo(X) =

eE(X) custo(e) e mnimo.

Ao observar as instancias do problema podemos classifica-las de acordo com as restricoes

estabelecidas entre as distancias das cidades[2]. Da maneira como esta formalizado o problema,

dizemos que ele e o caso geral. Pois nao estabelecemos nenhuma restricao com relacao as

distancias das cidades. As instancias simetricas[2] sao aquelas em que para qualquer par de

cidades v, u V a distancia de v para u e a mesma de u para v. Nesse caso fizemos uma

restricao nas instancias do caso geral impondo uma condicao de simetria entre elas. Tambem

temos os casos das instancias assimetricas[2] e TSP [2], onde as distancias satisfazem a

desigualdade triangular.

4.1 Ordem circular e instancias do caixeiro viajante

Como vimos anteriormente existe uma relacao entre os problema de encontrar ordem circular

e o caixeiro viajante. Agora vamos formalizar essa relacao de forma a demonstrar que existem

instancias comuns aos problemas. Isto e, transformar uma instancia do problema de encontrar

uma ordem circular numa do caixeiro viajante, e isso sera feito por uma reducao[9].

Vamos usar a tecnica de restricao[9] para demonstrar que o problema de encontrar ordem

circular contem instancias do caixeiro viajante como caso especial. Ou seja, vamos impor res-

tricoes as instancias do problema da ordem circular ate obtermos as do caixeiro viajante.

Tendo em vista que o tour da ordem circular e feito nas folhas da arvore. E como as distancias

entre as sequencias, que forma uma matriz de distancia, tem a propriedade de representar a

25

distancia total entre elas[5]. Logo se temos um grafo formado pelas sequencias e as distancias

entre cada par delas. Entao se impormos a restricao que todo ciclo hamiltoniano nas folhas gera

uma topologia correta na arvore filogenetica. Temos uma ordem circular pois para cada folha

do ciclo precisamos passar por duas arestas na arvore, devido a ido e sada de um no. E como

precisamos voltar a primeira sequencia entao todas as arestas da arvore sao visitadas duas vezes.

Portanto a restricao e que todo ciclo hamiltoniano de custo mnimo gere uma topologia correta

na arvore formada por um conjunto de folhas.

Com esse resultado podemos dizer que as instancias da ordem circular sao identificadas

como instancias simetricas do caixeiro viajante, pois a distancia do alinhamento e simetrica. A

partir disso podemos usar as formalidades ja conhecidas[2, 3, 9] para determinar que os vertices

representam as cidades e as arestas as distancias. Para resolver o problema do caixeiro viajante

iremos estudar uma solucao usando um algoritmo de branch and bound [3].

4.2 Algoritmo de Branch and Bound

Iremos usar algoritmo recursivo que usa a tecnica de branch and bound para resolver o

problema do caixeiro viajante. Ao usar a tecnica de branch and bound precisamos mostrar

como e feita a subdivisao do espaco de busca, estrutura da solucao parcial e metodos de corte.

A princpio vamos considerar que uma solucao parcial X contem as arestas do grafo que podem

formar uma solucao, isto e, colecao de arestas que podem formar um ciclo hamiltoniano de custo

mnimo.

4.2.1 Subdivisao

Antes de falarmos como e feita a subdivisao, iremos determinar qual e o espaco de busca[3]

do problema. O espaco de busca do problema do caixeiro viajante sao as colecoes de arestas tal

que formam um ciclo que percorre todos os vertices uma vez. A subdivisao sera feita baseada

na decisao de uma aresta pertencer ou nao a solucao. Isso significa que existe duas chamadas

recursivas, uma aonde uma determinada aresta e inserida em X e outra em que ela e removida

do grafo.

Na verdade a aresta nao e removida do grafo. Inicialmente temos uma lista A0 com todas

as arestas disponveis para escolha, que e inicializada com todas arestas do grafo. A lista A0

e colocada em ordem nao decrescente de peso das arestas. Pois se a solucao e o menor ciclo

hamiltoniano entao, a princpio, ela seria formada pelas arestas mais leves. E e da lista A0

que removemos a aresta. Como a cada chamada recursiva uma aresta e removido da lista.

Entao precisamos computar a lista Al usada no proximo passo da recursao, e isso e feito por

Al aAl1.

26

Ao inserir arestas uma determinada aresta em X seus vertices sao colapsados, isto e, o

no colapsado e formado pelos nos da extremidade da aresta. Quando colapsamos vertices eles

podem estar em qualquer lugar do grafo e com isso sao formadas componentes conexas em G[X].

Desse modo os nos vao sendo colapsados com outros formando conjuntos de aresta inicialmente

disjuntos. Ate chegar num ponto em que esses conjuntos de aresta sao colapsados, na verdade

unidos, ate compor a solucao final.

Antes de inserir uma aresta em X precisamos verificar se ela nao fecha ciclo, a nao ser que

seja a ultima. Ou se forma algum vertice de grau maior do que dois. Como as arestas da solucao

podem estar ou nao conexas entao teremos de realizar os testes nas componentes conexas geradas

pelo grafo induzido por X. Isso significa que precisamos de uma estrutura mais elaborada em

X para fazer os testes em tempo praticavel.

4.2.2 Estrutura da Solucao Parcial

A estrutura de X alem de ter uma lista de arestas ela deve ter uma estrategia para verificar

se uma aresta fecha ciclo ou nao, pois esse teste sera feito com bastante frequencia. Como,

inicialmente, as arestas formam conjuntos disjuntos e ao seus vertices serem colapsados chega

num ponto que esses conjuntos vao se unindo ate compor a solucao final. A estrategia adotada

pelo algoritmo TSP-BB e usar union and find para fazer as buscas de arestas, que serve para os

testes, e a uniao dos conjuntos disjuntos de arestas em X.

4.2.3 Metodos de Corte

Os metodos de corte[3] usado sao divididos em funcao de bound e restricoes a lista A. A

funcao de bound e baseado na estimativa do valor atual de X mais o peso das primeiras arestas

em A que faltam para X completar a solucao. Abaixo esta descrito em termos matematicos a

estimativa da funcao de bound e o algoritmo que a computa :

xX

custo(x) +k1

l=0

custo(al) , onde k = |X| e al A

27

Algoritmo 3: Bound(X, A)

Entrada: Uma solucao parcial X e uma lista Al ordenada em ordem crescente dos pesosSada: Uma estimativa do custo de menor ciclo a partir de Xincio

CustoX

xX custo(x) k |X|m |E(G)|

CustoAmk1

i=0 airetorna CustoA + CustoX

fim

A restricao imposta a lista A e com relacao a quantidade mnima de arestas para fechar

um ciclo, que seria n arestas. Entao para continuar calculando uma solucao parcial ela deve

satisfazer a condicao |X|+ |A| n. E tambem que o valor de Bound(X) deve ser menor do que

a ultima solucao encontrada.

4.2.4 Algoritmo TSP-BB

O algoritmo TSP-BB tem basicamente tres etapas que sao : otimizacao, cortes e subdivisao

do espaco de busca. A otimizacao so ocorre quando |X| = n o que significa que e uma solucao

completa. E nesse caso e verificado se o CustoX, que e a soma das arestas de X, e menor do

que uma solucao ja encontrada. E se for menor os valores da solucao completa sao atualizados.

O valor de CustoOtimo e inicializado com o valor do Bound(A0).

Os metodos de corte sao aplicados a cada no da arvore gerada pela recursao do algoritmo.

Primeiro e verificado se ainda ha arestas disponveis para fechar um ciclo. Depois e testado o

valor de bound e caso seu valor seja maior do que a solucao completa e cortado. Iremos usar a

funcao Elimina que recebe uma aresta, solucao parcial X, um grafo G e retorna verdadeiro se a

aresta fecha ciclo em G[X] ou tem vertices de grau maior do que dois em G[X]. Caso contrario

e retornado falso, abaixo segue a funcao Elimina :

Algoritmo 4: Elimina(a,X,G)

Entrada: Recebe uma aresta a, solucao parcial X e um grafo GSada: Retorna verdadeiro caso a nao fecha ciclo ou forma vertices com grau maior do

que dois em G[X], caso contrario e falsoincio

se |X| < n entaoretorna verdadeiro

fim

se a+X forma vertice de grau maior do que dois ou fecha ciclo em G[X] entaoretorna verdadeiro

fim

retorna falsofim

28

Na ultima etapa do algoritmo e feita a subdivisao do espaco de busca. Onde a primeira

recursao corresponde a aresta inserida em X. E a segunda e quando ela e eliminada do grafo e

nao entra em X.

Algoritmo 5: TSP(G = (V , E), X,A)

Entrada: Recebe um grafo completo G = (V , E)Sada: Um ciclo hamiltoniano X de custo mnimoincio

se |X| = n entaoCustoX =

xX custo(x)

se CustoX < CustoOtimo entao

CustoOtimo CustoX

SolucaoOtimo X

fim

fim

se |A|+ |X| < n entaoretorna

fim

B Bound(X,A)

se B CustoOtimo entaoretorna

fim

se Elimina(a,X,G) e falso entaoTSP(G, X + al,A al)

fim

TSP(G, X,A al)retorna X

fim

4.2.5 Implementacao e testes do algoritmo TSP-BB

O algoritmo TSP-BB foi implementado e avaliado o seu desempenho com relacao ao tempo

de execucao e cortes feitos. O TSP-BB foi implementado em python e os testes foram realizado

num computador com a seguinte especificacao : Pentium(R) Dual-Core CPU E5300 2.60GHz

de clock com 2048 Kb de cache e sistema operacional GNU/Linux Debian 5.0.4. As instancias

para o programa foram obtidas do TSPLIB e abaixo seguem os resultados dos testes.

Tabela 4: Burma14Tempo de Execucao 0,2094 Nos visitados 8689

Tempo do Bound 63,9292% Corte do Bound 8,1597%

Tempo de entrar em X 1,6151% Corte por tamanho 0,0115%

29

Tabela 5: Ulysses16Tempo de Execucao 0,02679 Nos visitados 105


Tempo de entrar em X 0,3497% Corte por tamanho 0,0%

Tabela 6: Ulysses22Tempo de Execucao 0,3992 Nos visitados 9959


Tempo de entrar em X 3,3618% Corte por tamanho 0.0%

Foi realizado tambem um estudo da distribuicao dos valores das arestas. Nele determinamos

o valor mnimo, maximo, medio e desvio padrao das arestas de cada instancia. Abaixo temos a

tabela com as informacoes sobre as instancias usadas nos testes do TSP-BB.

Tabela 7: Distribuicao das arestas das instanciasInstancia Mnimo Maximo Media Desvio Padrao

burma14 0,23 11,2146 4,4079 2,2684

ulysses16 0,3833 31,5536 8,9325 6,5242

ulysses22 0,0894 31,5536 8,2697 6,1323

Podemos verificar que o algoritmo tem um bom desempenho quando a diferenca entre os

valores de maximo e mnimo nao sao muito grandes. Isto e, essa diferenca nao ultrapassa a

media ou o desvio padrao. Uma distribuicao que e favoravel a heurstica usada e quando a

media e alta e boa parte das arestas estao no primeiro e segundo quartil. Isso mostra que e

necessario avaliar melhor a distribuicao das arestas.

30

5 Metodos Numericos para Construcao

de Filogenias

A construcao de arvores filogeneticas por metodos numericos tem por objetivo constru-la

sem saber a sua topologia. A ideia e determinar a sua topologia usando uma matriz de distancia

e uma ordem para juntar as sequencias. Alem disso a construcao da arvore e feita de forma

a minimizar o seu custo, isto e, minimizar a soma das arestas da arvore. Isso implica num

resultado mais consistente dela.

Basicamente o processo de montar a arvore e determinar qual sequencia e mais similar a

outra e junta-las. Isso significa que existe uma relacao de parentesco entre elas representada por

uma subarvore, onde as sequencias sao as folhas e o pai uma sequencia ancestral. Dizemos que

dois nos estao conectados se eles sao filhos do mesmo pai. As sequencias juntadas sao vistas

como se fossem uma so1 e o numero de sequencias e reduzido. O passo de juntar as sequencias

mais similares e repetido ate que tenhamos apenas o numero de sequencias igual a um. Isso

significa que todas as sequencias foram agrupadas segundo a sua similaridade e a topologia da

arvore determinada.

5.1 Calculo da Matriz de Distancia

Uma matriz de distancia D e obtida inicialmente a partir do alinhamento multiplo de um

conjunto de sequencias S, de tamanho n. E ela possui a seguinte estrutura :

di,j > 0 para i 6= j

di,j = 0 para i = j

di,j = dj,i para todo i, j

di,j di,k + dk,j para todo i, j, k (desigualdade triangular)

Cada elemento di,j e inicializado com os valores do resultado de [[a0, . . . , an1]]. E de acordo

com que os nos da arvore sao juntados os valores dos elementos di,j sao atualizados, representado

1A distancia dela para as demais e feita pela media das distancias.

31

o valor do caminho2 de si a sj . Segundo a definicao[5] abaixo dizemos que a matriz D e aditiva

quando :

Definicao 8. Seja D uma matriz simetrica de tamanho n n onde os numeros na diagonal

sao zeros e os fora dela sao estritamente positivos. Seja T um arvore com arestas valoradas

pelas distancias de D, com pelo menos n nos, onde os n nos distintos de T sao indexados pelas

linhas de D. A arvore T e dita um arvore aditiva para a matriz D se para todo par de nos i, j

o caminho de i a j tem o peso ou distancia total exatamente de di,j.

Isso significa que cada di,j representa a soma de todas as distancias das arestas que sao

percorridas ao sair do no si e ir ate o sj . O fato de D ser aditiva nos garante a seguinte

propriedade[5] :

di,j + dk,l = di,k + dj,l

nos nao conectados na mesma subarvore

di,l + dj,k

nos conectados na mesma subarvore

onde i, j, k, l sao elementos de D

(5.1)

Essa propriedade e conhecida como four point condition e mostra que o caminho entre dois

nos conectados3 e menor do que a de dois nos nao conectados .Para mostrar que ela(5.1) e valida,

considere a arvore T abaixo :

Vamos considerar os percursos, em ordem circular, das folhas i, l, k e j das respectivas

subarvores A, B, C, D. Efetuando os calculos das distancias entre cada no da arvore temos :

di,k = a+ x+ d dj,l = c+ x+ b

di,j = a+ x+ c dk,l = d+ x+ b

di,l = a+ b dj,k = c+ d

E fazendo as devidas substituicoes obtemos o seguinte resultado :

di,j + dk,l = a+ x+ c+ d+ x+ b = 2x+ di,l + dj,k

di,k + dj,l = a+ x+ d+ c+ x+ b = 2x+ di,l + dj,k

2Na arvore T .3Isso significa que numa arvore dados os nos a e b, eles estao numa subarvore aonde o pai e ab e os filhos sao

a e b.

32

Portanto se a propriedade (5.1) e satisfeita ela garante que um caminho entre dois nos

conectados e menor igual do dois no nao conectados. Caso contrario para dois nos conectados

de T seria possvel trocar um dos nos por um outro nao conectado e conseguir um caminho mais

curto. Isso implicaria numa aresta de peso negativo o que e impossvel, pois todo os elemento

de D sao nao negativos. E alem disso estaria desrespeitando a propriedade da desigualdade

triangular de D.

E importante observar um fato sobre as parcelas da conta da equacao(5.1). As duas primeiras

parcelas di,j +dk,l e di,k+dj,l correspondem a percursos na arvore T de nos nao conectados. E a

ultima parcela di,l + dj,k a um percurso em T de nos conectados. Alem disso as duas primeiras

parcelas representam a troca de nos conectados por nos nao conectados resultando num custo

de caminho igual a 2x + di,l + dj,k. Isso significa que a para um par de nos conectados a troca

por outro nao conectado faz aumentar o custo do caminho em pelo menos 2x.

5.1.1 Atualizacao da Matriz de Distancia

Iremos mostrar como os valores da matriz D sao atualizados ao juntar dois nos. Para isso

vamos considerar a matriz de distancia D abaixo :

A B C DA 0 8 6 14B 8 0 10 16C 6 10 0 12D 14 16 12 0

Vamos supor que iremos juntar os nos A e C e a partir de agora iremos nos referir a ele

como no AC. Agora precisamos calcular as distancias de AC para os demais nos que sera feita

pela media das distancias de A e C para os outros nos, abaixo e mostrado como a conta e feita.

AC B D Os calculos sao feitos da seguinte forma :

dB,AC =dB,A+dB,C

2 =8+62 = 7 dD,AC =

dD,A+dD,C2 =

14+122 = 13

AC 0 7 13B 7 0 16D 13 16 0

Supondo que vamos juntar os nos AC com B temos abaixo a atualizacao da matriz D :

ACB D Os calculos sao feitos da seguinte forma :

dD,ACB =dD,A+dD,C+dD,B

3 =14+16+12

3 = 14ACB 0 14D 14 0

Apesar de serem atualizados os valores da matriz D ainda temos de ter uma matriz auxiliar

com o valores iniciais de D. Pois precisam ser consultados para computar os novos valores dos

elementos de D.

Ao atualizar os valores de D tambem determinamos os valores dos ramos da arvore. O valor

33

para cada ramo e dado pela distancia di,j/2 ao juntar o no si com o sj . A arvore T obtida da

matriz D usada no exemplo acima e a seguinte :

ACBD

ACB

3,5

AC

0,5

A

3

C

3

B

3,5

D

7

5.2 Usando ordem circular para determinar a topologia

Uma maneira de determinar a ordem em que as sequencias sao agrupadas e por usar a

ordem circular. Pensando nas possveis topologias de uma arvore T formada pelo conjunto de

sequencias S. Ao determinar uma ordem circular C(T ) estamos encontrando um percurso em

T que, a princpio, contem as arestas de menor peso4. Isso significa que estamos minimizando

as distancias entre as sequencias e com isso construindo uma arvore mais precisa, ou seja ,

minimizando possveis erros.

Um problema de construir uma arvore a partir de um conjunto de sequencias e a existencia

de erros R, e esses erros estao presente em :

Distancia entre sequencias como a distancia obtida de uma pequena amostra e uma protena

e codificada pois mais de uma sequencia. Existe uma variacao no valor da distancia que e

dita como erro.

Modelo Evolutivo e o modelo que descreve os processos de substituicao de aminoacidos ao

longo do tempo, usado em matrizes de substituicao como a PAM. E como evolucao e um

processo aleatorio acaba tendo um erro.

Com base nisso iremos determinar um valor de erro de forma conseguirmos obter uma ordem

circular correta.

4Isso e uma heurstica pois acredita-se que um ciclo hamiltoniano mnimo deve conter as arestas de menor peso

34

5.2.1 Limite do erro

Numa ordem circular o erro esta presente no calculo da distancia entre si e sj e sera

representado por i,j + i,j , onde e a i,j distancia de si, sj e i,j o seu erro correspondente. O

limite de erro em que estamos interessados e o menor erro possvel de forma a obtermos uma

ordem circular incorreta. Isto e, uma ordem que visita uma determinada aresta mais de duas

vezes. Iremos considerar subarvore Tu de T por uma arvore com V V e E E, onde u e a

raiz e todos os caminhos diretos de u das folhas de T estao em Tu tambem.

Como queremos determinar o menor erro possvel entao vamos considerar x sendo a aresta

mais curta, menor distancia entre duas sequencias, e uma subarvore Tude T . Sejam C =

A,B,C,D, C = A,D,B,C duas ordens circulares e a subarvore Tu abaixo :

Se C e uma ordem circular invalida entao passa por x quatro vezes. E como C e uma

ordem circular correta entao a soma das arestas de C deve ser maior do que C . Pois C visita

x no maximo duas vezes, obrigando o a passar por uma aresta mais pesada do que x. Logo a

inequacao abaixo deve ser satisfeita :

A,B + B,C + C,D + D,A > A,D + D,B + B,C + C,A (5.2)

Adicionando os erros na equacao (5.2) temos os seguinte resultado :

A,B + A,B + B,C + B,C + C,D + C,D + D,A + D,A >

A,D + A,D + D,B + D,B + B,C + B,C + C,A + C,A

Fazendo as devidas simplificacoes temos :

A,B + A,B + C,D + C,D C,A C,A D,B D,B > 0 (5.3)

Como A,C = C,A e aplicando a propriedade four point condition(5.1) resulta em :

A,C + D,B = A,D + C,B = 2x+ A,B + C,D A,B + C,D

35

Fazendo as modificacoes na equacao(5.3) obtemos o seguinte resultado :

A,B + A,B + C,D + C,D (C,A + D,B) C,A D,B > 0

A,B + A,B + C,D + C,D (A,B + C,D + 2x) C,A D,B > 0

A,B + C,D 2x C,A D,B > 0

A,B + C,D C,A D,B > 2x

Entao se a soma dos valores absolutos dos erros for menor de 2x. Isto e, para qualquer

erro i,j ele deve ser menor dex2 para obtermos uma ordem circular correta. Portanto esse e o

limite de erro aceitavel num calculo correto da distancia entre duas sequencias.

A fim de determinar de determinar uma topologia de T (S) a partir de uma C(T ) precisamos

saber se dois nos estao conectados ou nao. Para isso vamos observar o resultado da seguinte

equacao sobre as distancias de D :

A,C + D,B = 2x+ A,B + C,D (5.4)

A primeira parcela da equacao(5.4) corresponde a caminhos entre nos nao conectados, A

a C ou D a B,resultando numa ordem circular incorreta. Enquanto que na segunda parcela

A,B + C,D e uma ordem circular correta, e os nos A e B sao conectados, assim como C e D.

Alem disso podemos observar que a troca de um nos do par de nos conectados por outro nao

conectado resulta num aumento de 2x no custo do caminho.

Com base na observacao acima vamos definir uma funcao dp(sCi) que determina se as

sequencias sCi e sCi+1 estao conectados ou nao. Para isso fazendo algumas modificacoes na

equacao(5.4) temos o seguinte :

A,C + D,B = 2x+ A,B + C,D

A,C + D,B A,B C,D = 2x

A,B + C,D A,C D,B = 2x (5.5)

A equacao acima e zero apenas se os nos B e C sao conectados, caso contrario o seu valor

e 2x. Fazendo os devidos calculos para dp(B) e dp(A) observamos que :

A,B + C,D A,C D,B = a+ b+ c+ d (a+ x+ c) (d+ x+ b) =

a a+ b b+ c c+ d d 2x = 2x

D,A + B,C D,B A,C = a+ x+ d+ b+ x+ c (b+ x+ d) (a+ x+ c) =

a a+ b b+ c c+ d d+ 2x 2x = 0

36

Enumerando as sequencias na conta acima podemos definir dp(sCi) por :

dp(sCi) = sCi1 ,sCi + sCi+1 ,sCi+2 sCi1 ,sCi+1 sCi ,sCi+2 (5.6)

Iremos usar a funcao dp para determinar quais nos estao conectados. Como estamos in-

teressados em saber qual e a melhor conexao a ser feita. Todos os resultados dos dp nos nos

da arvore serao analisados. E aquele dp(sCi) que tiver o menor valor tera os nos sCi e sCi+1

juntados. Como os valores de dp sao distancias e usado o valor absoluto delas.

Sabemos que quando dp(sCi) e zero logo os nos sCi e sCi+1 estao conectados. Mas como

estaremos determinando a topologia da arvore e as distancias representam o percurso total de

uma sequencias a outra. Nao temos os valores exatos de cada ramo da arvore pois faltam os

nos intermediarios, que dividem o valor delas ao meio. E por isso e provavel que inicialmente

os valores de dp nao seja zero para nos conectados. Devido a isso o dp que tiver o menor valor

e dito como a melhor conexao entre dois nos.

Com relacao aos valores de i, caso ele seja negativo o seu valor e dado por (n i) mod n. E

se seu valor for maior do que o numero de sequencias n o valor de i e i mod n.

5.3 Algoritmo CircTree

O algoritmo CircTree[1] tem as seguinte etapas : obtencao de uma ordem circular, calculo

dos valores de dp(sCi) e determinar qual no sera juntado.

Para obter a ordem circular iremos usar uma matriz distancias obtida do resultado de um

alinhamento multiplo de uma colecao de sequencias. Lembrando que as distancias sao os valores

dos alinhamentos usando uma matriz de substituicao, como a PAM. Os valores dos elementos

da diagonal dessa matriz, distancia de uma sequencias para si mesma, tem o valor , apesar de

seus valores inicialmente serem zero. Isso e feito a fim de obter um resultado correto ao usa-la

com instancia do caixeiro viajante.

A colecao de arestas retornada pelo algoritmo, que resolve o problema do caixeiro viajante, e

usada para determinar a ordem circular. Para entender como isso e feito considere um conjunto

de arestas X = {{A,B}, {B,C}, {C,A}}. Entao para determinarmos a ordem circular a partir

de uma colecao de arestas basta pegar o primeiro elemento de uma aresta para compor um das

sequencias da ordem circular. O segundo elemento da aresta e usado para procurar a aresta que

o contem como primeiro. Ao encontra-la, novamente escrevemos o primeiro elemento na ordem

circular. E assim por diante ate que todas as arestas do conjunto tenham sido visitadas. Nesse

caso se pegarmos {A,B} X escrevemos A e a proximo aresta escolhida e {B,C}, resultando

em A,B. E por fim {C,A} tendo a ordem circular A,B,C.

37

A partir da ordem circular vamos rearranjar as sequencias baseado nessa ordem. Isto e,

gerar uma lista de sequencias ordenadas pela ordem circular. E isso e feito pela funcao rearranja

que recebe um conjunto de sequencias S, uma ordem circular C e retorna a lista ordenada L.

Como vamos determinar a topologia da arvore filogenetica usando a ordem circular, preci-

samos fazer os calculos dos dp(sCi) para descobrir quais nos estao conectados. Para agilizar o

processo, todos os dp(sCi) sao calculados e guardados numa lista D juntamente com um ndice

i, que indexa a lista L.

Sabemos que a melhor conexao entre dois nos e aquela que tiver o menor valor de dp. E

devido a isso a lista D e ordenada em ordem nao decrescente. De forma que o primeiro elemento

de D seja o menor valor da lista, e consequentemente a melhor conexao.

A estrutura que guarda a topologia da arvore e inicializada apenas com as folhas L. Os

nos que devem ser juntados sao obtidos da primeira posicao da lista D. Isto e, iremos usar

D[0] para denotar que estamos pegando o ndice i de [dp(i), i] na primeira posicao da lista D.

O ndice i indexa as sequencias na ordem circular, ou seja, sCi . E com isso as sequencias sCi

e sCi+1 sao juntadas pela funcao join. Apos as sequencias serem juntadas um no ancestral e

adicionado e sao atualizados os valores de matriz de distancia e a lista D. Esse passo e repetido

ate determinarmos a topologia da arvore, abaixo temos o algoritmo CircTree.

Algoritmo 6: CircTree(S, MS)

Entrada: Um conjunto de sequencias S e sua matriz de distancia MS .Sada: Uma arvore de valor otimo Topt.incio

C TSP (S,MS)L rearranja(S, C)Topt L

Fmin n1

i=0 p(sCi , sCi+1)D [ ]n |L|para i 1 ate n faca

D D [dp(i), i]fim

D ordena(D)para k 1 ate n 1 faca

i D[0]Topt[i] join(Topt[i], Topt[i+ 1])D D \D[0]Atualizar os valores de MSRecalcular os valores de DD ordena(D)

fim

retorna Toptfim

38

Vamos ao um exemplo para ver como o algoritmo CircTree funciona. Para isso considere o

conjunto de sequencias S = {s0, s1, s2, s3} e a matriz de distancia de um alinhamento multiplo

de S :

Tabela 8: Matriz de MS para construcao de filogenia.s0 s1 s2 s3

s0 0 5 20 22s1 5 0 18 16s2 20 18 0 4s3 22 16 4 0

Vamos comecar por resolver o problema do caixeiro viajante usando como instancia S,

matriz MS e o algoritmo TSP-BB, para resolve-lo.

Passo : 0

A = [{s2, s3} = 4; {s0, s1} = 5; {s1, s3} = 16; {s2, s1} = 18; {s0, s2} = 20; {s0, s3} = 22]

X = [ ]

s0 s1

s2 s3

X {s2, s3} A {s2, s3}

Passo : 1

A = [{s0, s1} = 5; {s1, s3} = 16; {s2, s1} = 18; {s0, s2} = 20; {s0, s3} = 22]

X = [{s2, s3} = 4]

s0 s1

s2 s3

X {s0, s1} A {s0, s1}

Passo : 2

A = [{s1, s3} = 16; {s2, s1} = 18; {s0, s2} = 20; {s0, s3} = 22]

X = [{s2, s3} = 4; {s0, s1} = 5; ]

39

s0 s1

s2 s3

X {s1, s3} A {s1, s3}

Passo : 3

A = [{s2, s1} = 18; {s0, s2} = 20; {s0, s3} = 22]

X = [{s2, s3} = 4; {s0, s1} = 5; {s1, s3} = 16; ]

s0 s1

s2 s3

A aresta {s2, s1} nao pode ser includa em X pois fecha ciclo, A {s2, s1}

Passo : 4

A = [{s0, s2} = 20; {s0, s3} = 22]

X = [{s2, s3} = 4; {s0, s1} = 5; {s1, s3} = 16; ]

s0 s1

s2 s3

X {s0, s2} A {s0, s2}

Passo : 5

A = [{s0, s3} = 22]

X = [{s2, s3} = 4; {s0, s1} = 5; {s1, s3} = 16; {s0, s2} = 20; ]

s0 s1

s2 s3

CustoX = 4+5+16+20 = 45 e OptX = [{s2, s3} = 4; {s0, s1} = 5; {s1, s3} = 16; {s0, s2} =

40

20; ].

Passo : 6

A = [{s0, s3} = 22]

X = [{s2, s3} = 4; {s0, s1} = 5; {s1, s3} = 16]

s0 s1

s2 s3

A aresta {s0, s3} nao pode ser includa em X pois fecha ciclo, A {s0, s3}

Passo : 7

A = [{s2, s1} = 18; {s0, s2} = 20; {s0, s3} = 22]

X = [{s2, s3} = 4; {s0, s1} = 5]

s0 s1

s2 s3

Corte por bound pois : 4 + 5 + 18 + 20 = 47 > 45

Passo : 8

A = [{s1, s3} = 16; {s2, s1} = 18; {s0, s2} = 20; {s0, s3} = 22]

X = [{s2, s3} = 4]

s0 s1

s2 s3


Passo : 9

A = [{s0, s1} = 5; {s1, s3} = 16; {s2, s1} = 18; {s0, s2} = 20; {s0, s3} = 22]

X = [ ]

41

s0 s1

s2 s3


Com isso temos que a solucao e OptX = [{s2, s3} = 4; {s0, s1} = 5; {s1, s3} = 16; {s0, s2} =

20; ], CustoX = 45 e a ordem circular e C = s2, s3, s1, s0.

Rearranjando o conjunto S baseado na ordem circular C temos :

s2 e agora s0

s3 e agora s1

s1 e agora s2

s0 e agora s3

Com isso temos que lista de folhas e L = [s0, s1, s

2, s

3] e a matriz de distancia e :

s0 s1 s

2 s

3

s0 0 4 18 20s1 4 0 16 22s2 18 16 0 5s3 20 22 5 0

Agora vamos faze os calculos dos dp para compor a lista D.

dp(s0) = s3,s0 + s1,s2 s3,s1 s0,s2 = 20 + 16 22 18 = | 4| = 4

dp(s1) = s0,s1 + s2,s3 s0,s2 s1,s3 = 4 + 5 18 22 = | 31| = 31

dp(s2) = s1,s2 + s3,s0 s1,s3 s2,s0 = 16 + 20 22 18 = | 4| = 4

dp(s3) = s2,s3 + s0,s1 s2,s0 s3, s

1 = 5 + 4 18 22 = | 31| = 31

D = [(0, dp(s0) = 4), (2, dp(s2) = 4), (1, dp(s

1)) = 31, (3, dp(s

3) = 31)]

Com isso temos que a melhor conexao e juntar os nos s0 e s1, adicionando o no ancestral

s01.

42

Recalculando os valores da matriz e da lista D.

s01 s2 s

3

s01,s

2=

s0,s2+s

1,s2

2 =18+16

2 s01,s3 =s

0,s3+s

1,s3

2 =20+22

2 = 21s01 0 17 21s2 17 0 5s3 21 5 0

dp(s01) = s3,s01 + s2,s3 s3,s2 s01,s3 = 21 + 5 5 21 = 0

dp(s2) = s01,s2 + s3,s01 s01,s3 s2,s01 = 17 + 21 21 17 = 0

dp(s3) = s2,s3 + s01,s2 s2,s01 s3,s2 = 5 + 17 17 5 = 0

D = [(2, dp(s2) = 0), (01, dp(s01) = 0), (3, dp(s

3) = 0))]

Com isso temos que a melhor conexao e juntar os nos s2 e s3, adicionando o no ancestral

s23.

E como temos apenas dois nos restantes vamos juntar s01 ao no s23 resultando na arvore

abaixo :

Ao analisar a complexidade de tempo do algoritmo CircTree observamos que determinar a

ordem circular e O(2n), onde n = |S|. Rearranjar as sequencias de acordo com a ordem circular

leva (n). Ao calcular pela primeira vez os dp para a lista D e (n). E de acordo com que os

nos vao sendo juntados o calculo de D e O(n), pois a cada no agrupado um dp a menor precisa

ser calculado. O tempo da atualizacao dos valores da matriz e tambem de O(n).

E por fim, como precisamos de n 1 passos para juntar os nos. Logo o tempo total de

junta-los e de O(n2). E como o tempo de complexidade de determinar a ordem circular e muito

maior do que os demais. Portanto o algoritmo CircTree leva tempo de O(2n).

43

6 Conclusao

Vamos analisar como foi aplicado o problema do caixeiro viajante na construcao de arvores

filogeneticas. E verificar se a solucao do problema, o algoritmo CircTree, e praticavel em termos

computacionais.

A parte principal de resolver o problema de construcao de arvores filogeneticas, sem saber

a sua topologia, e a ordem em que os nos sao juntados. A ordem circular nos garante um menor

tour na arvore, isto e, um percurso que passa por todas as folhas e visita todas as arestas duas

vezes. Entretanto, so temos conseguimos alguma informacao sobre a topologia da arvore ao

trocar dois nos e observar o novo valor do percurso entre eles. E com base nesse resultado juntar

ou nao os nos.

O problema do caixeiro viajante e usado para determinarmos a ordem circular pelos seguintes

motivos. Tendo as sequencias como vertices e arestas sendo cada parde distancias entre elas.

A solucao do caixeiro viajante visita todos os vertices, e analogamente podemos ver o ciclo

hamiltoniano, de custo mnimo, como o menor tour entre as folhas da arvore.

Inicialmente consideramos que todo ciclo hamiltoniano de custo mnimo entre as folhas da

arvore gera uma topologia correta dela. Essa premissa pode ser feita pois em ambos os problemas

todos os elementos precisam ser visitados e temos de voltar ao primeiro, no fim do ciclo.

Com relacao as visitas das arestas, como num ciclo hamiltoniano de custo mnimo todos

os vertices tem grau dois. Isso acontece porque tenho de usar uma aresta para chegar num

vertice e outra para sair dele. A garantia de que o ciclo visita todas as arestas duas vezes pode

ser verificado da seguinte forma. Considere tres sequencias consecutivas numa ordem circular

si, sj , sh e que precisamos determinar a topologia entre elas. Inicialmente temos as arestas

{si, sj}, {sj , sh}, {sh, si} e ao adicionarmos nos intermediarios elas sao divididas em duas. Ou

seja, se sij e um no intermediario de si a sj entao o percurso anteriormente era feito por {si, sj}

e agora e {si, sij}, {sij , sj}. Adicionando o no intermediario sijh ao conectar os nos sij e sh

podemos verificar que todas as arestas sao visitadas duas vezes. Ao fazer o percurso dado pelo

ciclo {si, sj}, {sj , sh}, {sh, si} com os intermediarios adicionados o tour agora e feito por :

44

{si, sij}, {sij , sj},

{si,sj}

{sj , sij}, {sij , sijh}, {sijh, sh},

{sj ,sh}

{sh, sijh}, {sijh, sij}, {sij , si}

{sh,si}

Podemos generalizar esse caso simplesmente por adicionar mais folhas a ordem circular. E

por colocar os nos intermediarios assim como foi feito acima. E portanto todo ciclo hamiltoniano

de custo mnimo gera uma topologia de uma arvore e consequentemente e uma ordem circular

tambem.

O ciclo mnimo de uma solucao do caixeiro viajante garante que o percurso na arvore seja

mnimo por pegar as arestas de menor distancia de um vertice ao outro. Uma aresta da solucao

representa na arvore o percurso total de uma folha a outra. Ao minimizar os valores das arestas

implica num menor percurso da arvore. Isso e importante pois quanto menor a distancia entre

as sequencias mais similares elas sao, garantindo um resultado correto tendo em vista o contexto

biologico.

Vamos dividir em estagios o algoritmo CircTree para analisarmos em termos de complexidade

computacional. O algoritmo tem basicamente tres etapas, obter a ordem circular, preparacao

para montar a arvore e montagem propriamente dita. A ordem circular e obtida por uma

solucao do caixeiro viajante, tendo como instancia o conjunto de folhas e a distancia entre cada

par delas. Tendo em vista a reducao que foi feita, podemos afirmar que leva tempo de O(2n)

para determina-la, onde n e o tamanho do conjunto de sequencias.

O estagio de preparacao para montar a arvore e quando rearranjamos o conjunto de folha L,

fazemos os calculos para a lista D e o ordenamos. As duas primeiras atividades levam tempo de

(n) e a ordenacao de D, no pior caso, e O(n lgn). O que resulta num tempo total de O(n lgn).

E o ultimo estagio que e a montagem da arvore, temos uma repeticao que e executada n1

vezes. E dentro dela temos as seguinte operacoes : juntar os nos, atualizar os valores de D e MS

e ordenar D. A parte de juntar os nos e O(1), atualizacoes dos valores tanto de D e de MS e

(n), considerando uma matriz triangular. E novamente a ordenacao de D e O(n lgn). E com

isso o tempo final do terceiro estagio e de O(n2 lg n), no pior caso.

Fazendo a conta do tempo do algoritmo CircTree, usando os valores dos resultados de

cada estagio, podemos ver que ele leva tempo O(2n), pois determinar a ordem circular tem

maior complexidade. Isso significa que o tempo do algoritmo CircTree e determinado pelo do

caixeiro viajante, o que o tornaria impraticavel com instancias de tamanho grande. Entretanto

a distribuicao dos valores das distancias e fundamental para o algoritmo TSP-BB, o que pode

permitir instancias com tamanhos razoaveis.

Devido a heurstica usada, podemos convergir para a solucao rapidamente em alguns casos.

Quando temos desvio padrao pequeno ou quando a diferenca entre a menor a e maior distancia e

45

grande. Com relacao a outra distribuicoes de valores nao foi testado a convergencia da solucao.

A vantagem de atingir logo a solucao otima, ou proxima dela, e a quantidade de cortes por

bound feita e consequentemente reduz o tempo de execucao.

Portanto, baseado nos resultados acima, podemos dizer que o algoritmo CircTree usando

uma solucao exata do caixeiro viajante e praticavel apenas com instancias nao muito grandes,

em torno de 25 sequencias. Um estudo futuro seria ver como se comporta o tempo de execucao

do algoritmo CircTree com conjuntos de sequencias de diferentes distribuicoes de distancias.

[]

46

Referencias

[1] Gaston H. Gonnet Chantal Korostenky. Using travelling salesman problem algorithms forevolutionary tree construction. Bioinformatics, 16(7):619627, Julho 2000.

[2] Vasek Chvatal David L. Applegate, Robert E. Bixny. The Traveling Salesman Problem: AComputational Study, pages 1 56. Princeton University Press, 2006.

[3] Douglas R. Stinson Donald L. Kreher. Combinatorial Algorithms: generation, enumerationand search. CRC Press on discrete mathematics and its applications, 1998.

[4] Steve Benner Gaston H. Gonnet, Chantal Korostensky. Evaluation measures of multiplesequence alingments. Journal of Computational Biology, 7(1/2):261276, Fevereiro 2000.

[5] Dan Gusfield. Algorithms on Strings, Trees and Sequences, pages 447 479. CambridgeUniversity Press, 1997.

[6] Finn Rosenbech Jensen. Using the traveling salesman problem in bioinformatics algorithms.Masters thesis, Aarhus University, 2010.

[7] Joao Carlos Setbubal Joao Meidanis. Uma introducao a Biologia Computacional, pages552. Imprenssa UFPE, 1994.

[8] Arthur M. Lesk. Introduction to Bioinformatics. OXFORD, 2005.

[9] David S. Johnson Michael R. Garey. Computers and Intractability: A Guide to the Theoryof NP-Completeness. W. H. Freeman and Company, 1979.

[10] David W. Mount. Bioinformatics Sequence and Genome Analysis. Cold Spring HarborLaboratory Press, 2001.

Lista de FigurasLista de TabelasIntroduoAlinhamento de SequnciasAlinhamento globalFunes de EscoreMatriz de Escore

Significado do resultado do AlinhamentoAlinhamento Mltiplo de Sequncias(MSA)Soma de ParesSoma circular

Construo de rvores FilogenticasProblema de Construo de rvores FilogenticasRelao MSA e construo de filogeniaOrdem Circular e o problema do Caixeiro Viajante

Problema do Caixeiro ViajanteOrdem circular e instncias do caixeiro viajanteAlgoritmo de Branch and BoundSubdivisoEstrutura da Soluo ParcialMtodos de CorteAlgoritmo TSP-BBImplementao e testes do algoritmo TSP-BB

Mtodos Numricos para Construo de FilogeniasClculo da Matriz de DistnciaAtualizao da Matriz de Distncia

Usando ordem circular para determinar a topologiaLimite do erro

Algoritmo CircTree

ConclusoReferncias

Documents

Aplicando o problema do Caixeiro Viajante num … · Foi utilizado um algoritmo com a t´ecnica de branch and bound para resolver o problema. E conclu´ımos que a complexidade do