guilherme-taborda-ribas

Prévia do material em texto

UNIVERSIDADE FEDERAL DO PARANÁ
GUILHERME TABORDA RIBAS
TACOS: AVALIAÇÃO DE ÁRVORES FILOGENÉTICAS
CURITIBA
2021
GUILHERME TABORDA RIBAS
TACOS: AVALIAÇÃO DE ÁRVORES FILOGENÉTICAS
Dissertação apresentada como requisito parcial à ob-
tenção do grau de Mestre em Bioinformática no Pro-
grama de Pós-Graduação em Bioinformática, Setor de
Educação Profissional e Tecnológica da Universidade
Federal do Paraná.
Orientador: Dieval Guizelini
Coorientador: Roberto Tadeu Raittz
CURITIBA
2021
DADOS INTERNACIONAIS DE CATALOGAÇÃO NA PUBLICAÇÃO (CIP)
UNIVERSIDADE FEDERAL DO PARANÁ
SISTEMA DE BIBLIOTECAS – BIBLIOTECA DE EDUCAÇÃO PROFISSIONAL E TECNOLÓGICA
_______________________________________________________________
R482t Ribas, Guilherme Taborda
TACos: avaliação de árvores filogenéticas / Guilherme Taborda Ribas.
– dados eletrônicos. – Curitiba, 2021.
1 arquivo (97 f.) : PDF.
Requisitos do Sistema: Adobe Acrobat Reader
Modo de acesso: World Wide Web
Orientador: Dieval Guizelini
Coorientador: Roberto Tadeu Raitz
Dissertação (mestrado) – Universidade Federal do Paraná, Setor de
Educação Profissional e Tecnológica, Programa de Pós-graduação em
Bioinformática.
1. Bioinformática. 2. Filogenia. 3. Sequenciamento de nucleotídeos. 4.
Análise por conglomerados. 5. Software - Desenvolvimento. I. Guizelini,
Dieval. II. Raitz, Roberto Tadeu. III. Universidade Federal do Paraná.
Programa de Pós-Graduação em Bioinformática. IV. Título.
CDD : 572.860285
________________________________________________________________
Bibliotecária: Thays Luciana Barbosa de Farias CRB-9/1995
MINISTÉRIO DA EDUCAÇÃO
SETOR DE EDUCAÇÃO PROFISSIONAL E TECNOLÓGICA
UNIVERSIDADE FEDERAL DO PARANÁ
PRÓ-REITORIA DE PESQUISA E PÓS-GRADUAÇÃO
PROGRAMA DE PÓS-GRADUAÇÃO BIOINFORMÁTICA -
40001016066P4
TERMO DE APROVAÇÃO
Os membros da Banca Examinadora designada pelo Colegiado do Programa de Pós-Graduação em BIOINFORMÁTICA da
Universidade Federal do Paraná foram convocados para realizar a arguição da Dissertação de Mestrado de GUILHERME
TABORDA RIBAS intitulada: "TACos: Avaliação de Árvores Filogenéticas", sob orientação do Prof. Dr. DIEVAL GUIZELINI, que
após terem inquirido o aluno e realizada a avaliação do trabalho, são de parecer pela sua APROVAÇÃO no rito de defesa.
A outorga do título de mestre está sujeita à homologação pelo colegiado, ao atendimento de todas as indicações e correções
solicitadas pela banca e ao pleno atendimento das demandas regimentais do Programa de Pós-Graduação.
CURITIBA, 30 de Agosto de 2021.
Assinatura Eletrônica
30/08/2021 17:42:30.0
DIEVAL GUIZELINI
Presidente da Banca Examinadora
Assinatura Eletrônica
30/08/2021 17:38:35.0
RAZER ANTHOM NIZER ROJAS MONTAÑO
Avaliador Externo (SETOR DE EDUCAÇÃO PROFISSIONAL E TECNOLÓGICA - UNIVERSIDADE FEDERAL DO PARANÁ)
Assinatura Eletrônica
30/08/2021 17:57:28.0
RICARDO ASSUNÇÃO VIALLE
Avaliador Externo (ICAHN SCHOOL OF MEDICINE AT MOUNT SINAI - NEW YORK CITY)
Rua Dr. Alcides Vieira Arcoverde, 1225 - CURITIBA - Paraná - Brasil
CEP 81520-260 - Tel: (41) 3361-4906 - E-mail: bioinfo@ufpr.br
Documento assinado eletronicamente de acordo com o disposto na legislação federal Decreto 8539 de 08 de outubro de 2015.
Gerado e autenticado pelo SIGA-UFPR, com a seguinte identificação única: 108938
Para autenticar este documento/assinatura, acesse https://www.prppg.ufpr.br/siga/visitante/autenticacaoassinaturas.jsp
e insira o codigo 108938
Este trabalho é dedicado à comunidade de código livre e aberto.
AGRADECIMENTOS
Agradeço a todas as pessoas a minha volta que me deram suporte, acolhimento e
inspiração para que pudesse desenvolver este trabalho. Especialmente à minha esposa e a minha
família por todo o apoio. Aos meus orientadores e amigos colaboradores que fizeram parte
essencial desta etapa. Agradeço imensamente ao programa de pós-graduação em bioinformática
e todo seu corpo docente e discente, à secretaria e aos demais profissionais que sempre atuaram
de maneira primordial para me auxiliar e prover a matéria-prima para o desenvolvimento deste
trabalho. Agradeço à CAPES pela bolsa de estudos a mim oferecida.
RESUMO
O estudo das relações entre sequências genéticas auxiliam diversas áreas biológicas. A filogenia
pode ajudar a entender histórias e processos evolutivos, como estudo das migrações e dinâmica
social. A filogenia pode acelerar a pesquisa sobre doenças virais como o HIV e o SARS-CoV-2,
fornecendo insights e soluções para a criação de vacinas, por exemplo. As opções matemáticas
para encontrar a melhor relação entre as sequências biológica são diversas e contam com
diferentes propostas e abordagens. Essa larga variedade de métodos gera no pesquisador dúvidas
quanto a qual método deve ser utilizado, principalmente quando grandes quantidades e extensas
sequências são estudadas. Este trabalho propõem inferir os melhores métodos filogenéticos
baseados em distância aplicados a sequências de nucleotídeos e a sequências de aminoácidos.
Avaliou-se também os melhores métodos para abordagens dependente de alinhamento e livre
de alinhamento. Além do processo de análise dos métodos, projetou-se um modelo baseado
em machine learning capaz de classificar as árvores filogenéticas de acordo sua distância à
árvore teórica ideal. Para isso, gerou-se mais de 5.000 árvores teóricas e mais de 600.000 árvores
calculadas por diferentes métodos e métricas de clusterização.
Palavras-chaves: Filogenia. Clusterização. Aprendizado de máquina.
ABSTRACT
The study of relationships between genetic sequences supports several biological areas. Phylogeny
can help to understand evolutionary histories and processes, such as the study of migrations and
social dynamics. Phylogeny can accelerate research into viral diseases such as HIV and SARS-
CoV-2, providing insights and solutions for creating vaccines, for example. The mathematical
options to find the best relationship between biological sequences are diverse and have different
approaches. This wide variety of methods creates doubts about which method should be used,
especially when large quantities and extensive sequences are studied. This work proposes to infer
the best distance-based phylogenetic methods applied to nucleotide and amino acid sequences.
The best methods for based-alignment and free-alignment approaches were also evaluated. In
addition to the method analysis process, a model based on machine learning was designed, it is
capable of classifying phylogenetic trees according to their distance from the ideal theoretical
tree. For this, more than 5,000 theoretical trees were simulated and more than 600,000 trees were
calculated by different clustering methods and metrics.
Key-words: Phylogeny. Clustering. Machine learning.
LISTA DE ILUSTRAÇÕES
FIGURA 1 – ÁRVORE FILOGENÉTICA DE MAMÍFEROS . . . . . . . . . . . . . 18
FIGURA 2 – ÁRVORE ENRAIZADA E NÃO ENRAIZADA ESTÁ À DIREITA . . . 20
FIGURA 3 – ÁRVORE ULTRAMÉTRICA . . . . . . . . . . . . . . . . . . . . . . . 20
FIGURA 4 – REAMOSTRAGEM DO TIPO JACKKNIFE . . . . . . . . . . . . . . . 23
FIGURA 5 – REAMOSTRAGEM DO TIPO BOOTSTRAPPING . . . . . . . . . . . 24
FIGURA 6 – RELAÇÃO ENTRE DISTÂNCIA GENÉTICA E P-DISTANCE . . . . . 28
FIGURA 7 – TAXAS DE MUDANÇAS DE PARES DE NUCLEOTÍDEOS POR
UNIDADE DE TEMPO PARA O MODELO JC69 . . . . . . . . . . . . 30
FIGURA 8 – TAXAS DE MUDANÇAS DE PARES DE NUCLEOTÍDEOS POR
UNIDADE DE TEMPO PARA O MODELO K80 . . . . . . . . . . . . 31
FIGURA 9 – HIERARQUIA DOS MODELOS EVOLUTIVOS DE DNA . . . . . . . 33
FIGURA 10 – TIPOS DE CLUSTERIZAÇÃO . . . . . . . . . . . . . . . . . . . . . . 34
FIGURA 11 – TIPOS DE CLUSTERIZAÇÕES HIERÁRQUICAS . . . . . . . . . . . 35
FIGURA 12 – AGRUPAMENTO SINGLE LINKAGE . . . . . . . . . . . . . . . . . . 36
FIGURA 13 – AGRUPAMENTO COMPLETE LINKAGE . . . . . . . . . . . . . . . . 36
FIGURA 14 – AGRUPAMENTO GROUP AVERAGE LINKAGE . . . . . . . . . . . . 37
FIGURA 15 – CÁLCULO DE DISTÂNCIA SIMÉTRICA ENTRE AS DUAS ÁRVORES 41
FIGURA 16 – MAPA DE DECISÕES PARA ENCONTRAR O MELHOR TIPO DE
MODELO DE MACHINE LERANING. . . . . . . . . . . . . . . . . . 43
FIGURA 17 – PAINEL ESQUEMÁTICO DO EXPERIMENTO . . . . . . . . . . . . 46
FIGURA 18 – PAINEL ESQUEMÁTICO DO EXPERIMENTO DEMONSTRANDO
DADOS UTILIZADOS PARA O DESENVOLVIMENTO DO MODELO
DE MACHINE LEARNING . . . . . . . . . . . . . . . . . . . . . . . . 50
FIGURA 19 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA NUCLE-
OTÍDICA E DEPENDENTE DE ALINHAMENTO . . . . . . . . . . . 55
FIGURA 20 – BOXPLOTS DAS VARIAÇÕES DA DISTÂNCIA À ÁRVORE DE RE-
FERÊNCIA NUCLEOTÍDICA E DEPENDENTE DE ALINHAMENTO 56
FIGURA 21 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA DE
AMINOÁCIDOS E DEPENDENTE DE ALINHAMENTO . . . . . . . 58
FIGURA 22 – BOXPLOTS DAS VARIAÇÕES DA DISTÂNCIA À ÁRVORE DE RE-
FERÊNCIA DE AMINOÁCIDOS E DEPENDENTE DE ALINHAMENTO 59
FIGURA 23 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA NUCLE-
OTÍDICA E INDEPENDENTE DE ALINHAMENTO . . . . . . . . . . 60
FIGURA 24 – DISTÂNCIA MÉDIAS DAS ÁRVORES DE SEQUÊNCIAS NUCLEO-
TÍDICAS E INDEPENDENTES DE ALINHAMENTO . . . . . . . . . 61
FIGURA 25 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA DE
PARES MÉTODO-MÉTRICA EM SEQUÊNCIAS NUCLEOTÍDICAS
PARA MÉTODO INDEPENDENTES DE ALINHAMENTO . . . . . . 62
FIGURA 26 – HEATMAP DE SIGNIFICÂNCIA DA VARIAÇÃO DA DISTÂNCIA
À ÁRVORE DE REFERÊNCIA DE PARES MÉTODO-MÉTRICA EM
SEQUÊNCIAS NUCLEOTÍDICAS PARA MÉTODO INDEPENDEN-
TES DE ALINHAMENTO . . . . . . . . . . . . . . . . . . . . . . . . 68
FIGURA 27 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA EM
SEQUÊNCIAS DE AMINOÁCIDOS PARA MÉTODO INDEPENDENTE
DE ALINHAMENTO . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
FIGURA 28 – DISTÂNCIA MÉDIAS DAS ÁRVORES GERADAS POR MÉTODOS E
MÉTRICAS DIFERENTES EM SEQUÊNCIAS DE AMINOÁCIDOS
PARA MÉTODO INDEPENDENTES DE ALINHAMENTO. . . . . . . 70
FIGURA 29 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA DE
PARES MÉTODO-MÉTRICA EM SEQUÊNCIAS DE AMINOÁCIDOS
PARA MÉTODO INDEPENDENTES DE ALINHAMENTO. . . . . . . 71
FIGURA 30 – HEATMAP DA SIGNIFICÂNCIA DA VARIAÇÃO DA DISTÂNCIA
À ÁRVORE DE REFERÊNCIA DE PARES MÉTODO-MÉTRICA EM
SEQUÊNCIAS DE AMINOÁCIDOS PARA MÉTODO INDEPENDEN-
TES DE ALINHAMENTO. . . . . . . . . . . . . . . . . . . . . . . . . 72
FIGURA 31 – REPRESENTAÇÃO ESQUEMÁTICA DO PROCESSO DE MODELA-
GEM DO MÉTODO RANDOM FOREST. . . . . . . . . . . . . . . . . 73
FIGURA 32 – RESULTADOS DE VALIDAÇÃO DO MODELO RANDOM FOREST. . 73
FIGURA 33 – CURVAS ROC RANDOM FOREST DO MODELO. . . . . . . . . . . . 74
FIGURA 34 – TACOS WEB SITE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
LISTA DE TABELAS
TABELA 1 – SIMILARIDADE MEDIDA PARA DADOS BINÁRIOS . . . . . . . . 26
TABELA 2 – CONTAGEM DE RESULTADOS BINÁRIOS PARA DOIS INDIVÍDUOS 26
TABELA 3 – SIMILARIDADE MEDIDA PARA DADOS CONTÍNUIOS . . . . . . 29
TABELA 4 – MATRIZ DE CONFUSÃO . . . . . . . . . . . . . . . . . . . . . . . . 44
TABELA 5 – CARACTERÍSTICAS DA SIMULAÇÃO: QUANTIDADE, TAMANHO
E TAXA DE MUTAÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . 47
TABELA 6 – RESUMO DE PROGRAMAS E PACOTES UTILIZADOS . . . . . . . 53
TABELA 7 – MELHORES MÉTRICAS OBTIDAS COM GRIDSEARCHCV . . . . 64
TABELA 8 – MELHORES HIPERPARÂMETROS OBTIDOS COM GRIDSEARCHCV 64
TABELA 9 – MATRIZ DE CONFUSÃO DE CADA CLASSE DO MODELO RAN-
DOM FOREST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
TABELA 10 – MÉTRICAS MÉDIAS PARA VALIDAÇÃO DO MODELO RANDOM
FOREST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
TABELA 11 – MÉTRICAS DETALHADAS POR CLASSE PARA VALIDAÇÃO DO
MODELO RANDOM FOREST . . . . . . . . . . . . . . . . . . . . . . 66
LISTA DE ABREVIATURAS E DE SIGLAS
AB Alignment-Based
ACO Ant Colony Optimization
AF Alignment-Free
AUC Area Under The Curve
BLOSUM Blocks Substitution Matrix
DNA Ácido Desoxirribonucleico
EMBOSS European Molecular Biology Open Software Suite
F81 Felsenstein 1981
F84 Felsenstein 1984
GTR Generalised time-reversible model of Tavaré 1986
HIV Vírus da Imunodeficiência
HKY85 Hasegawa, Kishino and Yano 1985
JC69 Jukes-Cantor
K80 Kimura 2-parâmetros
ML Máxima Verossimilhança
ML Machine Learning
NCBI National Center for Biotechnology Information
PAM Point Accepted Mutation
PCO Particle Swarm Optimization
ROC Receiver Operating Characteristic
SWeeP Spaced Words Projection
TN93 Tamura and Nei 1993
UPGMA Unweighted Pair Group Method with Arithmetic Mean
UPGMC Unweighted Pair Group Method Using the Centroid
WPGMA Weighted Pair Group Method with Average Linkage
WPGMC Weighted Pair Group Method with Centroid Linkage
SUMÁRIO
1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1 Justificativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Objetivos Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 FUNDAMENTAÇÃO TEÓRICA . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1 Árvores Filogenéticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.1 Métodos Baseados em Distância . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.2 Métodos Baseados em Caracteres . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Estimativa e teste de hipóteses em filogenia . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Jackknife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Bootstrapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.3 Estimativa e teste de hipótese para método livre de alinhamento . . . . . . . . . 23
2.3 Processos independentes de alinhamento . . . . . . . . . . . . . . . . . . . . . 24
2.4 Clusterização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Medidas de proximidade entre indivíduos . . . . . . . . . . . . . . . . . . . . . 25
2.4.2 Correção Modelo Evolutivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.3 Tipos de Clusterização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.4 Métodos aglomerativos: bottom-up . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4.5 Métodos divisivos: top-down . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.5 Distância entre árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.6 Processos evolutivos simulados . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.7 Aprendizado de máquina (Machine learning) . . . . . . . . . . . . . . . . . . . 42
3 MATERIAIS E MÉTODOS . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1 ETAPA 1: Simulação de árvores, sequências e alinhamentos . . . . . . . . . . . 46
3.2 ETAPA 2: Cálculo das matrizes de dissimilaridade . . . . . . . . . . . . . . . . 47
3.2.1 Cálculo de matrizes dependentes de alinhamentos - EMBOSS . . . . . . . . . . 47
3.2.2 Cálculo de matrizes independentes de alinhamentos - SWeeP . . . . . . . . . . 48
3.3 ETAPA 3: Clusterização das matrizes de dissimilaridade . . . . . . . . . . . . . 48
3.4 ETAPA 4: Cálculo de distância entre as árvores . . . . . . . . . . . . . . . . . . 49
3.5 ETAPAS 5,6 e 7: Construção do modelo de classificação de árvores filogenéticas 49
3.5.1 Definição das variáveis de entrada (features) . . . . . . . . . . . . . . . . . . . 50
3.5.2 Definição do modelo de aprendizado de máquina . . . . . . . . . . . . . . . . . 51
3.6 Delimitação do experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.7 Limitações do experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.8 Lista de pacotes e programas utilizados . . . . . . . . . . . . . . . . . . . . . . 52
4 RESULTADOS E DISCUSSÃO . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1 Resultados dependentes de alinhamento . . . . . . . . . . . . . . . . . . . . . . 54
4.1.1 Sequências de nucleotídeos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1.2 Sequências de aminoácidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
14
4.2 Resultados independentesde alinhamento . . . . . . . . . . . . . . . . . . . . . 57
4.2.1 Sequências de nucleotídeos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2.2 Sequências de aminoácidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3 Treino e validação do modelo classificador de árvores filogenéticas . . . . . . . 64
4.4 TACos: Pacote python e aplicação web . . . . . . . . . . . . . . . . . . . . . . 66
5 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
APÊNDICE 1 - Scripts para o desenvolvimento do experimento . . . . . . . 85
1.1 Obtenção dos dados de referência - árvores, sequências e alinhamentos . . . . . 86
1.2 Scripts para cálculo das matrizes de distância por método dependentes de
alinhamento (AB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
1.3 Scripts para cálculo das matrizes de distância por método livre de alinhamento (AF) 89
1.4 Scripts para cálculo das árvores a partir das matrizes de distância e cálculo das
distâncias entre as árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
15
1 INTRODUÇÃO
O estudo das relações evolutivas entre os seres vivos a partir de dados moleculares
auxilia os cientistas a responderem diversas perguntas biológicas, entre elas respostas essenciais
para a cura e tratamentos de doenças. Nas áreas de desenvolvimento de vacinas, a filogenia pode
auxiliar no entendimento da proliferação de doenças, mutações genéticas de parasitas, interações
proteicas e redes genéticas. (MAHAPATRO et al., 2012).
A exemplo do Vírus da Imunodeficiência (HIV), a filogenia auxiliou a elucidar e a criar
abordagens de tratamento a respeito desse vírus. Por exemplo, como a taxa de recombinação e
substituição genética do HIV impacta nos tratamentos antivirais, como diferentes cepas do HIV
evoluem dentro do indivíduo infectado, ou ainda, como a rota de transmissão pode influenciar no
resultado da infecção (CASTRO-NALLAR et al., 2012).
Recentemente a filogenia teve papel crucial nos estudos da SARS-CoV-2 com o
entendimento da evolução do vírus e como algumas mutações surgiram e onde surgiram (LI
et al., 2020), reforçando a importância do trabalho de monitoramento da variação e evolução do
SARS-CoV-2 para o tratamento e controle da COVID-19 e de futuras pandemias. Outros estudos
que envolvem filogenia, como a filogeografia também são essenciais para o entendimento da atual
pandemia. É possível rastrear mutações virais e entender como o vírus se espalha e relacionar
sua dispersão com dados de rotas viagens feitas entre países (LEMEY et al., 2020), podendo
ajudar em estabelecer estratégias de mitigação de infecção com o fechamento de fronteiras, por
exemplo.
Outros temas importantes da biologia também encontram na filogenia uma base para a
investigação, como na ecologia com estudos de migrações, dinâmica social, mudanças ambientais
promovidas por espécies exóticas, assim como e processos de extinção de espécies (LEWITUS;
MORLON, 2015).
A proposição de árvores filogenéticas baseada em dados moleculares atravessa diversas
etapas até ser inferida. Tem início no wet-lab com o sequenciamento de ou aminoácidos (VERLI,
2014) e passa por diversas etapas até ser graficamente representada. Dependendo da abordagem,
as sequências são alinhadas para gerar uma matriz de valores que representem a similaridade
entre os indivíduos. Ou ainda, a similaridade pode ser obtida sem a necessidade de alinhamentos
com o uso de ferramentas livres de alinhamento. Com as distâncias entre as sequências, os
indivíduos são hierarquicamente ordenados em árvores ou dendrogramas.
Alguns processos de clusterização são comumente utilizados na obtenção dos dendro-
gramas baseados em distância como UPGMA e Neighbor joining (LEMEY et al., 2009). Já
para modelos probabilísticos, alguns outros métodos são aplicados como: método Bayesiano,
máxima parsimônia e máxima verossimilhança (FELSENSTEIN, 1983). Como alternativa a
16
essas abordagens citadas, existem outros métodos estruturados em inteligência artificial como:
Ant Colony Optimization (ACO) e Particle Swarm Optimization (PCO) (RIZZO; ROUCHKA,
2007), evidenciando a pluralidade dos métodos envolvidos ao tema. Outro importante processo
envolvido é a determinação da confiança estatística das árvores obtidas. A validade estatística da
árvore é, geralmente, analisada com o método bootstrapping, um esforço estatístico para avaliar
uma árvore gerada quando não se conhece a distribuição da variável analisada (FELSENSTEIN,
1985).
Dentre tantos processos distintos envolvidos na determinação das relações hierárquicas
dos seres vivos, um mesmo conjunto de indivíduos pode gerar diferentes relações dependendo
da abordagem adotada, em especial quando espécies distantes estão envolvidas (PUIGBÒ
et al., 2019). Com isso surge o questionamento de qual é o melhor método a ser utilizado
para determinado conjunto de dados. Dependendo das características do conjunto, quais são as
diferenças entre resultados obtidos por diferentes técnicas?
Limitando-se a abordagens de inferência filogenéticas baseados em distância, este projeto
investiga como métodos e métricas de clusterização hierárquica respondem aos experimentos
baseados em alinhamento e aos livres de alinhamento. O projeto também investiga como esses
métodos e métricas respondem a diferentes tipos de conjuntos de sequências. Ou seja, conjunto
de dados com diferentes quantidades de sequências, diferentes tamanhos de sequências, diferentes
taxas de mutação e diferentes tipos de informação - sequências de nucleotídeos e aminoácidos.
O projeto também investiga a possibilidade de se classificar uma árvore filogenética
de acordo com sua proximidade da árvore teórica, ou árvore ideal. O método de classificação
proposto é baseado em aprendizado de máquina e pode ser um complemento às técnicas de
bootstraping e jackknife utilizadas para inferir a confiança dos ramos das árvores.
Para controlar as variáveis durante o experimento, fez-se necessário trabalhar com
sequências teóricas, que mesmo simuladas in silico geram percepções e direcionamentos para
aplicação em problemas reais. Conhecer a acurácia dos métodos e como eles podem ser melhor
aproveitados pode gerar rapidez e assertividade na resolução de importantes questões que
dependem da filogenia para serem corretamente respondidas.
Dada a importância da filogenia nas diversas áreas de investigação da ciência biológica,
é imprescindível entender amplamente os métodos de inferência de árvores filogenéticas e, assim,
propor o melhor método que possa inferir a melhor topologia dentre todo o conjunto de árvores
possíveis de serem inferidas. Dessa maneira, também se faz importante a criação de novas
ferramentas capazes de classificar a árvore de acordo com a sua capacidade de reproduzir as
relações evolutivas reais.
17
1.1 JUSTIFICATIVAS
1. Com a diversidade de métodos e métricas existentes para inferir uma árvore filogenética,
faz-se necessário definir a melhor opção para diferentes tipos de alinhamentos de entrada e
diferentes metodologias de obtenção de árvores (dependente de alinhamento e livre de
alinhamento).
2. Considerando as relações entre a árvore e a matriz de distância, pode-se usar o apren-
dizado de máquina para classificar a dissimilaridade da árvore a sua árvore teórica.
Complementando as avaliações de reamostragem.
1.2 OBJETIVOS GERAIS
1. Avaliar métodos clássicos de clusterização hierárquica na obtenção de árvores filogenéticas
em abordagens dependentes de alinhamentos e baseadas em distância.
2. Desenvolver um modelo baseado em aprendizado de máquina para classificar árvores de
acordo com suas características e suas relações com a matriz de distância.
1.3 OBJETIVOS ESPECÍFICOS
1. Investigar métodos e métricas de clusterização hierárquica.
2. Investigar métodos de comparação de árvores.
3. Avaliar como mudanças no tamanho das sequências, na quantidade das sequências e na
taxa de mutaçãoalteram a árvore resultante.
4. Selecionar características que definem uma árvore (grafo).
5. Encontrar relações entre a árvore e a matriz de distância.
6. Criar um modelo baseado em aprendizado de máquina para classificar uma árvore de
acordo com suas características.
7. Disponibilizar pacote em Python para facilitar investigações que precise comparar árvores
e classificá-las.
8. Criar uma aplicação amigável em web para o mesmo do item 7.
18
2 FUNDAMENTAÇÃO TEÓRICA
2.1 ÁRVORES FILOGENÉTICAS
A inferência da história evolutiva de um determinado grupo de espécies é conhecida
como filogenia (FREEMAN; HERRON, 2009) e a relação entre os diferentes indivíduos é
graficamente expressa em uma árvore filogenética, também chamada de árvore evolutiva. O
dendrograma da FIGURA 1 representa de forma hierárquica as semelhanças, ou distâncias,
entre os indivíduos analisados. Os indivíduos mais próximos são agrupados de acordo com as
semelhanças entre as suas sequências genéticas escolhidas para a análise. As árvores possuem
um padrão gráfico em que as espécies são representadas como uma folha, e a relação entre as
espécies é representado com uma aresta ou ramo (RIZZO; ROUCHKA, 2007).
FIGURA 1 – ÁRVORE FILOGENÉTICA DE MAMÍFEROS
FONTE: FREEMAN; HERRON(2009)
Originalmente, o propósito principal de se construir uma árvore filogenética era
representar essa relação entre as espécies, porém, atualmente a aplicação desta técnica é usada
também para explicar funções de genes ainda não estudadas experimentalmente, explicar
mecanismos que levam a surtos microbianos auxiliando no entendimento da proliferação de
doenças (HALL, 2013). Também auxilia no desenvolvimento de vacinas e medicamentos,
permitindo prever mutações genéticas de parasitas, interações proteicas e redes genéticas
(MAHAPATRO et al., 2012).
Existem diversas etapas para a determinação de uma árvore filogenética, e em cada
etapa várias decisões devem ser tomadas e podem mudar totalmente o resultado final. Entre
essas escolhas estão os métodos de construção mais adequados ao problema. Ou seja, qual
método terá como resultado uma árvore que possua um sentido biológico e que melhor represente
o agrupamento das sequências estudadas e, ao mesmo tempo, seja viável de ser calculada
19
computacionalmente. Pode-se dividir estes métodos de obtenção de árvores filogenéticas em duas
principais abordagens: a baseada em distância e a baseada em caracteres (RIZZO; ROUCHKA,
2007), também classificadas como abordagens quantitativas e qualitativas, respectivamente
(VERLI, 2014). Também pode-se classificar os métodos em dependentes de alinhamento e
independentes de alinhamento (alignment-free) (VINGA; ALMEIDA, 2003).
Independe da aplicação, a inferência filogenética começa pela coleta de sequências
moleculares, sejam sequências de aminoácidos ou nucleotídeos, tomando-se o cuidado de avaliar
a coerência das sequências, como a quantidade de caracteres ambíguos e os tamanhos médios
das sequências, para que o agrupamento não seja afetado. Após isso, alinham-se as sequências e
gera-se uma primeira árvore para se ter uma primeira impressão das relações entre os indivíduos.
Caso o alinhamento possua muitos indels consecutivos, ou seja, uma coluna extensa de gaps,
avalia-se a possibilidade de se deletar partes das sequências para reduzir estes gaps e evitar um viés
durante a construção das árvores. Após isso, constrói-se novas árvores para reavaliar a alteração
no alinhamento, para então, com métodos mais robustos como Máxima Verossimilhança (ML)
ou bayesiano, gerar a árvore final (JILL HARRISON; LANGDALE, 2006). Deve-se ainda definir
o modelo evolutivo das substituições de pares de bases em cada sítio do alinhamento, uma vez
que todos os métodos de inferência filogenética dependem do modelo escolhido (POSADA;
CRANDALL, 1998).
Para métodos independentes de alinhamento, a etapa de avaliação de alinhamento não é
executada, aplicando-se diretamente o método livre de alinhamento às sequências, sequências
essas também avaliadas quanto a coerência e aos seus tamanhos, podendo-se, dependendo do
método, inferir modelos evolutivos de substituição (DE PIERRI et al., 2020).
As árvores geradas são, geralmente, não enraizadas (unrooted), os métodos de inferência
de árvores como máxima verossimilhança, neighbor joining, parcimônia e bayesiano são incapazes
de determinar a raíz de uma árvore (HALL, 2013). Caso seja do interesse do pesquisador avaliar
a direção evolutiva, deve-se enraizar a árvore (rooted) escolhendo o outgroup como a raíz da
árvore ou calculando o ponto médio entre as duas folhas mais dissimilares (LEMEY et al., 2009).
Ambos os tipos de árvores são exemplificadas na FIGURA 2.
Para árvores filogenéticas enraizadas, qualquer distância medida (ou valor de dissimi-
laridade) entre três membros deve ser preferencialmente ultramétrica. Essa condição garante
que uma única topologia seja possível (EWENS; GRANT, 2006), e que, o tempo decorrido
da mutação, conhecido como molecular clock, seja considerado. Para o mesmo autor, caso as
distâncias originais não sejam ultramétricas, espera-se uma inferência incorreta da árvore em
relação aos tamanhos dos ramos e às distâncias de similaridade (HAUBOLD; WIEHE, 2006). A
distância ultramétrica obedece ao critério de três pontos. O qual afirma que, para quaisquer três
táxons A, B, C, há dois pares equidistantes de táxons, sendo a distância entre o terceiro menor ou
igual aos outros dois (HAUBOLD; WIEHE, 2006). Ou seja, para a topologia representada na
20
FIGURA 2 – ÁRVORE ENRAIZADA E NÃO ENRAIZADA ESTÁ À DIREITA
FONTE: RIZZO; ROUCHKA(2007)
NOTA: Árvore não enraizada está à esquerda e a enraizada está à direita. Note que o método de
enraizamento desta árvore foi pelo cálculo do ponto médio entre os ramos distantes.
Transformando a aresta central (AB-CD) em duas arestas denominadas e e f.
FIGURA 3, tem-se a condição posta pela EQUAÇÃO 2.1.
3�� = 3�� ≥ 3�� (2.1)
FIGURA 3 – ÁRVORE ULTRAMÉTRICA
FONTE: HAUBOLD; WIEHE(2006)
NOTA: Os ramos definidos pelas folhas AB e AC são equidistantes. E o ramo definido por BC
é menor que os outros dois.
2.1.1 Métodos Baseados em Distância
A primeira abordagem envolve algoritmos de clusterização aplicados às matrizes de
distâncias entre as sequências analisadas. Estas matrizes são previamente calculadas o podem
ser obtidas por diversos métodos, como distância euclidiana, cosseno, cityblock, sokalsneath
entre outras métricas melhor descritas na TABELA 1 e TABELA 3. Uma vez calculadas as
21
matrizes, calcula-se os dendrogramas com métodos de clusterização hierárquica. Como exemplo
pode-se citar o método UPGMA, ou simplesmente average linkage method muito utilizado
entre os algoritmos de clusterização (HAUBOLD; WIEHE, 2006) assim como os métodos
neighbor-joinning, distance wagner method e miminum evolution method, esses dois últimos
menos utilizados.
Os métodos filogenéticos baseados em distância compõem a maior família de métodos
filogenéticos (FELSENSTEIN, 2004) e, atualmente, tiveram acrescida popularidade com a era
do big data, em que se busca inferir árvores com centenas ou milhares de folhas (XIA, 2018)
com algoritmos de baixa complexidade. Ainda segundo Felsenstein, os métodos de distância
são fáceis de programar, são rápidos e consistentes quando as matrizes são corrigidas para
modelos evolutivos, ou seja, que representem a quantidade de mutações por unidade de tempo do
conjunto de sequências. Porém, há um grande problema quando se tem altas taxas de mutações
distribuídas em diferentes posições ao longo das sequências alinhadas. Essa diferença de mutação
entre posições do alinhamento é impossível de ser considerada pelo método de distância. Em
contraponto, o método da verossimilhança (likelihood) pode usar a informação das mudanças de
uma parte da árvore para corrigir as outras partes da árvore (FELSENSTEIN, 2004).
2.1.2 Métodos Baseados em Caracteres
Contrastando com a inferência baseada em distância, os principais métodos baseados
em caracteres utilizam o alinhamento originalpara a resolução das árvores. Ao invés de calcular
distâncias par a par, otimiza-se a árvore resultante de acordo com a distribuição dos dados
alinhados em relação a cada caractere específico (STRICKLER, 2014). Ou seja, para cada posição
do alinhamento compara-se simultaneamente todas as sequências do alinhamento gerando-se
novas árvores a cada comparação, sendo que a cada comparação os métodos geram uma
pontuação da árvore (tree score) (YANG; RANNALA, 2012). Fazem parte dos grupos baseados
em caracteres os métodos da máxima parcimônia, máxima verossimilhança e de inferência
bayesiana. Cada método gera, respectivamente, os scores pela mínima quantidade de mudanças,
valor de log-likelihood e probabilidade a posteriori.
O método da máxima parcimônia segue a ideia da mínima quantidade de eventos
evolutivos (CAVALLI-SFORZA; EDWARDS, 1963), ou seja, é sempre preferível a hipótese mais
simples à mais complicada (HILLIS et al., 1996). Esta hipótese se justifica com as primeiras
aplicações do método, que foi desenvolvido para inferência evolutiva a partir de características
morfológicas. O cálculo de pontuação, portanto, é a soma das mudanças de estado necessárias
para se construir a árvore, e a árvore com menor score, é a árvore escolhida (FELSENSTEIN,
2004).
Caso queira-se construir uma árvore filogenética considerando a probabilidade de se
encontrar uma mutação ao longo de um ramo da árvore filogenética, pode-se usar o método da
máxima verossimilhança. A ideia principal deste método é determinar a topologia, tamanhos dos
22
ramos e parâmetros de modelos evolutivos, ou seja, os parâmetros da função de verossimilhança,
que maximizem a probabilidade de se conseguir reproduzir o alinhamento das sequências
(LEMEY et al., 2009).
Semelhante ao método da máxima verossimilhança, o método bayesiano é também
aplicado para inferência filogenética. O que o difere da ML é o uso da distribuição a priori da
árvore a ser inferida. Isso permite interpretar os resultados como uma nova distribuição de dados
de entrada (FELSENSTEIN, 2004). Ou seja, a cada nova análise tem-se um novo conjunto de
dados - uma distribuição a posteriori.
2.2 ESTIMATIVA E TESTE DE HIPÓTESES EM FILOGENIA
Quando uma variável não possui uma distribuição conhecida de probabilidade, recorre-
se a métodos chamados computação intensiva para estimar um intervalo de confiança, inferindo
novas amostragens a partir a amostra original (FELSENSTEIN, 1985). Porém, como enfatiza
Ewens, há um erro terminológico ao utilizar intervalo de confiança para árvore filogenéticas,
pois o termo intervalo de confiança é definido para um intervalo de números reais (EWENS;
GRANT, 2006). Enquanto em agrupamentos monofiléticos (agrupamento de membros de uma
mesma espécie), por exemplo, a medida de confiança busca determinar se o grupo é real ou não,
e não um intervalo propriamente dito.
Os principais métodos estatísticos adaptados e utilizados em filogenia são o jackknife e
o bootstrapping.
2.2.1 Jackknife
A reamostragem proposta por este método consiste em dividir as sequências ao meio e
gerar novos agrupamentos. Ou seja, a cada reamostragem retira-se, aleatoriamente, metade dos
nucleotídeos ou aminoácidos, e infere-se a árvore para as sequências adulteradas. Por essa razão,
muitas vezes o método é também chamado de delete-half jackknifing (LEMEY et al., 2009). A
FIGURA 4 ilustra o funcionamento do método.
Quanto mais os agrupamentos se repetirem para diferentes amostras, maior a confiança
do clado agrupado. Caso um clado esteja presente em todas as reamostragens, diz-se que o valor
do jackknife é 100%. Quanto menos aparecer, menor o seu valor.
2.2.2 Bootstrapping
Assim como jackknife, o bootstrapping é utilizado para reamostrar as sequências e
verificar o quanto determinado clado se repete a cada reamostragem. Porém, diferentemente do
jackknife, o método não altera o tamanho das sequências, mas sim o conteúdo. Após alinhar
as sequências, substitui-se aleatoriamente colunas originais por colunas de outras posições.
23
FIGURA 4 – REAMOSTRAGEM DO TIPO JACKKNIFE
FONTE: O Autor.
NOTA: Reamostragem do tipo Jackknife. Na primeira linha da figura tem-se o alinhamento
original. Na segunda linha tem-se em cinza claro as colunas excluídas do
alinhamento. Na terceira linha tem-se a reamostragem, ou seja, variações do
alinhamento original.
Mantendo-se o alinhamento, porém com nucleotídeos diferentes. Então computa-se a quantidade
de vezes que os clados se repetem, inferindo, assim, a probabilidade do clado estar correto.
A figura 5 exemplifica o processo. A adaptação deste método para aplicação em inferência
filogenética foi proposta por Joseph Felsenstein em 1985 (FELSENSTEIN, 1985).
Um dos problemas deste método de reamostragem é que se a sequência tiver um
viés, as estimativas do bootstrap também serão enviesadas. Por exemplo, sequências ricas em
conteúdo GC tem grandes chances de substituir colunas ricas em bases GC por colunas ricas
em nucleotídeos do mesmo tipo. Isso gera uma confiança artificial gerada pelo método, como
expressa (LEMEY et al., 2009).
2.2.3 Estimativa e teste de hipótese para método livre de alinhamento
Assim como os métodos bootstrapping e jackknife foram adaptados para estimar a
confiabilidade de árvores filogenéticas, eles podem ser readaptados para inferir confiabilidade
a árvores geradas sem que o alinhamento múltiplo seja feito. O programa AAF, sigla para
Alignment and Assembly Free, aplica o método bootstrapping na estratégia livre de alinhamento
para inferir a confiabilidade dos clados gerados (FAN et al., 2015). Infelizmente, os detalhes do
método utilizado neste programa não contém códigos abertos.
Porém, Zuo et al, propõem uma adaptação ao método bastante criativa e, segundo
24
FIGURA 5 – REAMOSTRAGEM DO TIPO BOOTSTRAPPING
FONTE: O Autor.
NOTA: Reamostragem do tipo Bootstrapping. Na primeira linha da figura tem-se o
alinhamento original e destaque as colunas que serão repetidas para a reamostragem.
Na segunda linha tem-se a reamostragem com três variações do alinhamento
original. Na primeira variação substituí-se aleatoriamente colunas do alinhamento
original pelas colunas em azul. Na segunda variação substituí-se aleatoriamente
colunas do alinhamento original pelas colunas amarelas. Por fim, no terceiro
exemplo de variação substituí-se aleatoriamente colunas do alinhamento original
pelas colunas verdes.
seu artigo, com bons resultados. A estratégia pode ser aplicada tanto para jackknife quanto
para bootstrapping. Ao invés de excluir ou substituir colunas do alinhamento múltiplo original,
cataloga-se todas as proteínas existentes comuns a todas as sequências envolvidas na análise, para
então excluí-las aleatoriamente de todas as sequências (jackknife), ou então substituir e repetir
aleatoriamente as proteínas ao longo das sequências (bootstrapping), podendo algumas proteínas
serem repetidas ou excluídas (ZUO et al., 2010).
2.3 PROCESSOS INDEPENDENTES DE ALINHAMENTO
Tradicionalmente, a inferência de árvores filogenéticas conta com a etapa de alinhamento
múltiplo das sequências. Porém, as ferramentas de alinhamento múltiplo largamente usadas não
são capazes de alinhar sequências longas de DNA - da ordem de milhões de nucleotídeos - ou de
aminoácidos (ZIELEZINSKI et al., 2019). Na era dos sequenciadores de próxima-geração, o
sequenciamento de genomas inteiros é realizado de maneira rápida (se comparada às tecnologias
anteriores) para crescentes números de distintos organismos (FAN et al., 2015), por isso há
grande necessidade de metodologias alternativas aos métodos baseados em alinhamento -
Alignment-Based (AB) - como os métodos livres de alinhamento ou Alignment-Free (AF).
Nos últimos anos, um grande número de métodos rápidos livres de alinhamento foram
propostos para a reconstrução de árvores filogenéticas (DENCKER et al., 2020). Resultando numa
diversidade de propostas e combinações de métodos e métricas para a inferência filogenética.
Um dos principais problemas apontados é que as inferências das árvores nãosão baseadas em
modelos evolutivos específicos, principalmente na comparação de similaridade entre sequências
25
(FAN et al., 2015).
Isso pode levar a crer que os métodos livres de alinhamentos não geram árvores
confiáveis com sentido biológico, porém, em recente trabalho publicado, a ferramenta livre
de alinhamento Spaced Words Projection (SWeeP) se mostrou capaz de inferir filogenias
convergentes às estabelecidas na literatura. Os experimentos feitos com o genoma mitocondrial
e proteoma bacterial de todos os organismos listados no National Center for Biotechnology
Information (NCBI) mostrou-se inclusive superior aos métodos baseados em alinhamento (DE
PIERRI et al., 2020). O desenvolvimento de métodos alignment-free podem suprir algumas
deficiências dos métodos baseado em alinhamentos, como a imprecisão dos métodos AB em
cenários de baixa identidade entre as sequências e a incapacidade de serem aplicados diretamente
a sequências rearranjadas, sejam os rearranjos provenientes de recombinação de domínios
proteicos, por duplicação de genes ou por transferências horizontais (ZIELEZINSKI et al., 2019).
2.4 CLUSTERIZAÇÃO
O agrupamento de dados, a partir de características comuns, é parte do processo de
conhecimento humano nas mais diversas áreas de investigação. Um dos agrupamentos mais
conhecidos, e talvez o mais revolucionário das ciências exatas, foi o pensado por Dimitri
Mendeleiev 1869: a tabela periódica, que levou 80 anos para ser proposta como a conhecemos
desde a primeira organização em 1798 por Lavoisier (STRATHERN, 2001). Atualmente conta-se
com a ciência da computação para, em segundos, agrupar dados de uma população em subgrupos
relacionados. O método de clusterização é justamente esse: o particionamento de um conjunto de
objetos em subconjuntos de acordo com algum critério desejado, a fim de encontrar padrões
entre grupos de um determinado conjunto de dados (BLUM et al., 2016).
Geralmente, os critérios utilizados são a similaridade ou dissimilaridade para compara-
ções entre conjuntos de variáveis categóricas e a distância aritmética entre os elementos quando
estes são contínuos. Pode-se dizer que dois elementos são próximos quando suas similaridades
são altas, e distantes quando suas similaridades são baixas. Em termos geométricos, clusterizar
é um processo para identificar regiões densas, as quais são separadas por regiões esparsas, no
conjunto de dados a serem agrupados (MA; CHOW, 2004).
2.4.1 Medidas de proximidade entre indivíduos
Antes de se falar em agrupamento de indivíduos semelhantes, é necessário medir essa
similaridade ou dissimilaridade entre os indivíduos da população analisada. Esses indivíduos
podem ser representados por valores categóricos ou contínuos. Os valores contínuos podem ser
calculados segundo a TABELA 1, em que os valores de entrada são obtidos através da TABELA 2
de classificação cruzada de correspondência e não correspondência (match e mismatch) entre
dois indivíduos.
26
TABELA 1 – SIMILARIDADE MEDIDA PARA DADOS BINÁRIOS
Medidas Fórmula
S1: Matching coefficient B8 9 = 0+30+1+2+3
S2: Jaccard coefficient B8 9 = 00+1+2
S3: Rogers e Tanimoto B8 9 = 0+30+2(1+2)+3
S4: Sneath e Sokal B8 9 = 00+2(1+2)
S5: Gower e Legendre B8 9 = 0+30+ 12 (1+2)+3
S6: Gower e Legendre B8 9 = 00+ 12 (1+2)
FONTE: Everitt et al. (2011)
TABELA 2 – CONTAGEM DE RESULTADOS BINÁRIOS PARA DOIS INDIVÍDUOS
indivíduo i
Outcome 1 0 Total
Indivíduo j 1 0 1 0 + 1
0 2 3 2 + 3
Total 0 + 2 1 + 3 ? = 0 + 1 + 2 + 3
FONTE: Everitt et al. (2011)
A escolha do melhor método para o cálculo da distância depende da análise que se está
fazendo. Se para análise a ausência de determinada característica em ambos os indivíduos for
irrelevante, como o que ocorre em d (co-ausência), utiliza-se S2, S4 e S6, uma vez que a variável
d é ignorada nas equações. Caso a informação de co-ausência seja importante para a análise,
utiliza-se as outras fórmulas.
Outro fator considerado nas equações é o peso dos valores c e b, em que há ocorrência
da característica em um indivíduo e ausência em outro. Nas equações S3 e S4 o peso é duas vezes
para b e c. Já nas equações S5 e S6, o peso dado para b e c é de 0,5. Os valores dos pesos podem
ser diferentes dos mostrados nas equações, refletindo o melhor julgamento do investigador sobre
o conjunto estudado, ou, ajustando algum aspecto da matriz de dados (EVERITT et al., 2011).
Caso a mensuração de similaridade tenha mais de um nível - como tipo sanguíneo, cor
dos olhos, partido político ou mesmo bases das sequências de DNA recomenda-se calcular um
score B8 9 : que varie de zero a um para cada variável k, dependendo dos indivíduos do grupo
i e j terem o mesmo valor para a variável k. Uma vez definido os valores de score, calcula-se
então a média dos scores obtidos, como demonstra a EQUAÇÃO 2.2, para obter o coeficiente de
similaridade (EVERITT et al., 2011).
B8 9 =
1
?
∞∑
:=1
B8 9 : (2.2)
Porém, na prática, para comparação de similaridade entre sequências moleculares
alinhadas, considera-se match como score 1 e mismatch como score 0, como é o caso da função
27
distmat do programa European Molecular Biology Open Software Suite (EMBOSS) (RICE
et al., 2000).
É comum também levar em consideração a quantidade de inserções ou deleções e definir
o score para cada um dos gaps das sequências. O cálculo de similaridade entre duas sequências
com a função distmat é definida pela EQUAÇÃO 2.3. Em que < é a soma dos matches, =?>B é
quantidade de posições incluindo os matches, 60?B é a quantidade de gaps nas sequências, e
60??4=0;CH é o score de penalidade a cada posição de gap.
( =
<
=?>B + (60?B × 60??4=0;CH)
(2.3)
Com o valor de similaridade calcula-se pela EQUAÇÃO 2.4 a distância observada. Essa
distância é mais conhecida como p-distance (LEMEY et al., 2009).
? − 38BC0=24 = 1 − ( (2.4)
É possível ainda atribuir scores de match e mismatch a partir de matrizes de substituições
difundidas na literatura ou matrizes personalizadas. A função DistanceCalculator do pacote
Biopython (COCK et al., 2009), por exemplo, permite calcular matrizes de distâncias com scores
de matches e mismatches usados na ferramenta Blast para nucleotídeos e aminoácidos, como
PAM , BLOSUM , BENNER e outras.
É interessante notar que, apesar de bastante intuitiva, a medida p-distance pode não
representar a distância genética entre as sequências, principalmente quando há alto grau de
divergência entre elas. A distância de dissimilaridade é incapaz de contabilizar mais de uma
mutação entre os sítios comparados. Por exemplo, tomando-se a substituição do nucleotídeo A
por C e, posteriormente, por G, a função p-distance contabiliza apenas a mudança observada, ou
seja, de A para G. Caso, posterior mudança de A para C seja para A, nenhuma mutação será
detectada ao calcular a dissimilaridade. Pode-se dizer que p-distance subestima a verdadeira
distância genética, pois conforme o tempo evolutivo avança, as diferenças entre as sequências
podem se tornar aleatórias ou saturadas (LEMEY et al., 2009). A figura 6 ilustra a relação entre
p-distance (p) e distância genética (d).
Próximo ao valor 0,7 de p-distance, o valor de d pode aumentar infinitamente que o
valor de p não se altera devido ao efeito de saturação. A forma desta curva pode ser alterada caso
leve-se em consideração a probabilidade de mudanças entre pares de bases ou aminoácidos. O
que pode ser feito com o uso de modelos evolutivos para corrigir a distância de dissimilaridade,
esses modelos são detalhados na seção 2.4.2.
As considerações abordadas até aqui referem-se à mensuração de distâncias entre dados
categóricos. Já para dados contínuos, temos as equações da TABELA 3. Note que as distâncias
28
FIGURA 6 – RELAÇÃO ENTRE DISTÂNCIA GENÉTICA E P-DISTANCE
FONTE: LEMEY et al.(2009)
NOTA: Relação entre distância genética (eixo da abscissas) e p-distance (eixo das ordenadas).
Note que para este modelo, para valores de d maiores que 3, os valores de p se
mantém constantes, ou seja, não contabilizam as mudanças genéticas ocorridas.
são divididasem medidas de distâncias e tipos de correlações. A primeira equação da tabela é
interpretada como a distância física entre dois pontos no espaço euclidiano, ou seja, distâncias
fixadas em coordenadas ortogonais (BOULOS; CAMARGO, 1987). Já a segunda distância
cityblock, também conhecida como manhattan, é a distância em uma configuração retilínea entre
dois pontos. Ambas as distâncias, euclidiana e cityblock, são derivadas da equação de distância
de minkowski. Note que para a cityblock o valor de r na equação de minkowski é 1. Já para a
euclidiana, r tem valor 2.
A distância calculada pelos métodos de Pearson correlation e Angular separation são
dependentes do coeficiente q8 9 . Este valor reflete a correlação entre os valores, sendo que valores
iguais a +1 indica forte relação positiva. Já valores iguais a -1 indica forte relação negativa entre
os elementos.
29
TABELA 3 – SIMILARIDADE MEDIDA PARA DADOS CONTÍNUIOS
Medidas Fórmula
D1: Distância
Euclidiana 38 9 =
[ ∑?
:=1 F
2
:
(G8: − G 9: )2
] 1/2
D2: Distância
City Block 38 9 =
∑?
:=1 F: |G8: − G 9: |
D3: Distância
Minkowski 38 9 =
( ∑?
:=1 F
A
:
|G8: − G 9: |A
) 1/A
(A ≥ 1)
D4: Distância
Canberra 38 9 =
{
0 para G8: = G 9: = 0∑?
:=1 F: |G8: − G 9: |/( |G8: + G 9: |) para G8: ≠ G 9: ≠ 0
D5: Correlação de
Pearson X8 9 = (1 − q8 9 )/2 com
q8 9 =
∑?
:=1 F: (G8: − G8∗ ) (G 9: − G 9∗ )
/
...
...
[ ∑?
:=1 F: (G8: − G8∗ )
2 ∑?
:=1 F: (G 9: − G 9∗ )
2
] 1/2
em que G8∗ =
∑?
:=1 F:G8:
/ ∑?
:=1 F:
D6: Separação
Angular X8 9 = (1 − q8 9 )/2 com
q8 9 =
∑?
:=1 F:G8:G 9:
/ ( ∑?
:=1 F:G
2
8:
∑?
:=1 F:G
2
9:
) 1/2
FONTE: Everitt et al. (2011)
2.4.2 Correção Modelo Evolutivo
Uma árvore baseada na distância não possui uma relação linear com o tempo decorrido
desde o último ancestral comum. Uma proposta para corrigir a distância calculada é levar em
consideração as taxas e probabilidades de substituições que podem ocorrer a cada intervalo
infinitesimal de tempo (3C). Existem diversos modelos que corrigem a diferença entre as sequências
levando-se em conta as probabilidades de trocas de nucelotídeos, o modelo Jukes-Cantor (JC69)
é o modelo evolutivo mais simples de correção para sequências de DNA (FELSENSTEIN, 2004).
Neste modelo, a taxa de mutação é a mesma independente da troca, ou seja, considera-se a mesma
taxa para transições (purina para purina, ou pirimidina para pirimidina) e para transversões
(purina para pirimidina e vice-versa). A figura 7 ilustra a taxa de mudanças entre todos os pares
de nucleotídeos por unidade de tempo.
30
FIGURA 7 – TAXAS DE MUDANÇAS DE PARES DE NUCLEOTÍDEOS POR UNIDADE DE TEMPO
PARA O MODELO JC69
FONTE: EGAN; CRANDALL(2006)
NOTA: Taxas de mudanças de pares de nucleotídeos por unidade de tempo para o modelo
JC69. Todas as taxas tem o mesmo valor para qualquer tipo de substituição.
A partir desse modelo pode-se inferir que a mudança de uma base aleatória para qualquer
uma das quatro bases possui uma taxa de 43D. Utilizando a distribuição de Poisson chega-se à
probabilidade de nenhum evento acontecer igual a EQUAÇÃO 2.5:
4
4
3DC (2.5)
Sendo, portanto, a probabilidade de pelo menos um evento de mudança de base ocorrer
igual a EQUAÇÃO 2.6.
1 − 4 43DC (2.6)
Desenvolvendo a expressão para a probabilidade de qualquer evento resultar em uma
mudança para um nucleotídeo específico e determinado, pode-se chegar à função de correção de
distâncias de Jukes-Cantor ( EQUAÇÃO 2.7), ou melhor, o modelo evolutivo de Jukes-Cantor
31
(FELSENSTEIN, 2004). Esta expressão nada mais é do que a estimativa de verossimilhança da
distância genética (LEMEY et al., 2009).
� = D̂C = −3
4
;=
(
1 − 4
3
�(
)
(2.7)
Uma das principais limitações práticas deste modelo é a descontinuidade da função
para o conjunto dos números reais para valores de distância entre sequências (�() maiores que
3
4 . Além disso, pode-se questionar os valores iguais para as taxas de mutações de nucleotídeos
independentemente se é uma transição ou transversão. Vários outros modelos foram desenvolvidos
para lidar com esses problemas, entre eles o modelo Kimura 2-parâmetros (K80), em que as
taxas de mudanças são distintas para transições e transversões. O modelo é representado na figura
8.
FIGURA 8 – TAXAS DE MUDANÇAS DE PARES DE NUCLEOTÍDEOS POR UNIDADE DE TEMPO
PARA O MODELO K80
FONTE: EGAN; CRANDALL(2006)
NOTA: Taxas de mudanças de pares de nucleotídeos por unidade de tempo para o modelo
K80. Taxas de transições (a) são diferentes das taxas de transversões (b).
32
As taxas de mudanças de nucleotídeos podem ser generalizadas pelo processo de Markov,
o qual utiliza a matriz Q para especificar cada troca de nucleotídeos. Essa matriz esta representada
pela EQUAÇÃO 2.8.
Q =
A C G T©­­­­­«
ª®®®®®¬
−`� `�� `�� `�) A
`�� −`� `�� `�) C
`�� `�� −`� `�) G
`)� `)� `)� −`) T
(2.8)
Ou seja, o modelo evolutivo JC69, com a mesma taxa de mutação para cada nucleotídeo,
tem a matriz Q representada pela EQUAÇÃO 2.9 (LEMEY et al., 2009).
Q =
A C G T©­­­­­«
ª®®®®®¬
−34`
1
4`
1
4`
1
4` A
1
4` −
3
4`
1
4`
1
4` C
1
4`
1
4` −
3
4`
1
4` G
1
4`
1
4`
1
4` −
3
4` T
(2.9)
Os modelos evolutivos Jukes-Cantor (JC69), Kimura 2-parâmetros (K80), Felsenstein
1981 (F81), Felsenstein 1984 (F84), Hasegawa, Kishino and Yano 1985 (HKY85), Tamura and
Nei 1993 (TN93) e Generalised time-reversible model of Tavaré 1986 (GTR) podem ter o valores
de taxas de mudanças representados pela matriz Q generalista representada na EQUAÇÃO 2.10,
em que ` é média instantânea da taxa de substituição; 0, 1, 2, 3, 4, 5 , 9 , ℎ, 8, 9 , :, ; são parâmetros
que descrevem a taxa de substituição de cada nucleotídeo por outro; c�, c� , c) , c� são valores
que representam a frequência dos respectivos nucleotídeos(LEMEY et al., 2009).
A C G T©­­­­­«
ª®®®®®¬
−`(0c�+1c� + 2c) ) 0`c� 1`c� 2`c)
6`c� −`(6c�+3c�+4c) ) 3`c� 4`c)
ℎ`c� 8`c� −`(ℎc�+ 9c�+ 5 c) ) 5 `c)
9 `c� :`c� ;`c� −`(6c�+3c�+4c) )
(2.10)
A partir desta matriz Q pode-se obter a matriz de qualquer modelo evolutivo citado. A
figura 9 ilustra a relação entre os modelos e como deve-se substituir cada parâmetro da matriz da
EQUAÇÃO 2.10.
33
FIGURA 9 – HIERARQUIA DOS MODELOS EVOLUTIVOS DE DNA
FONTE: LEMEY et al.(2009)
Além dos modelos evolutivos citados, existem diversos outros modelos já desenvolvidos.
O software para a construção de árvores filogenéticas IQ-TREE (NGUYEN et al., 2015), por
exemplo, lista em sua descrição para nucleotídeos 22 modelos comuns, 29 modelos de Lie-Markov,
18 para códons e 23 modelos evolutivos para aminoácidos, entre eles Blosum62, Dayhoff, JTT,
LG e WAG. Estima-se que mais de 200 modelos estejam disponíveis para o uso nesta ferramenta
(MINH et al., 2020). Há também softwares que comparam os modelos, encontrando o método
que melhor se ajusta aos problemas filogenéticos, entre eles o jModelTest (DARRIBA et al.,
34
2012).
2.4.3 Tipos de Clusterização
Os métodos de clusterização tem sido muito utilizados na ciência de mineração de dados,
reconhecimento de padrões e bioinformática. Pode-se dividir a técnica em duas abordagens, a
hierárquica e a não-hierárquica.
A abordagem hierárquica envolve fusões ou divisões de dados de maneira progressiva,
gerando grupos (clusters) que podem ser relacionados hierarquicamente em um dendrograma.
Já na abordagem não-hierárquica, a relação entre os dados particionados é indeterminada, não
criando relação de hierarquia. Além disso, os grupos são criados a partir de uma única partição
(KAUFMAN; ROUSSEEUW, 2009), e não em partições consecutivas, como nos modelos
hierárquicos. Essas abordagens são categorizadas conforme a figura 10.
FIGURA 10 – TIPOS DE CLUSTERIZAÇÃO
FONTE: adaptado de MA; CHOW(2004)
A construção de dendrogramas evolutivos dependem das técnicas de agrupamentos de
tipo hierárquico, uma vez que o objetivo é comparar grupos biológicos distribuídos entre seus
ascendentes e descendentes. Ou seja, a construção de árvores filogenéticas, a qual precisa da
relação hierárquica bem determinada (ROHLF, 1970).
As fusões e divisões de dados subdividema metodologia hierárquica em aglomerativo
e divisivo. Esses dois métodos são também referenciados como bottom-up e top-down, res-
pectivamente. No primeiro, a partir de n elementos, constrói-se a árvore agrupando-os em um
único cluster. Já no divisivo, ao contrário do aglomerativo, divide-se todo o conjunto de dados
agrupados em grupos mais homogêneos que o agrupamento originário. Em ambos os casos, os
clusters são representados por um dendrograma. A figura 11 exemplifica essa representação.
É importante ressaltar a principal desvantagem dos métodos hierárquicos: os dados uma
vez divididos ou aglomerados em novos grupos, não podem retornar ao agrupamento anterior.
Ou seja, o cluster resultante não pode retornar ao estado anterior à divisão ou fusão. Essa
característica é também a chave de sucesso do método, pois exige menor tempo de computação
(KAUFMAN; ROUSSEEUW, 2009). Porém, essa característica não impede que se compare
35
FIGURA 11 – TIPOS DE CLUSTERIZAÇÕES HIERÁRQUICAS
FONTE: adaptado de EVERITT et al.(2011)
a matriz de distância com o vetor cofenético que representa o dendrograma. Sokal e Rohlf
propuseram a avaliação dos dendrogramas pela relação entre a matriz e o vetor-dendrograma,
chamada de correlação cofenética (SOKAL; ROHLF, 1962). Porém, não é usual para comparações
entre árvores, os principais estudos para a distância entre árvores são discutidos na seção 2.5.
2.4.4 Métodos aglomerativos: bottom-up
Os principais métodos aglomerativos são: Single linkage, complete linkage e average
linkage (UPGMA), weighted average linkage (WPGMA) , centroid linkage (UPGMC) , median
linkage (WPGMC) e Ward (GORDON, 1987).
Para o primeiro deles, single linkage, a distância entre dois conjuntos (A e B) é
determinada a partir dos indivíduos mais similares entre A e B, ou seja, a menor distância entre
dois pontos de cada cluster, conforme ilustra a figura 12.
Esse método, também conhecido como nearest neighbour, considera a área que separa
os dois clusters. Entre todos os pares de objetos de diferentes clusters, seleciona-se o par com
maior similaridade (MANNING et al., 1999). Essa similaridade entre objetos de diferentes
conjuntos, determina a similaridade entre os clusters. Portanto, quanto menor a distância entre os
36
FIGURA 12 – AGRUPAMENTO SINGLE LINKAGE
FONTE: adaptado de SCHÜTZE et al.(2008)
pares, mais similares são os conjuntos entre si.
! (�, �) = <8=[3 (G�8,G�8 )] (2.11)
O single linkage é geralmente relacionado à árvore de expansão mínima, minimum
spanning tree (CIESLIK, 2006), a qual conecta todos os objetos com arestas de maior similaridade.
O método single linkage é localmente coerente, pois algomera os dados mais próximos, o que
graficamente pode gerar conjuntos estreitos e desbalanceados (EVERITT et al., 2011). Ele pode
ser aplicado de forma divisiva a partir de uma árvore de expansão mínima, removendo os pontos
mais distantes entre os grupos, criando assim, novos subgrupos.
Já o complete linkage, também conhecido por furthest neighbour, ao contrário do
anterior, avalia a similaridade entre dois conjuntos a partir dos elementos mais dissimilares
pertencentes a diferentes conjuntos, como ilustra a FIGURA 13. Ou seja, entre todos os pares de
objetos de diferentes clusters, seleciona-se o par com maior dissimilaridade, evitando conjuntos
alongados graficamente, pois avalia a similaridade de maneira global, resultando em conjuntos
mais compactos.
FIGURA 13 – AGRUPAMENTO COMPLETE LINKAGE
FONTE: adaptado de SCHÜTZE et al.(2008)
Esse tipo de agrupamento, segundo Everitt (EVERITT et al., 2011), tende a formar
37
clusters com diâmetros semelhantes. Sendo o diâmetro a maior diferença entre elementos de um
mesmo conjunto. Sua fórmula é a seguinte:
! (�, �) = <0G [3 (G�8,G�8 )] (2.12)
A principal desvantagem deste tipo clusterização é a complexidade do tempo (time
complexity). Enquanto a estratégia single linkage tem complexidade $ (=2), o método complete
linkage possui $ (=3), exigindo maior quantidade de comparação entre os elementos (MANNING
et al., 1999).
Muitas vezes as estratégias que consideram os elementos mais similares e menos
similares entre si não são as mais adequadas para o problema, surgindo, assim, uma terceira
forma de avaliar as distâncias entre os elementos de cada grupo, medindo-se a similaridade
média. Toma-se a distância entre os clusters como a média simples das distâncias entre cada
elemento de um cluster e cada elemento do outro cluster. A essa abordagem dá-se o nome de
group average linkage clustering.
FIGURA 14 – AGRUPAMENTO GROUP AVERAGE LINKAGE
FONTE: adaptado de SCHÜTZE et al.(2008)
Esta estratégia, assim como a single linkage, possui uma complexidade da ordem $ (=2)
no tempo, porém, sem a característica do single linkage de criar clusters alongados (MANNING
et al., 1999), portanto, sendo uma alternativa mais eficiente ao método complete linkage. Sua
fórmula é descrita segundo a EQUAÇÃO 2.13
! (�, �) = 1|=� | |=� |
∑
8n �
∑
9n �
� [8, 9] (2.13)
A abordagem aglomerativa baseada na média das distâncias pode ser UPGMA ou
WPGMA, siglas de unweighted pair-group method average e weighted pair-group method
average, respectivamente. No primeiro método, as distâncias contribuem igualmente para
obtenção da similaridade. Já no segundo, um maior peso é dado a pequenos clusters. Ambas
38
as estratégias agrupam elementos em clusters com baixa variância e possuem relativa robustez
(EVERITT et al., 2011).
Outra abordagem existente é o método de clusterização baseado nas distâncias entre
os centros geométricos (centroides) dos clusters, conhecido como centroid clustering. Se o
mesmo peso for dado para as distâncias euclidianas entre os clusters, o método é dito unweighted
pair-group method using the centroid approach (UPGMC) (EVERITT et al., 2011). Ainda,
segundo o mesmo autor, o método UPGMC funde os clusters com vetores médios mais similares a
partir de dados não tratados da matriz, ou seja, aos dados originais e não da matriz de proximidade.
O modelo weighted pair-group method using centroid approach (WPGMC) é similar ao
UPGMC, porém, todos os clusters são ponderados antes de se fundir os centroides semelhantes e
gerar um novo cluster. Isto é feito para evitar que dois grupos com tamanhos bem diferentes, ao
serem fundidos, gerem um novo cluster com um centroide muito parecido com o cluster com
maior centroide (HE, 1999). Assim, o novo cluster terá um centroide de valor intermediário entre
os cluster que deram origem. Ressalta-se que as fórmulas de centroid e median podem produzir
inversões no dendrograma a cada novo passo (MÜLLNER, 2011).
Em 1963, Ward introduziu um novo método de agrupamento de grupos, o método em
que a fusão é baseada no tamanho do erro do critério da soma dos quadrados (EVERITT et al.,
2011). O objetivo é, a cada novo estágio, minimizar o aumento da soma total dos quadrados
dentro do cluster. O método tende a gerar grupos esféricos de tamanhos semelhantes. Porém, ele
é muito sensível aos outliers.
Os passos tomados para cada algoritmo iniciam-se com as matrizes de distância entre
os elementos do conjunto a ser clusterizado. Encontrado o par (8, 9) que satisfaz a abordagem
de clusterização escolhida, agrupa-se o par num táxon c. Remove-se o par (8, 9) e adiciona-se o
táxon 2. Então calcula-se a distância de todos os elementos ao nó 2, com a EQUAÇÃO 2.14:
3 (2, :) = 3 (8, :) + 3 ( 9 , :)
2
(2.14)
É importante ressaltar que caso o espaço seja ultramétrico, essa distância será sempre a
mesma (HAUBOLD; WIEHE, 2006).
Entre os algoritmos de clusterização hierárquica mais utilizados estão UPGMA, já
citado, e o neighbor-joining. Este último desenvolvido por Sitou e Nei para a reconstrução de
árvores filogenéticas (SAITOU; NEI, 1987). Sua ampla difusão se dá pelo fato de o algoritmo
combinar eficiência computacional com razoável acurácia (CRANDALL; LAGERGREN, 2008).
Resumidamente, o método tem como entrada uma matriz de distância calculada a partir de
alguma métrica abordada no capítulo 2.4.1, e uma matriz chamada de matiz-Qé calculada através
39
da EQUAÇÃO 2.15.
&(8, 9) = 3 (8, 9) − 1
= − 2
( =∑
:≠8
3 (8, :) +
=∑
:≠ 9
3 ( 9 , :)
)
(2.15)
Em que, = é o número de espécies. 3 (8, 9) é a distância entre os elementos 8 e 9 . O par
com menor valor de &(8, 9), em que 8 ≠ 9 , são unidos gerando um novo nó, ou táxon c. Definido
o novo nó, calcula-se a distância de cada elemento ao novo nó com a fórmula 2.19.
3 (:, 2) = 1
2
[3 (8, :) + 3 ( 9 , :) − 3 (8, 9)], : ≠ 8, 9 (2.16)
Calcula-se e computa-se a distância do novo ramo aos táxons i e j.
3 (8, 2) = 1
2(= − 2)
[
(= − 2)3 (8, 9) +
( =∑
:≠8
3 (8, :) −
=∑
:≠ 9
3 ( 9 , :)
) ]
, : ≠ 8, 9 (2.17)
3 ( 9 , 2) = 1
2(= − 2)
[
(= − 2)3 (8, 9) +
( =∑
:≠8
3 ( 9 , :) −
=∑
:≠ 9
3 (8, :)
) ]
, : ≠ 8, 9 (2.18)
A cada novo nó constituído, substitui-se os táxons i e j por c, e reduz-se o tamanho do
conjunto de espécies em n-1. Caso o tamanho seja igual a um, gera-se o último ramo, logo, o
último passo é:
&(8, 9) = 3 (8, 9) (2.19)
2.4.5 Métodos divisivos: top-down
Com uma direção oposta ao método aglomerativo, esse método parte de um grupo denso
que contém todos os elementos, que, iterativamente, é dividido em dois agrupamentos menores.
Qualquer algoritmo de comparação pode ser utilizado no processo divisivo, incluindo
os anteriormente analisados no processo aglomerativo e algoritmos não-hierárquicos, o principal
problema dos algoritmos divisivos é o peso computacional de processamento (MANNING et al.,
1999). Enquanto algoritmos aglomerativos possuem possíveis combinações igual a �2= =
=(=−1)
2 ,
o método divisivo possui 2(=−1) − 1, ou seja, considera todas as possíveis divisões do grupo,
crescendo exponencialmente com a quantidade de elementos a serem clusterizados, por este fato
ele não é tão citado na literatura e é pouco utilizado (KAUFMAN; ROUSSEEUW, 2009).
O método divisivo pode ser monético ou politético. A abordagem monética utiliza uma
única variável para, a cada iteração, comparar e reagrupar os elementos. Por exemplo, agrupar
pessoas de acordo com a presença ou ausência de automóvel próprio. Isso gera uma matriz
binária a cada divisão, determinando a presença ou não de determinada característica em cada
40
grupo (EVERITT et al., 2011). Ainda, segundo o mesmo autor, a escolha da variável depende de
uma otimização de um critério que reflita a homogeneidade do grupo ou a associação com outras
variáveis, minimizando assim a quantidade de divisões.
Já na abordagem politética, várias características são analisadas no mesmo estágio de
divisão dos grupos. Como ela pode trabalhar com a matriz de proximidade, o método politético é
muito semelhante aos métodos aglomerativos de clusterização (EVERITT et al., 2011). Dentro
do cluster que reúne todos os elementos, escolhe-se o menos semelhante para iniciar um novo
grupo, assim, outros elementos mais semelhantes a este novo grupo começam a povoar este novo
cluster, e o processo se repete.
2.5 DISTÂNCIA ENTRE ÁRVORES
Medir a distância entre árvores filogenéticas é necessário, por exemplo, para estudar
como diferentes composições de sequências ou genes geram diferentes árvores, ou ainda, como
diferentes métodos de construção de árvores geram resultados diferentes.
Diversas métricas de medidas de dissimilaridade entre árvores foram desenvolvidas,
entre elas os métodos que consideram apenas a ordem das folhas da árvore, como: a distância
Robinson-Foulds - também conhecida como diferença simétrica ou unweighted-Robinson-Foulds,
distância entre quartetos e distância de alternância entre vizinhos mais próximos (JOMBART
et al., 2017).
Para computar a diferença simétrica entre duas árvores A e B, divide-se cada uma em
bipartições (FELSENSTEIN, 2004). Então soma-se a quantidade de partições contidas em A que
não estão contidas em B à quantidade de partições contidas em B que não estão contidas em A
(ROBINSON; FOULDS, 1979). A FIGURA 15 ilustra o processo. Note que todas as possíveis
bipartições estão representadas abaixo de sua respectiva árvore. As partições em negrito são as
que respeitam a definição do método, o que resulta em uma distância igual a 3 entre as árvores.
Há um grupo de métodos que consideram também o tamanho dos ramos para computar
a distância entre as árvores, são eles: a distância ponderada de Robinson-Foulds (weighted-
Robinson-Foulds), distância euclidiana, distância de branch score e distância geodésica, a qual
requer álgebra não euclidiana para a construção do espaço de árvores (tree space) (BILLERA
et al., 2001). Com exceção desta última, as anteriores são variações da diferença simétrica, porém,
inserindo os tamanhos dos ramos como pesos a cada diferença entre as árvores.
A distância geodésica, desenvolvida por Billera-Holmes-Vogtmann (BILLERA et al.,
2001), não considera um espaço euclidiano, mas sim um espaço curvado não-positivamente,
conhecido como espaço de Hadamard. Na realidade o tree space (ou BHV space, em homenagem
aos pesquisadores que definiram este espaço) é uma instância do espaço de Handamard (BACÁK,
2014). Neste espaço dois pontos estão conectados por um único e menor caminho em todo o
41
FIGURA 15 – CÁLCULO DE DISTÂNCIA SIMÉTRICA ENTRE AS DUAS ÁRVORES
FONTE: FELSENSTEIN(2004)
NOTA: Cálculo de distância simétrica entre as duas árvores. As arestas em negrito são arestas
que definem as bipartições. Os conjuntos abaixo de cada árvore representam as
partições possíveis e em negrito as que não pertencem ao grupo de comparação.
espaço, caminho esse chamado de geodésico (BILLERA et al., 2001). Assim, a distância entre
duas árvores é definida como a distância geodésica que conecta a árvore A à árvore B. Há uma
fundamentação algébrica bastante densa e formal para a definição do tree space e para o cálculo
desta distância. Esta definição foi desenvolvida algoritmicamente em 2008 (KUPCZOK et al.,
2008) e está disponível em diversos pacotes em R e Python.
O cálculos de distância entre árvores estão disponíveis nos pacotes PHANGORN
(SCHLIEP, 2011), APE (PARADIS et al., 2004), DISTORY (CHAKERIAN; HOLMES, 2013),
TREESPACE (JOMBART et al., 2017) e ADEPHYLO (JOMBART; DRAY, 2010) em R. Em
Python nos pacotes ETE3 Toolkit (HUERTA-CEPAS et al., 2016), Dendropy (SUKUMARAN;
HOLDER, 2010), Tree_compare (GORI et al., 2016).
2.6 PROCESSOS EVOLUTIVOS SIMULADOS
Um dos grandes desafios da biologia evolutiva computacional é a verificação dos
resultados e a possibilidade de se estabelecer avaliações comparativas entre diferentes métodos,
modelos, tipo e quantidade de dados disponíveis para o estudo. Essa dificuldade decorre do fato
de que a história evolutiva da entidades biológica são, geralmente, desconhecidas (DALQUEN
42
et al., 2012). Por isso, é de extrema importância a simulação de eventos evolutivos in silico.
Esta estratégia promove um ambiente de variáveis controladas que facilita os teste de robustez
e acurácia dos métodos de inferência filogenética (FLETCHER; YANG, 2009). Por exemplo,
pode-se avaliar como um método de inferência pode gerar diferentes respostas para diferentes
tipos de sequências (nucleotídeos ou aminoácidos), diferentes quantidades, tamanhos, taxa
evolutivas, escalas de tempo, modelos evolutivos entre outras características.
A simulação pode auxiliar no entendimento de filogenias reais, como a inferência de
enraizamentos de árvores de procariotos, a posição de determinadas linhagens sem uma origem
clara, teste de inferências de relógios moleculares (molecular clock) (DAVIN et al., 2020) entre
diversas outras aplicações. Vale ressaltar que o termo "filogenias reais"refere-se às inferências
calculadas pelo cientista, ou seja, filogenias não simuladas.
As possíveis aplicações dependem da cada programa de simulação. O programa ZOMBI
(DAVIN et al., 2020), por exemplo, permite inserir uma árvore filogenética real como entrada e,
sobre esta árvore, aplicar diferentes simulações de escala e taxas de mutações, permitindo assim
que se calibre a escala da árvore real com a escala obtida através da simulação.
O programa ALF permite a simulação de genomas inteiros, assimcomo simulação de
fusões, fissões e perda de genes (DALQUEN et al., 2012). O programa ALF e diversos outros
como INDELible (FLETCHER; YANG, 2009) permitem a simulação de inserções e deleções
de caracteres nas sequências (indels) e se diferenciam pelo modelo de distribuição e cálculo do
tamanho das inserções e deleções.
Dentre os programas citados, todos usam o algoritmo de Gillespie para simular o
processo evolucionário, ou alguma parte do processo. Este algoritmo é o padrão nas simulações
evolutivas, ele simula processos de Markov de tempo contínuo arbitrariamente complexos
(DAVIN et al., 2020) para um dado sistema químico. O algoritmo fornece cenários realistas
com simulações paralelas de eventos no nível da sequência e do genoma (DALQUEN et al.,
2012). Gillespie desenvolveu o algoritmo como alternativa a dois métodos formais de descrição
do comportamento do tempo de um sistema químico espacialmente homogêneo: a) abordagem
determinística que tenta resolver as equações diferenciais de taxas de reações; b) abordagem
estocástica que trata a evolução do tempo como um processo random-walk governado por uma
única equação diferencial denominada de master equation (GILLESPIE, 1977).
2.7 APRENDIZADO DE MÁQUINA (MACHINE LEARNING)
Os dados biológicos geralmente são difíceis de serem interpretados. Devido a sua
complexidade e grandes volumes, muitas vezes recorre-se à ciência de dados, em especial
Machine Learning (ML), para dar luz ao que os dados podem responder. Desde predição
de reposta a tratamentos contra o câncer (BAGAEV et al., 2021) a proposições de árvores
filogenéticas (BHATTACHARJEE; BAYZID, 2020) ou melhoras no processo de construção
43
dessas árvores (AZOURI et al., 2021).
Os modelos de ML podem ser classificados de acordo com algumas características
gerais, como: surpevisionado, não-supervisionado e de reforço. O modelo escolhido depende do
tipo de problema e do objetivo de se criar um modelo ML.
No modelo supervisionado, o sistema produz suas saídas baseado nos dados de entrada.
É preciso fornecer, nos dados de treinamento, tanto variáveis de entrada (input), quando os
valores de saída (output) para que o sistema "aprenda"as relações entre a entrada e saída. A
classificação de imagens em classes de animais é um exemplo de modelo supervisionado. Já o
sistema não-supervisionado tenta, a partir de dados não rotulados, reorganizar e criar classes que
respeitem alguma relação entre os dados (DAS, 2016). Neste caso, os métodos de construção de
árvores filogenéticas, tratados na seção 2.4, seriam exemplos de modelos não-supervisionados.
Já as diferenças entre regressão e classificação se dá pelo tipo de dado que o modelo
deve predizer. Quando o modelo deve processar os dados de input e entregar uma classe, ou seja,
uma escolha entre várias possibilidades, diz-se que o modelo é de classificação (SKIENA, 2020).
Porém, se o modelo deve entregar um valor contínuo, como a renda média anual de determinada
pessoa, ou o valor futuro de determinado ativo na bolsa de valores, define-se o modelo como de
regressão (MÜLLER; GUIDO, 2016).
A FIGURA 16 ilustra as diferentes aplicações de cada tipo de modelo de acordo com o
problema e o objetivo do cientista.
FIGURA 16 – MAPA DE DECISÕES PARA ENCONTRAR O MELHOR TIPO DE MODELO DE
MACHINE LERANING
FONTE: PEDREGOSA et al.(2011)
A escolha do modelo certamente passa pela avaliação do qual melhor se adapta ao seu
44
problema, mas também pelas medidas de qualidade que cada modelo oferece para cada tipo de
dados ou relações entre eles. As métricas mais difundidas e mais usuais para a validação do
modelo de clasificação são a taxa de acurácia, F1-score e (AMANCIO et al., 2014).
A medida de acurácia é, geralmente, a mais utilizada e considerada uma boa medida para
dados balanceados, ou seja, dados que possuam quantidades próximas de dados em cada classe
(STPOR, 2017). Caso os dados sejam desbalanceados, ou seja, exista significativa diferença entre
as quantidades de dados para cada classe, a medida F1-score é melhor, segundo Stapor. Esta
última depende tanto da taxa de acerto (true positive rate ou recall) e da taxa de falso negativo
(false negative rate ou precision). Ambas são calculadas a partir dos dados da matriz de confusão
na TABELA 4. Nesta tabela, as siglas são referentes aos termos em inglês, T é referente a true, F
a false, P a positive e N a negative.
TABELA 4 – MATRIZ DE CONFUSÃO
Predição Positiva Predição Negativa
Condição Positiva verdadeiro positivo (TP) falso negativo (FN)
Condição Negativa falso positivo (FP) verdadeiro negativo (TN)
FONTE: O Autor
As equações a seguir representam respectivamente o cálculo da acurácia (2.20), precision
(2.21), recall (2.22) e F1-score (2.23).
022 =
)% + )#
)% + �# + )# + �% (2.20)
?A428B8>= =
)%
)% + �% (2.21)
A420;; =
)%
)% + �# (2.22)
�1 − B2>A4 = 2 × ?A428B8>= × A420;;
?A428B8>= + A420;; (2.23)
Outra forma de mesurar a qualidade de um modelo de machine learning é traçar a
curva de recall vs 1-specificity (a EQUAÇÃO 2.24 refere-se ao cálculo da specificity), conhecida
como curva Receiver Operating Characteristic (ROC). Com a curva, calcula-se a área sob ela
(AUC: Area Under the Curve). Esta métrica é utilizada para contornar distorções na distribuição
das classes (STPOR, 2017). A área sob a curva ROC é calculada através do cálculo da integral
definida da curva.
B?428 5 828CH = 1 − �%
)# + �% (2.24)
45
3 MATERIAIS E MÉTODOS
Para uma análise sobre o impacto na árvore filogenética ao variar-se a quantidade de
sequências, o tamanho de sequências e a taxa de mutação, é necessário que exista um conjunto
de árvores com valores controlados para cada uma das variáveis. Isso é impraticável com árvores
reais, o controle destas características só pode ser feito, de forma ampla, com a simulação de
sequências e árvores filogenéticas teóricas ou ideais, chamadas aqui de árvores de referência.
Com as sequências simuladas, geram-se outras árvores calculadas por diferente métodos para
então avaliar as distância entre estas árvores e as de referência.
A proposição de modelos classificadores baseados em machine learning necessita de um
conjunto de dados grande e robusto. Infelizmente não há como projetar um modelo apenas com
as árvores presentes na literatura, o primeiro motivo é pela baixa quantidade de árvores curadas
e que sejam um consenso na comunidade científica. Um segundo motivo, é que o treinamento
seguiria apenas as relações criadas pelo métodos filogenéticos utilizados pelos cientistas, e não
de distintos métodos que possam convergir para uma mesma árvore. Por isso, o processo de
simulação das árvores também é essencial para o desenvolvimento do projeto.
Para melhor entender o experimento pode-se separá-lo em 7 etapas descritas a seguir e
ilustradas na figura FIGURA 17:
1. Simulação das árvores, sequências e alinhamentos tanto para sequências de aminoácidos
(AA) quanto para sequências nucleotídicas (NT);
2. Cálculo das matrizes de dissimilaridade (pairwise);
• Método dependente de alinhamento;
• Métodos independente de alinhamento;
3. Clusterização das matrizes de dissimilaridade;
4. Cálculo de distância (Robinson-Foulds) entre as árvores de referência geradas no item 1 e
as geradas no item 3.
5. Criação de classes de proximidade de distância baseados no valores relativos de Robinson-
Foulds.
6. Escolha da variáveis de entrada (features) do modelo de machine learning.
7. Escolha, treinamento e validação do modelo.
46
FIGURA 17 – PAINEL ESQUEMÁTICO DO EXPERIMENTO
FONTE: O Autor.
NOTA: A base do experimento é divida em quatro principais etapas: (1) Simulação das
árvores, sequências e alinhamentos; (2) Cálculo das matrizes de dissimilaridade
pelo método SWeeP (livre de alinhamento) e pelo EMBOSS (baseado em
alinhamento); (3) Clusterização das matrizes de dissimilaridade; (4) Cálculo das
distâncias entre as árvores de Referência e as calculadas.
3.1 ETAPA 1: SIMULAÇÃO DE ÁRVORES, SEQUÊNCIAS E ALINHAMENTOS
Para a geração in silico das árvores utilizou-se o programa INDELible(FLETCHER;
YANG, 2009). Este programa gera árvores ideais respeitando a teoria e os processos evolutivos
conhecidos. Isso permite gerar dendrogramas evolutivos com características definidas, como
quantidade de sequências, tamanho das sequências, taxa de mutação, escala da árvore, tipos de
modelos evolutivos, tipos de sequências (AA, NT ou códon), se a árvore é enraizada entre outras
variáveis.
Além das árvores ideais (referência), o INDELible gera as sequências e alinhamentos
que podem dar origem às árvores simuladas. Neste experimento gerou-se árvores combinando-se
as características de acordo com a TABELA 5. Os resultados foram obtidos tanto para sequências
simuladas de nucleotídeos (NT) quanto para aminoácidos (AA), sendo que o modelo evolutivo
para NT foi escolhido o F84, e para AA o Dayhoff, obtendo-se, portanto, 2508 árvores de
referência com sequências nucleotídicas e a mesma quantidade para árvores de aminoácidos.
Como o experimento é simulado, a escolha dos modelos evolutivos foi determinada
pelos modelos disponíveis tanto na ferramenta INDELibe quanto no EMBOSS (RICE et al.,
47
TABELA 5 – CARACTERÍSTICAS DA SIMULAÇÃO: QUANTIDADE, TAMANHO E TAXA DE
MUTAÇÃO
Características Valores
Quantidades de Sequências {10, 20, 30, ..., 110}
Tamanhos das Sequências {50, 75, 100 ..., 1450}
Taxas de Mutação {0.01, 0.1 , 0.5 , 1.0}
Modelos Evolutivos F84 (NT) e Dayhoff (AA)
Tipo Ultramétrica e Não Enraizada (unrooted)
FONTE: O Autor.
2000). Além disso, escolheu-se modelos que pudessem gerar menos erros possíveis durante
a obtenção das matrizes de distância. Como a função matemática do modelo F84 não possui
descontinuidade ou valores não pertencentes ao conjunto dos números reais, optou-se por
este modelo. Os experimentos com os modelos Jukes-Cantor e Kimura-2 parâmetros foram
abandonados, pois nestes modelos as transformações são dependentes de funções que geraram,
em várias simulações, valores não pertencentes ao conjunto dos números reais, impossibilitando
a criação de árvores a partir delas.
Uma vez geradas todas as árvores de referência, sequências e alinhamentos, dá-se
continuidade à etapa 2 com o cálculo das matrizes de distância das sequências e alinhamentos.
3.2 ETAPA 2: CÁLCULO DAS MATRIZES DE DISSIMILARIDADE
Com o intuito de também avaliar a proximidade das árvores de referência às árvores
geradas por métodos dependentes e independentes de alinhamento, dividiu-se esta etapa em duas
subetapas. A primeira calculando-se as matrizes de dissimilaridade a partir dos alinhamentos com
a ferramenta EMBOSS. Já a segunda etapa com a ferramenta SWEEP (DE PIERRI et al., 2020)
a partir das sequências não alinhadas, uma vez que esta ferramenta calcula a dissimilaridade sem
a necessidade de alinhamento.
3.2.1 Cálculo de matrizes dependentes de alinhamentos - EMBOSS
Com a ferramenta EMBOSS, cada alinhamento deu origem a uma única matriz de
dissimilaridade, ou seja, 2508 matrizes NT e outras 2508 matrizes AA. Para o cálculo das
matrizes de sequências nucleotídicas utilizou-se a função fdnadist e o modelo evolutivo F84. Já
para os alinhamentos de sequência de aminoácidos, a função utilizada foi a fprotdist e o modelo
evolutivo Dayhoff.
Calculadas as matrizes para cada alinhamento, segue-se para a obtenção das árvores
clusterizadas pelos métodos de distância na etapa 3.
48
3.2.2 Cálculo de matrizes independentes de alinhamentos - SWeeP
Se o EMBOSS gera uma única matriz corrigida para cada alinhamento, o SWeeP gera
um vetor representando cada conjunto de sequências. Para prosseguir com a clusterização, a
distância par a par (pairwise) entre cada elemento do vetor deve ser calculada. No experimento
com o SWeeP, os seguintes métodos de distância par a par foram avaliados: euclidean, kulsinski,
chebyshev, yule, russellrao, correlation, rogerstanimoto, sqeuclidean, canberra, dice, cityblock,
sokalsneath, cosine, braycurtis, sokalmichener, hamming, jaccard. As matrizes de distâncias par
a par foram calculadas através pacote Scipy (VIRTANEN et al., 2020). Com o método SWeep,
para cada conjunto de sequências de referência, pode-se gerar até 17 matrizes de distâncias, ou
seja, nesta etapa são calculadas 2508G17 matrizes de distâncias.
Para os cálculos dos vetores, manteve-se os argumentos padrões da função sweep tanto
para NT, quanto para AA. As matrizes de transformação ortonormais, necessárias para o cálculo, es-
tão as disponíveis em https://sourceforge.net/projects/spacedwordsprojection/.
3.3 ETAPA 3: CLUSTERIZAÇÃO DAS MATRIZES DE DISSIMILARIDADE
Com as matrizes de distância calculadas, segue-se para o agrupamento das sequências e
geração das árvores. Neste trabalho, foram geradas árvores com modelos clássicos de clusterização
pelo método da distância. Os métodos abordados são: single, complete, average, weighted, median,
centroid, ward e neighbor joining. A clusterização pelo método neighbor joining foi obtida
através do pacote Scikit-bio (TEAM, 2020), as demais pelo Scipy (VIRTANEN et al., 2020).
Para manter a padronização do experimento, todas as árvores calculadas foram ultramé-
tricas e não enraizadas. Como o método neighbor joining pode gerar árvores não ultramétricas,
usou-se o pacote ETE3 Toolkit (HUERTA-CEPAS et al., 2016) para forçar a transformação em
ultramétrica.
Este processo é repetido para cada árvore simulada. Por exemplo, o experimento para
uma árvore de referência gerada a partir de um conjunto de 10 sequências, com tamanho de 50
caracteres e taxa de mutação igual a 0.1, será comparada com as árvores geradas pelo EMBOSS
e pelo SWeeP. O processo que envolve o EMBOSS gerará apenas uma matriz de distância que
será clusterizada pelos métodos clássicos citados, ou seja, uma árvore simulada será comparada
com outras 8 geradas por distintos métodos. Já com o SWeeP, como exige o cálculo da matriz de
dissimilaridade durante o processo, calcula-se 17 diferentes métricas de dissimilaridade (citadas
anteriormente), e cada matriz resultante de cada métrica é clusterizada pelos 8 métodos distintos
de clusterização. Ou seja, no processo do SWeeP, cada árvore de referência será comparada a
outras 136 árvores.
Isso é feito para verificar qual métrica e método mais se aproxima da árvore de referência,
e como cada variação na característica das sequências afetam a acurácia dos métodos e métricas
de clusterização.
https://sourceforge.net/projects/spacedwordsprojection/
49
3.4 ETAPA 4: CÁLCULO DE DISTÂNCIA ENTRE AS ÁRVORES
Uma vez geradas todas as árvores a partir do alinhamento ou das sequências, calculou-
se as distâncias entre cada árvore obtida por diferentes métodos à sua referência (simulada).
Os métodos de distâncias calculados entre as árvores foram: Robinson-Foulds (S), Weighted-
Robinson-Foulds (W), Euclidean (E) e Geodesic Distance (G). A Geodesic Distance foi calculada
com o pacote TreeCL (GORI et al., 2016), as demais distâncias foram calculadas pelo pacote
Dendropy (SUKUMARAN; HOLDER, 2010). Apesar de todas as distâncias serem calculadas,
nem todas foram analisadas. As distâncias de Robinson-Foulds são usadas para medida de
similaridade da ordem dos clados, as demais também consideram o tamanho das arestas nos
cálculos de distâncias entre árvores que foram avaliadas. Porém, como as distâncias de Robinson-
Folds mantiveram-se altas, abandonou-se as análises com as distâncias W, S e G, pois as árvores
dissimilares, mas com alguns ramos similares e longos podem gerar falsos valores de proximidade.
Uma vez calculadas e normalizadas as distâncias entre árvores, fez-se a análise dos
dados obtidos a fim de saber quais métodos geraram os melhores resultados para as diferentes
configurações de árvores e sequências.
3.5 ETAPAS 5,6 E 7: CONSTRUÇÃO DO MODELO DE CLASSIFICAÇÃO DE ÁRVORES
FILOGENÉTICAS
Os resultados do experimento simulado na seção 3.1 foram utilizados para estruturação
e desenvolvimento de um modelo de classificação supervisionado de árvores filogenéticas. A
FIGURA 18 ilustra os dados utilizados nesta etapa. O objetivo é criar um modelo baseado em
machine learning queclassifique a qualidade da árvore a partir dos dados de distância das árvores
calculadas às árvores de referência. Para isso, seguiu-se os seguintes passos:
1. Definição das classes (labels): Definiu-se quatro classes a partir dos dados de dissimi-
laridade normalizada de Robinson-Foulds (D), são elas: � ≤ 0.25, 0.25 < � ≤ 0.50,
0.50 < � < 0.75 e � ≥ 0.75.
2. Definição das variáveis de entrada (features): Como features do modelo, utilizou-se
grandezas características das árvores, como raio e eficiência global, assim como relações
entre a matriz que identifica a árvore (matriz cofenética) e a matriz de distância que dá
origem à respectiva árvore.
3. Definição do modelo de aprendizado de máquina: Para a escolha do modelo, fez-se
diversos testes com diferentes modelos supervisionados de machine learning. Definiu-se o
modelo com base nas métricas de qualidade de cada modelo.
50
FIGURA 18 – PAINEL ESQUEMÁTICO DO EXPERIMENTO DEMONSTRANDO DADOS UTILI-
ZADOS PARA O DESENVOLVIMENTO DO MODELO DE MACHINE LEARNING
FONTE: O Autor.
NOTA: Os dados utilizados são as classes obtidas a partir dos dados de dissimilaridade entre
as árvores calculadas e as árvores de referência, assim como as características das
árvores cacluladas, como raio, eficiência global e coeficiente cofenético.
3.5.1 Definição das variáveis de entrada (features)
Primeiramente, considerou-se apenas características intrínsecas das árvores, como seu
raio e sua eficiência global. Porém, além dos valores de acurácia do modelo serem baixos (no
máximo 0.60), criou-se um modelo enviesado, pois apenas árvores com menores quantidades de
linhagens eram classificadas com distância de Robinson-Foulds normalizada menores ou igual a
0,25.
Para corrigir este viés, inseriu-se variáveis que representassem a qualidade da árvore
construída relação à matriz de distância que lhe deu origem. A maneira mais comum de se
mensurar essa relação é o cálculo do coeficiente cofenético, que é o valor da correlação de
pearson entre a matriz cofenética (matriz que representa a árvore) e a matriz de distância sobre a
qual a árvore é calculada.
Entre essas duas matrizes calculou-se também a correlação de spearman, permitindo
atingir valores de acurácia de até 0.80 ao inserir esta correlação ao modelo. As mesmas correlações
(pearson e spearman) foram calculadas entre os autovalores da matriz cofenética e os autovalores
da matriz de distância, ignorando-se as coordenadas imaginárias das relações. Para o cálculo das
relações entre matrizes cofenética e matrizes de distância, utilizou-se o pacote scipy (VIRTANEN
et al., 2020), já para os cálculos referentes ao raio e eficiência global das árvores, utilizou-se o
51
pacote networkx (HAGBERG et al., 2008).
3.5.2 Definição do modelo de aprendizado de máquina
Antes de treinar e validar o modelo, optou-se por normalizar os dados de entrada pela
método dos máximos e mínimos. Então separou-se 70% dos dados para treinamento do modelo, e
30% para a validação. Após pré-processamento dos dados, testou-se diversas técnicas de machine
learning, como Random Forest, Support Vector Machine (SVM), K-Nearest Neighbors (KNN)
e Multi-layer Perceptron (MLP). Para o desenvolvimento dos modelos, utilizou-se o pacote
scikit-learn (PEDREGOSA et al., 2011).
3.6 DELIMITAÇÃO DO EXPERIMENTO
O experimento proposto gera dados que podem responder a questões e problemas que
estejam de acordo com as delimitações e características abordadas neste projeto, que são:
• Sequências de nucleotídeos (NT) e aminoácidos (AA);
• Quantidades de sequências contidas no conjunto Q = {10, 20, 30, 40, 50, 60, 70, 80, 90,
100, 110};
• Tamanhos de sequências contidas no conjunto T = {50, 75, 100, 125, 150, 175, 200, 225,
250, 275, 300, 325, 350, 375, 400, 425, 450, 475, 500, 525, 550, 575, 600, 625, 650, 675,
700, 725, 750, 775, 800, 825, 850, 875, 900, 925, 950, 975, 1000, 1025, 1050, 1075, 1100,
1125, 1150, 1175, 1200, 1225, 1250, 1275, 1300, 1325, 1350, 1375, 1400, 1425, 1450};
• Taxas de mutações contidas no conjunto M = {0.01, 0.1 , 0.5 , 1.}
• Modelos evolutivos F84 para nucleotídeos e Dayhoff para aminoácidos.
• O tipos das árvores são não enraizadas e ultramétricas;
• As matrizes de distâncias consideradas são as matrizes de dissimilaridade;
• Para a etapa independente de alinhamento, as matrizes de distâncias são calculadas pelas
métricas euclidean, kulsinski, chebyshev, yule, russellrao, correlation, rogerstanimoto,
sqeuclidean, canberra, dice, cityblock, sokalsneath, cosine, braycurtis, sokalmichener,
hamming, jaccard;
• Os métodos de clusterização hierárquica abordados são single, complete, average, weighted,
median, centroid, ward e neighbor joining;
• As distâncias analisadas são as obtidas pelo método Robinson-Foulds normalizado;
• A classificação das árvores é limitada a quatro classes: � ≤ 0.25, 0.25 < � ≤ 0.50,
0.50 < � < 0.75 e � ≥ 0.75;
52
• As variáveis de entrada para classificar uma árvore filogenética são: raio, eficiência global,
correlação de pearson e spearman entre matriz cofenética e matriz de distância, correlação
de pearson e spearman entre autovalores da matriz cofenética e autovalores matriz de
distância.
3.7 LIMITAÇÕES DO EXPERIMENTO
Devido a grande quantidade de dados gerados e avaliados, as conclusões do experimento
não levam em consideração a comparação visual das árvores em relação à árvore de referência.
Ademais, o experimento não leva em consideração o nível de confiança dos clados de cada árvore,
ou seja, não efetuou-se processos como bootstrap e jacknife.
O experimento independente de alinhamento não teve suas matrizes corrigidas pelo
modelo evolutivo F84 para nucleotídeos e Dayhoff para aminoácidos, uma vez que não há
metodologia de aplicação destes modelos evolutivos a abordagens livres de alinhamento.
Outra importante limitação é a sujeição do experimento ao viés do programa INDELible
(FLETCHER; YANG, 2009). Não se pode afirmar categoricamente que os resultados aqui
obtidos sejam reproduzidos para árvores reais ou para árvores geradas por outros programas
desenvolvidos para a simulação evolutiva.
3.8 LISTA DE PACOTES E PROGRAMAS UTILIZADOS
Na TABELA 6 a seguir estão descritos programas e pacotes utilizados para o desenvol-
vimento do experimento.
53
TABELA 6 – RESUMO DE PROGRAMAS E PACOTES UTILIZADOS
Pacote /Programa Funções Usadas Objetivo
INDELible indelible Gerar árvores, sequências e alinhamentosde referência.
EMBOSS fdnadist, fprotdist Calcular a distância entre as sequências dereferência alinhadas.
SWeeP sweep() Gerar vetores a partir das sequências dereferência.
Scipy
scipy.spatial.distance(), scipy.spa-
tial.squareform(), scipy.cluster.hi-
erarchy(), scipy.stats.spearmanr(),
scipy.stats.pearsonr()
Cálculo das matrizes de distâncias, transfor-
mação das matrizes na forma condensada,
clusterização e cálculo de correlações de
spearman e pearson.
Scikit-learn
sklearn.preprocessing(), sklearn.mo-
del_selection(), sklearn.ensemble(),
sklearn.naive_bayes(),
sklearn.neighbors(),
sklearn.neural_network(), skle-
arn.metrics()
Normalização, seleção de dados de treino
e teste, treinamento de modelos, qualidade
de modelos.
Scikit-bio skbio.DistanceMatrix(),skbio.tree.nj()
Clusterização das matrizes pelo método
neighbor joining.
ETE Toolkit convert_to_ultrametric()
Forçar as árvores de referência e as calcula-
das por neighbor joining a serem ultramé-
trica.
Dendropy
get().as_string(),
symmetric_difference(),
euclidean_distance(),
weighted_robinson_foulds_
distance()
Leitura dos arquivos tipos newick e cálculos
das distâncias Robinson-Foulds, Weighted-
Robinson-Foulds, Euclidean
tree_distance getGeodesicDistance() Cálculos de Geodesic Distance entre asárvores.
Networkx
networkx.radius(), networkx.glo-
bal_efficiency(), networkx.resis-
tance_distance()
Cálculode raio, eficiência global e resistên-
cia das árvores
Bioconda Criação de ambiente virtual para instalaçãodos pacotes e programas.
FONTE: O Autor.
54
4 RESULTADOS E DISCUSSÃO
Este capítulo dedica-se a apresentar os resultadosobtidos e avaliar relações entre as
mais de um milhão e oitocentas distâncias calculadas (1.827.077). Os resultados apresentados
neste capítulo estão divididos em três principais partes. A primeira dedicada a avaliar os
resultados para o processo dependente de alinhamento. A segunda avalia os resultados para o
processo independente de alinhamento. Ressalta-se que as análises são separadas entre os tipos
de sequências - aminoácidos e nucleotídeos. E por fim, a terceira parte dedica-se à criação de um
modelo baseado em aprendizado de máquina para classificar árvores filogenéticas baseando-se
na sua relação a árvore de referência, ou seja, a árvore teórica.
4.1 RESULTADOS DEPENDENTES DE ALINHAMENTO
4.1.1 Sequências de nucleotídeos
Na figura FIGURA 19 (A), nota-se que o método neighbor joining (nj) apresenta uma
distribuição de dados mais próxima das árvores de referência. Os testes p-valor (Mann-Whitney-
Wilcoxon) da figura FIGURA 19 (B) confirmam a diferença estatística relevante dos demais
métodos, demonstrando que, para sequências nucleotídicas alinhadas, este é o melhor método de
clusterização dentre os abordados neste trabalho.
Esse comportamento se confirma nos gráficos C, D e E da figura FIGURA 19. As árvores
obtidas, para cada característica de sequência, que mais se aproximam da árvore referência são
as árvores obtidas por nj. Os gráficos C, D e E representam a média das distâncias para cada
agrupamento no eixo x. Por exemplo, para compor o gráfico C, calculou-se os valores médios
de distâncias para cada valor de quantidade de sequências (eixo x). O mesmo foi feito para o
gráficos D e E. Como apenas o método neighbor joining apresentou valores próximos às árvores
de referência, apenas as suas curvas serão analisadas.
É interessante notar que, conforme aumenta-se a quantidade de sequências, mais distante
da referência as árvores ficam. Uma direção parecida acontece em relação à taxa de mutação,
porém, com a diferença inicial da curva. Para uma mutação de 0,01, a menor taxa experimentada,
tem-se a maior distância da árvore de referência. A partir da taxa de mutação igual a 0,1, a curva
passa a ser acendente. Já a curva do tamanho da sequência tem uma comportamento inverso,
quanto menor o tamanho das sequências, maior a distância em relação à árvore de referência.
Conforme aumenta-se o tamanho da sequência, os valores se estabilizam, ou seja, as diferenças
possuem pouca variação.
Nos gráficos da FIGURA 20 é possível verificar se há diferenças estatísticas relevantes
55
FIGURA 19 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA NUCLEOTÍDICA E
DEPENDENTE DE ALINHAMENTO
FONTE: O Autor.
NOTA: Variação da distância à árvore de referência ao variar a quantidade de sequência, taxa
de mutação e o tamanho das sequências para sequências de nucleotídeos para
método dependente de alinhamento.
entre os pontos da curva do método nj, ou seja, se as árvores com sequências de tamanhos
diferentes são mais distantes das árvores de referência.
Para a quantidade de sequências, tem-se apenas a amostra de 10 sequências se dife-
renciando de todas as demais. Até 40 sequências há diferenças relevantes entre as amostras,
podendo-se dizer que há relativo aumento das distâncias quando varia-se de 10 a 40. Já para
quantidade acima de 40, pode-se dizer que a amostras não são diferentes entre si, ou seja, pode-se
aumentar a quantidade de sequências que a média da distância à referência não se altera de forma
relevante.
A variação da taxa de mutação também possui diferenças estatísticas significativas entre
si. Apenas a taxa de mutação igual a 0,1 não se diferencia da taxa de 0,5. Ao analisar o boxplot e
o histograma para variação dos tamanhos de sequência, é possível notar que até um tamanho
56
FIGURA 20 – BOXPLOTS DAS VARIAÇÕES DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA
NUCLEOTÍDICA E DEPENDENTE DE ALINHAMENTO
FONTE: O Autor.
NOTA: Boxplots das variações das distâncias à árvore de referência ao variar a quantidade de
sequência, taxa de mutação e o tamanho das sequências para sequências de
nucleotídeos. Heatmaps com p-valores da comparação entre cada conjunto. Para
método dependente de alinhamento.
de sequência de 975 nucleotídeos, há diferença entre as amostras, ou seja, pode-se dizer que
conforme aumenta-se o tamanho, mais o resultado se aproxima da árvore de referência. Porém,
ao analisar os pontos a partir de 975 do gráfico F da FIGURA 20, a maioria dos pontos maiores
ou iguais a 975 não se diferenciam entre si. Pode-se dizer, de forma generalizada, que a partir de
975 nucleotídeos, não há impacto relevante na diferenciação das árvores, isso ocorre devido ao
efeito de saturação abordado na seção 2.4.1.
4.1.2 Sequências de aminoácidos
Para sequências de aminoácidos (aa) é possível avaliar comportamento semelhante ao
já analisado para as sequências nucleotídicas. Na FIGURA 21 é possível verificar curvas das
médias com direções semelhantes às curvas de nucleotídeos para o método de neighbor joining.
Os boxplots e os heatmaps dos p-valores também são semelhantes, ou seja, diferença entre o
57
início e fim das curvas.
Na FIGURA 22 é possível verificar que o que se altera da análise de nucleotídeos
para aminoácidos é o limite da diferenciação, por exemplo, para a quantidade de sequências de
aminoácidos, a partir 30 sequências não há diferença estatística entre as amostras. Ou seja, a
partir 30 não se pode afirmar que a distância continuou aumentando, para nt esse limite era de 40.
Para a taxa de mutação só não há diferença entre as amostras de 0,1 e 1,0, demonstrando que
para uma taxa de 0,01, a árvores geradas realmente se distanciam da referência mais do que as
demais. Para o tamanho das sequências, semelhante à análise de nucleotídeos, pode-se dizer que
apenas o início da curva se diferencia das amostras ao final da curva. Percebe-se que de 50 a 800
aminoácidos, há uma diminuição da distância às árvores, já a partir de 800 aminoácidos não há
diferença estatística entre a maioria das amostras (com exceção do sample de 1375 aminoácidos).
Ou seja, a partir de 800 aminoácidos, ao aumentar o tamanho das sequências, não se pode afirmar
que a distância à árvore de referência diminui.
4.2 RESULTADOS INDEPENDENTES DE ALINHAMENTO
O método SWeeP, analisado nesta seção, gerou resultados diferentes do método depen-
dente de alinhamento. Antes de prosseguir é importante ressaltar que neste experimento não há
correção do modelo evolutivo. Por isso, a direção da curva é mais importante do que o valor de
distância à árvore, pelo menos até que algum método de correção evolutiva seja desenvolvido
para o método independente de alinhamento.
4.2.1 Sequências de nucleotídeos
Para este experimento pode-se notar na FIGURA 23 dois principais resultados diferentes
do experimento dependente de alinhamento: maiores curvas médias e, ao menos, 4 métodos de
clusterização geraram bons resultados em relação aos demais (nj, median, centroid e ward).
Não se pode afirmar o motivo de valores médios maiores, mas pode-se especular ao
menos dois. A falta de correção para o modelo evolutivo F84, ou, o método independente em
questão pode ser melhor aproveitado em outras combinações de características das sequências,
conforme já demonstrado em artigo sobre a ferramenta (DE PIERRI et al., 2020). Por este motivo,
a análise dos resultados é feita sem comparar a eficiência dos métodos dependentes com os
independentes de alinhamento. Este mesmo critério é adotado para a análise das sequências de
aminoácidos.
Além dos métodos nj, median, centroid e ward gerarem resultados melhores que os
58
FIGURA 21 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA DE AMINOÁCIDOS E
DEPENDENTE DE ALINHAMENTO
FONTE: O Autor.
NOTA: Variação da distância à árvore de referência ao variar a quantidade de sequência, taxa
de mutação e o tamanho das sequências para sequências de aminoácidos para
método dependente de alinhamento.
demais, é possível notar que a variação da taxa de mutação aumenta as distâncias médias das
árvores de referência de maneira significativa,ou seja, com considerável variação de 50,0 pontos
entre as taxas de mutação de 0,1 a 1,0 para os métodos median, centroid e ward. Além da taxa
crescente para a mutação, para a quantidade de sequências, também há aumento da distância com
o aumento da quantidade. E já com o aumento do tamanho das sequências, há um decréscimo
inicial da distância e uma estabilização também proveniente do efeito de saturação da medida de
distância entre sequências.
Para avaliar os 4 métodos com distâncias mais próximas da referência, verificou-se se
há relevância estatística entre as médias apresentadas na FIGURA 23 (B). Para melhor entender
o comportamento destes métodos, deve-se avaliar como cada métrica utilizada na obtenção das
matrizes de distância interferem na árvores final. A FIGURA 24 ilustra os valores das médias
para cada combinação de método-métrica. É possível visualizar que para nj, as melhores métricas
são euclidean, correlation, chebyshev e cosine, nesta ordem. O método weighted com a métrica
59
FIGURA 22 – BOXPLOTS DAS VARIAÇÕES DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA DE
AMINOÁCIDOS E DEPENDENTE DE ALINHAMENTO
FONTE: O Autor.
NOTA: Boxplots das variações das distâncias à árvore de referência ao variar a quantidade de
sequência, taxa de mutação e o tamanho das sequências para sequências de
aminoácidos. Heatmaps com p-valores da comparação entre cada conjunto. Para
método dependente de alinhamento.
sokalsneath também gerou um bom resultado. Os métodos centroid, median e ward, com a
métrica euclidiana, geraram resultados próximos aos obtidos por nj. Esses três métodos de
clusterização, por definição, só podem ser aplicados a matrizes calculadas pela métrica euclidiana,
por isso, para estes métodos, preencheu-se as outras métricas com valores médios máximos
(100% de diferença) para a construção da figura FIGURA 24.
Com os pares métricas-métodos com menores valores médios de distância, analisou-se
como as características de taxa de mutação, tamanho e quantidade de sequências afetam a árvore
final. Com os resultados da FIGURA 25 (A), pode-se notar que o método nj com a métrica cosine
apresenta os maiores valores de distâncias, seguido pelo método nj com a métrica chebyshev.
Estatisticamente a diferença desses dois pares aos demais é relevante, na FIGURA 25 (B) é possível
verificar os p-valores sinalizando tal diferença. Nesta mesma figura é possível verificar que entre
60
FIGURA 23 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA NUCLEOTÍDICA E
INDEPENDENTE DE ALINHAMENTO
FONTE: O Autor.
NOTA: Variação da distância à árvore de referência ao variar a quantidade de sequência, taxa
de mutação e o tamanho das sequências para sequências de nucleotídeos para
método independentes de alinhamento.
os pares weighted-sokalsneath, ward-euclidean, nj-euclidean, median-euclidean, nj-correlation
e centroid- euclidean não há diferença estatisticamente relevante, o que permite especular que as
árvores obtidas por um destes 6 pares método-métrica não geram resultados diferentes entre si,
pelo menos em termos de distância de Robinson-Foulds. Esta comportamento fica mais evidente
ao visualizar a semelhança entre as curvas de distâncias médias pela quantidade de sequências,
taxas de mutação e tamanho das sequências, FIGURA 25 (C, D e E), respectivamente.
É importante também verificar como os valores de distância método-métrica se diferen-
ciam para cada uma das características das sequências, a FIGURA 26 ilustra esse comportamento.
Para facilitar a visualização e explicação, apenas os heatmaps são mostrados. Porém, todas
as curvas seguem as mesmas direções das figuras anteriores. Com poucas diferenças entre os
pares métodos-métrica, é possível verificar que há aumento das distâncias com o aumento das
61
FIGURA 24 – DISTÂNCIA MÉDIAS DAS ÁRVORES DE SEQUÊNCIAS NUCLEOTÍDICAS E
INDEPENDENTES DE ALINHAMENTO
FONTE: O Autor.
NOTA: Distância médias das árvores geradas por métodos e métricas diferentes em sequências
de nucleotídeos para método independentes de alinhamento.
quantidades de sequência, a partir de 30 sequências para weighted-sokalsneath, nj-correlation e
centroid- euclidean pode-se dizer que não há diferença entre as amostras, ou seja, há aumento da
distância entre as amostras de 10 e 30 e após isso há uma certa estabilidade. Já para os pares
ward-euclidean, nj-euclidean e median-euclidean, o limite de diferenciação é de 20 sequências,
ou seja, há aumento da distância entre o intervalo 10 e 20, e então segue-se uma estabilidade de
distância entre as árvores calculadas e a referência.
Já o efeito da variação da taxa de mutação contatou-se diferença significativa para todos
os pares método-métrica para cada taxa. Ou seja, há uma queda da distância entre a taxa de 0,01
e 0,1, e após isso uma constante alta, podendo-se afirmar que, estatisticamente, a partir de 0,1 há
aumento da distância conforme aumenta-se a taxa de mutação.
Ao aumentar o tamanho da sequência obtém-se uma curva descendente de médias de
distâncias. Estes valores convergem para uma estabilidade próximo a um tamanho de sequências
a 250 nucleotídeos. Ou seja, a partir de 250 nucleotídeos, com poucas exceções, não há diferença
62
FIGURA 25 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA DE PARES MÉTODO-
MÉTRICA EM SEQUÊNCIAS NUCLEOTÍDICAS PARA MÉTODO INDEPENDENTES
DE ALINHAMENTO
FONTE: O Autor.
NOTA: Variação da distância à árvore de referência de pares método-métrica relevantes ao
variar a quantidade de sequência, taxa de mutação e o tamanho das sequências para
sequências de nucleotídeos para método independentes de alinhamento.
estatística relevante entre os valores médios das amostras. Pode-se especular que devido ao efeito
da saturação da dissimilaridade entre as sequências, os métodos de clusterização geram clusters
muito parecidos entre si.
4.2.2 Sequências de aminoácidos
Na FIGURA 27, para as sequências de aminoácidos, obteve-se direções parecidas das
curvas obtidas com nucleotídeos, porém, é interessante verificar que o patamar das curvas são
mais próximos da referência para as sequências de aminoácidos. É possível afirmar esta diferença
apenas para os métodos median, centroid e ward, uma vez que o método nj manteve-se distante
da árvore de referência em um patamar próximo ao calculado para nucleotídeos.
63
Para melhor entender o comportamento dos 4 principais métodos dessa análise, median,
centroid, ward e nj, calculou-se a média de distâncias da árvore de referência para cada par
método-métrica, as melhores médias podem ser vistas na figura FIGURA 28. Existem alguma
diferenças entre os resultados demonstrados nesta figura e os resultados para nucleotídeos da
FIGURA 24, porém, para a menores médias, o comportamento manteve-se o mesmo. Ou seja,
bons resultados da métrica euclidean para os métodos median, centroid e ward. Para nj com
as métricas euclidean, correlation, chebyshev e cosine, assim como para o método weighted
combinado com a métrica sokalsneath.
Com os melhores resultados de pares método-métrica para aminoácidos, é interessante
avaliar cada par e verificar o comportamento das curvas ao variar as características das sequências.
Esse comportamento pode ser visualizado na FIGURA 29 (A). Igualmente ao demonstrado
para sequências nucleotídicas, os pares nj-cosine e nj-chebyshev apresentaram as maiores
distâncias. Os pares métodos-métricas weighted-sokalsneath, ward-euclidean, nj-euclidean,
median-euclidean, nj-correlation e centroid-euclidean apresentaram menores valores médios
e, com exceção da comparação entre weighted-sokalsneath e median-euclidean, não possuem
diferenças estatísticas relevantes entre si, conforme FIGURA 29 (B). Pelo critérios de distância de
Robinson-Foulds, pode-se especular também que esses métodos geram árvores muito parecidas
entre si, a FIGURA 29 (C, D e E) também permitem chegar a esta conclusão, visto que as curvas
médias para cada característica são semelhantes.
Para entender melhor as curvas da FIGURA 29, avalia-se o quão diferente as amostras
são entre si e, principalmente, qual o pontode convergência das distâncias, ou seja, a partir de
qual valor a curva se estabiliza. Analisando os p-valores da FIGURA 30 é possível determinar
estes pontos. Com esta figura é possível especular que entre 10 e 30 sequências há um aumento da
distância de entre as árvores calculadas para os métodos em questão e as árvores de referência. E
a partir de 30 sequências, não há mais aumento estatisticamente relativo da distância ao aumentar
a quantidade das sequências, ou seja, pode-se dizer que a partir de 30 sequências, os resultados
convergem para um patamar de distância.
A taxa de mutação mantém o comportamento de queda da distância entre os valores
0,01 e 0,1, e a partir de 0,1 passa a se comportar, visualmente, como um reta ascendente, ou
seja, conforme aumenta-se a taxa de mutação, aumenta-se a distância. É interessante verificar na
FIGURA 29 (D) que o valor médio da distância em 0,01 é muito próximo ao valor da distância
para uma taxa de 0,5. Isso é confirmado pela FIGURA 30 (E, H e K), em que demonstra-se que
não há relevante diferença estatística entre estas duas amostras de taxas de mutação. É possível
também verificar nos heatmaps para taxa de mutação, que todos os valores de médias podem ser
64
considerados não-iguais, ou seja, pode-se dizer que há aumento da distância com o aumento da
taxa de mutação para os valores 0,1, 0,5 e 1,0.
Para as comparações dos valores de tamanho de sequência nota-se um aumento do limite
de convergência. É possível notar diferença entre as amostras até um valor de 450 de tamanho de
sequência de aminoácidos, em contraponto aos 250 para sequências nucleotídicas. Esse aumento
é esperado uma vez que se reduz o efeito da saturação com mais caracteres para se comparar.
Para diferenciar sequências de nucleotídeos tem-se até 4 caracteres diferentes para calcular a
dissimilaridade, já para sequências de aminoácidos tem-se até 20 caracteres.
4.3 TREINO E VALIDAÇÃO DO MODELO CLASSIFICADOR DE ÁRVORES FILOGENÉ-
TICAS
Com as árvores calculadas e com as distâncias entre árvores de referência, pode-se
projetar um modelo de classificação baseado em machine learning para predizer a qualidade de
cada árvore gerada de acordo com sua distância à árvore de referência. A função GridSearchCV()
do pacote scikit-learnig retornou as métricas de qualidade dos melhores hiperparâmetros para os
métodos KNN, MLP, Random Forest e SVM. O método que gerou melhores métricas de qualidade
foi o Random Forest, conforme TABELA 7 e TABELA 8.
A FIGURA 31 ilustra o processo de treinamento, com as etapas de seleção das features,
normalização da matriz de entrada, treinamento e teste do modelo e, por fim, a predição das
classes previamente definidas.
TABELA 7 – MELHORES MÉTRICAS OBTIDAS COM GRIDSEARCHCV
Método Accuracy mean Precision mean Recall mean F1 mean Média
Random Forest 0, 786 0, 788 0, 786 0, 787 0, 787
KNN 0, 735 0, 738 0, 735 0, 736 0, 736
MLP 0, 717 0, 717 0, 717 0, 715 0, 717
SVM 0, 674 0, 673 0, 674 0, 660 0, 670
FONTE: O Autor.
TABELA 8 – MELHORES HIPERPARÂMETROS OBTIDOS COM GRIDSEARCHCV
Método Hyperparâmetros
Random Forest ’criterion’: ’gini’, ’n_estimators’: 150
KNN ’algorithm’: ’auto’, ’n_neighbors’: 20, ’weights’: ’distance’
MLP ’activation’: ’relu’, ’learning_rate’: ’constant’, ’solver’: ’adam’
SVM ’C’: 5, ’degree’: 3, ’kernel’: ’rbf’
FONTE: O Autor.
65
A quantidade de elementos em cada classe foi balanceada, contendo 12745 elementos
em cada grupo. As classes e as features estão listadas a seguir.
• Classes: Distâncias de Robinson-Foulds (D).
– � ≤ 0, 25;
– 0, 25 < � ≤ 0, 50;
– 0, 50 < � < 0, 75;
– � ≥ 0, 75;
• Features:
– Raio da árvore;
– Eficiência Global da árvore;
– Relações entre matriz cofenética e matriz de distância;
∗ Coeficiente cofenético (pearson);
∗ Correlação de spearman;
– Relações entre os autovalores da matriz cofenética e da matriz de distância;
∗ Correlação de pearson;
∗ Correlação de spearman;
O método Random Forest gerou uma matriz de confusão com valores da diagonal
principal menos variáveis, conforme tabela TABELA 9. Ou seja, os valores de verdadeiros
positivos e verdadeiros negativos são bem mais elevados que os falsos positivos e falsos negativos.
É importante verificar que as classes � ≤ 0, 25 e � ≥ 0, 75 possuem os melhores
valores de acertos quando comparados às classes 0, 25 < � ≤ 0, 50 e 0, 50 < � < 0, 75.
Permitindo concluir que os valores intermediários podem predizer dados menos acurados que as
duas primeiras.
TABELA 9 – MATRIZ DE CONFUSÃO DE CADA CLASSE DO MODELO RANDOM FOREST
D <= 0,25 D >= 0,75 0,25 < D <= 0,50 0,50 < D < 0,75
D <= 0,25 3216(83%) 1(0%) 605(16,5%) 46(1,2%)
D >= 0,75 0(0%) 3268(86%) 14(0,04%) 514(13,5%)
0,25 < D <= 0,50 715(18,5%) 1(0%) 2687(69,5%) 465(12%)
0,50 < D < 0,75 73(1,9%) 318(8,5%) 495(13,5%) 2876(76,4%)
FONTE: O Autor.
66
Além disso, outras métricas também indicaram que o modelo pode classificar as árvores
com boa qualidade. Na tabela TABELA 10 encontra-se os valores médios de outras métricas.
TABELA 10 – MÉTRICAS MÉDIAS PARA VALIDAÇÃO DO MODELO RANDOM FOREST
Médias das Métricas Valores
Accuracy score 0, 79
Precision score 0, 79
Recall score 0, 79
F1 score 0, 79
FONTE: O Autor.
Na TABELA 11 tem-se as métricas do modelo detalhadas para cada classe. É possível
verificar que os melhores valores correspondem às classes � ≤ 0, 25 e � ≥ 0, 75.
TABELA 11 – MÉTRICAS DETALHADAS POR CLASSE PARA VALIDAÇÃO DO MODELO RAN-
DOM FOREST
Classes Precision Recall F1 score
� ≤ 0, 25 0, 80 0, 83 0, 81
� ≥ 0, 75 0, 91 0, 86 0, 88
0, 25 < � ≤ 0, 50 0, 71 0, 70 0, 70
0, 50 < � < 0, 75 0, 74 0, 76 0, 75
Accuracy 0, 79 0, 79 0, 79
Média Ponderada 0, 79 0, 79 0, 79
FONTE: O Autor.
Ao aplicar a técnica Cross Validation para gerar diferentes valores de acurácia para
diferentes dados de treino, os valores se concentraram entre 0,75 e 0,80, conforme FIGURA 32.
Demonstrando boa consistência nos resultados de acurácia.
A métrica de área sobre a curva ROC (auc) também possui valores satisfatórios para
este modelo. Todas as classes tem área acima de 0, 50 e se aproximam de 1, 00. As classes com
valores extremos de proximidade, � ≤ 0, 25 e � ≥ 0, 75, possuem as melhores métricas com
valores de área sob a curva ROC de 0.96 e 0.98, respectivamente. As classes 0, 25 < � ≤ 0, 50
e 0, 50 > � ≥ 0, 75 também possuem valores satisfatórios acima de 0, 90, 0, 91 e 0, 93
respectivamente.
4.4 TACOS: PACOTE PYTHON E APLICAÇÃO WEB
Os códigos criados para o desenvolvimento do projeto foram compilados em um pacote
em python para usuários avançados e, em um site amigável (FIGURA 34), aos usuário menos
67
familiarizados com linhas de códigos python.
O pacote e o site permitem, facilmente, que o usuário gere árvores pelos diferentes
métodos calculados nesta dissertação. Calcule distâncias entre as árvores filogenéticas abordadas
neste trabalho. Classifique as árvores de acordo com o modelo baseado em machine learning
desenvolvido nesta dissertação.
Os códigos, o pacote e o manual podem ser acessados no repositório https://github.
com/guilhermetabordaribas/tacos. Até a finalização deste trabalho, o web site ainda não
possui um endereço eletrônico registrado, por isso deixaremos no repositório o endereço do site
assim que adquirirmos.
https://github.com/guilhermetabordaribas/tacos
https://github.com/guilhermetabordaribas/tacos
68
FIGURA 26 – HEATMAP DE SIGNIFICÂNCIA DA VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE RE-
FERÊNCIA DE PARES MÉTODO-MÉTRICA EM SEQUÊNCIAS NUCLEOTÍDICAS
PARA MÉTODO INDEPENDENTES DE ALINHAMENTO
FONTE: O Autor.
NOTA: Heatmap da significância da variação da distância à árvore de referência de pares
método-métrica ao variar a quantidade de sequência, taxa de mutação e o tamanho
das sequências para sequências de nucleotídeos para método independentes de
alinhamento.
69
FIGURA 27 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA EM SEQUÊNCIAS DE
AMINOÁCIDOS PARA MÉTODO INDEPENDENTE DE ALINHAMENTO
FONTE: O Autor.
NOTA: Variação da distância à árvore de referência ao variar a quantidade de sequência, taxade mutação e o tamanho das sequências para sequências de aminoácidos para
método independentes de alinhamento.
70
FIGURA 28 – DISTÂNCIA MÉDIAS DAS ÁRVORES GERADAS POR MÉTODOS E MÉTRICAS
DIFERENTES EM SEQUÊNCIAS DE AMINOÁCIDOS PARA MÉTODO INDEPEN-
DENTES DE ALINHAMENTO.
FONTE: O Autor.
71
FIGURA 29 – VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE REFERÊNCIA DE PARES MÉTODO-
MÉTRICA EM SEQUÊNCIAS DE AMINOÁCIDOS PARA MÉTODO INDEPENDEN-
TES DE ALINHAMENTO.
FONTE: O Autor.
NOTA: Variação da distância à árvore de referência de pares método-métrica relevantes ao
variar a quantidade de sequência, taxa de mutação e o tamanho das sequências para
sequências de aminoácidos para método independentes de alinhamento.
72
FIGURA 30 – HEATMAP DA SIGNIFICÂNCIA DA VARIAÇÃO DA DISTÂNCIA À ÁRVORE DE RE-
FERÊNCIA DE PARES MÉTODO-MÉTRICA EM SEQUÊNCIAS DE AMINOÁCIDOS
PARA MÉTODO INDEPENDENTES DE ALINHAMENTO.
FONTE: O Autor.
NOTA: Heatmap da significância da variação da distância à árvore de referência de pares
método-métrica relevantes ao variar a quantidade de sequência, taxa de mutação e o
tamanho das sequências para sequências de aminoácidos para método
independentes de alinhamento.
73
FIGURA 31 – REPRESENTAÇÃO ESQUEMÁTICA DO PROCESSO DE MODELAGEM DO MÉ-
TODO RANDOM FOREST.
FONTE: O Autor.
NOTA: Representação esquemática do processo de modelagem do método Random Forest.
Após calculadas a variáveis de entrada (features), normaliza-se os dados pelo
método dos máximos e mínimos, treina-se o modelo informando com as classes
especificadas.
FIGURA 32 – RESULTADOS DE VALIDAÇÃO DO MODELO RANDOM FOREST.
FONTE: O Autor.
NOTA: Resultados de validação do modelo Random Forest treinado. Os resultados de
acurácia foram obtidos através da técnica cross validation.
74
FIGURA 33 – CURVAS ROC RANDOM FOREST DO MODELO.
FONTE: O Autor.
NOTA: Curvas ROC Random Forest do modelo. Todas as classes possuem valores de área sob
a curva acima de 0, 50 e próximos a 1, 00. São valores satisfatórios para o modelo.
FIGURA 34 – TACOS WEB SITE.
FONTE: O Autor.
NOTA: Página inicial do web site TACos: Trees Analyzer and Classifier (an open source tool).
75
5 CONCLUSÃO
Para o experimento baseado em alinhamento, fica evidente que o método neighbor
joining gera resultados muito melhores que os demais métodos de clusterização. Tanto para
sequência de aminoácidos quanto para sequências nucleotídicas. É interessante ressaltar que
os valores médios, para quaisquer variações de sequências, geraram melhores árvores do que o
método average, comumente utilizado para inferências filogenéticas. Isso pode impactar também
em métodos baseados em caracteres, que necessitam de uma árvore inicial como ponto de
partida. Fornecer uma árvore com maior acurácia, pode reduzir o tempo computacional destas
ferramentas.
Os experimentos com o SWeeP que geraram melhores resultados foram os pares método-
métrica weighted-sokalsneath, ward-euclidean, nj-euclidean, median-euclidean, nj-correlation e
centroid-euclidean. Tanto para sequência de nucleotídeos quanto para sequências de aminoácidos.
As curvas médias para cada características ficaram muito semelhantes, os primeiros
cinco métodos citados tiveram praticamente a mesma curva de comportamento para cada
característica, não sendo possível dizer se há um melhor método entre eles para as delimitações
deste experimento.
Quanto às características das sequência, é interessante notar que em todos experimentos
há aumento da distância conforme aumenta-se a quantidade de sequências. Pode-se especular que
quanto maior número de elementos maior a dificuldade de agrupá-los em clusters bem definidos
e distintos entre si. Outra característica que segue a mesma direção de correlação é a taxa de
mutação. Porém, a justificativa para o aumento da distância com o aumento da taxa de mutação é
mais evidente, facilmente explicada pelo efeito da saturação, ou seja, quanto maior a taxa de
mutação, menos a função p-distance reproduz a distância genética.
Já a direção do tamanho das sequências segue uma direção contrária, pelo menos até
a estabilização da curva de distância. Um proposta de explicação deste efeito é a nitidez dos
dados. Quando as sequências são muito curtas existem poucos caracteres, o que dificulta a
diferenciação entre eles pela simples somatória de matches e mismatches. Conforme aumenta-se
a quantidade, aumentando-se a nitidez das sequências, pode-se criar coleções mais distintas
entre si gerando valores mais variados de distância par a par entre as sequências. Porém, há
um limite de diferenciação pelos caracteres das sequências, conforme a sequências aumentam,
as chances de sequências diferentes gerarem resultados semelhantes de matches e mismatches
também aumentam.
Apesar dos resultados independentes de alinhamento apresentarem valores médios
superiores aos dados baseados em alinhamento, a comparação entre eles seria rasa, pois enquanto
o experimento com alinhamento foi corrigido para os mesmos modelos evolutivos usados na
76
geração das árvores teóricas, isso não pode ser feito com método de alignment-free. Pelo menos
enquanto um modelo de evolução não for desenvolvido.
O desenvolvimento de funções e distribuições de correção evolutiva é uma das pers-
pectivas futuras para o desenvolvimento das ferramentas livres de alinhamento. O que tornará
os resultados mais robustos para gerar respostas aos problemas que envolvam filogenia. Outra
proposta futura também importante é o desenvolvimento de testes de hipóteses e confiança para
métodos independentes de alinhamento, como bootstrapping e jackkniffe.
Quanto a classificação de árvores filogenéticas, o modelo Random Forest desenvolvido
mostrou-se satisfatório para a classificação das classes de dissimilaridade, ou seja, para predição
das classes � ≤ 0, 25, 0, 25 < � ≤ 0, 50, 0, 50 < � < 0, 75 e � ≥ 0, 75. Possuindo taxas de
acerto e correta rejeição acima de 80% para as classes extremas de similaridade e dissimilaridade
(� ≤ 0, 25 e � ≥ 0, 75) e próximo a 70% para as classes intermediárias (0, 25 < � ≤ 0, 50 e
0, 50 < � < 0, 75). A acurácia, precisão, recall e F1-score médios próximos a 80% demonstram
boa acertividade geral do modelo, fornecendo ao pesquisador resultados de classificação bem
melhores que a escolha aleatória de classes. Isso indica que o modelo pode auxiliar nos estudos
filogenéticos juntamente com outras ferramentas.
Com a metodologia de simulação evolutiva desenvolvida para o treinamento de modelos
classificadores, pode-se atingir valores ainda maiores dos indicadores de qualidade modelo. A
simulação de um número ainda maior de árvores, geradas por diferentes softwares, pode ajudar
a melhorar o modelo. As features utilizadas no projeto foram suficientes para a classificação
correta da maioria das árvores, porém, explorar outras variáveis que não relacionem a matriz
de distância ampliará a aplicação do modelo. Explorar outras variáveis que caraterizam apenas
o grafo, por exemplo, permitirá aplicar o modelo para classificar árvores geradas por métodos
baseados em caracteres, como método de bayes e verossimilhança.
77
REFERÊNCIAS
AMANCIO, D. R.; COMIN, C. H.; CASANOVA, D.; TRAVIESO, G.; BRUNO, O. M.;
RODRIGUES, F. A.; FONTOURA COSTA, L. da. A systematic comparison of supervised
classifiers. PloS one, Public Library of Science San Francisco, USA, v. 9, n. 4, e94137, 2014.
Citado 1 vez na página 44.
AZOURI, D.; ABADI, S.; MANSOUR, Y.; MAYROSE, I.; PUPKO, T. Harnessing machine
learning to guide phylogenetic-tree search algorithms. Nature communications, Nature
Publishing Group, v. 12, n. 1, p. 1–9, 2021. Citado 1 vez na página 43.
BACÁK, M. Convex analysis and optimization in Hadamard spaces. [S.l.]: Walter de
Gruyter GmbH & Co KG, 2014. v. 22. Citado 1 vez na página 40.
BAGAEV, A.; KOTLOV, N.; NOMIE, K.; SVEKOLKIN, V.; GAFUROV, A.; ISAEVA, O.;
OSOKIN, N.; KOZLOV, I.; FRENKEL, F.; GANCHAROVA, O. et al. Conserved pan-cancer
microenvironment subtypes predict response to immunotherapy. Cancer Cell, Elsevier, v. 39,
n. 6, p. 845–865, 2021.Citado 1 vez na página 42.
BHATTACHARJEE, A.; BAYZID, M. S. Machine learning based imputation techniques for
estimating phylogenetic trees from incomplete distance matrices. BMC genomics, Springer,
v. 21, n. 1, p. 1–14, 2020. Citado 1 vez na página 42.
BILLERA, L. J.; HOLMES, S. P.; VOGTMANN, K. Geometry of the space of phylogenetic
trees. Advances in Applied Mathematics, Elsevier, v. 27, n. 4, p. 733–767, 2001. Citado 3
vezes nas páginas 40, 41.
BLUM, A.; HOPCROFT, J.; KANNAN, R. Foundations of data science. Vorabversion eines
Lehrbuchs, p. 208, 2016. Citado 1 vez na página 25.
BOULOS, P.; CAMARGO, I. de. Geometria analtica: um Tratamento Vetorial. São Paulo:
McGraw-Hill, 1987. Citado 1 vez na página 28.
CASTRO-NALLAR, E.; PÉREZ-LOSADA, M.; BURTON, G. F.; CRANDALL, K. A. The
evolution of HIV: inferences using phylogenetics. Molecular phylogenetics and evolution,
Elsevier, v. 62, n. 2, p. 777–792, 2012. Citado 1 vez na página 15.
78
CAVALLI-SFORZA, L.; EDWARDS, A. The reconstruction of evolution. Ann. Hum. Genet,
v. 27, p. 105–106, 1963. Citado 1 vez na página 21.
CHAKERIAN, J.; HOLMES, S. distory: Distance Between Phylogenetic Histories. URL
http://CRAN. R-project. org/package= distory. R package version, v. 1, n. 1, 2013. Citado 1
vez na página 41.
CIESLIK, D. Shortest connectivity: an introduction with applications in phylogeny. [S.l.]:
Springer Science & Business Media, 2006. v. 17. Citado 1 vez na página 36.
COCK, P. J.; ANTAO, T.; CHANG, J. T.; CHAPMAN, B. A.; COX, C. J.; DALKE, A.;
FRIEDBERG, I.; HAMELRYCK, T.; KAUFF, F.; WILCZYNSKI, B. et al. Biopython: freely
available Python tools for computational molecular biology and bioinformatics. Bioinformatics,
Oxford University Press, v. 25, n. 11, p. 1422–1423, 2009. Citado 1 vez na página 27.
CRANDALL, K.; LAGERGREN, J. Algorithms in Bioinformatics: 8th International
Workshop, WABI 2008, Karlsruhe, Germany, September 15-19, 2008, Proceedings. [S.l.]:
Springer, 2008. v. 5251. Citado 1 vez na página 38.
DALQUEN, D. A.; ANISIMOVA, M.; GONNET, G. H.; DESSIMOZ, C. ALFa simulation
framework for genome evolution. Molecular biology and evolution, Oxford University Press,
v. 29, n. 4, p. 1115–1123, 2012. Citado 3 vezes nas páginas 41, 42.
DARRIBA, D.; TABOADA, G. L.; DOALLO, R.; POSADA, D. jModelTest 2: more models,
new heuristics and parallel computing. Nature methods, Nature Publishing Group, v. 9, n. 8,
p. 772–772, 2012. Citado 1 vez na página 33.
DAS, S. R. Data science: theories, models, algorithms, and analytics. [S.l.], 2016. Citado 1
vez na página 43.
DAVIN, A. A.; TRICOU, T.; TANNIER, E.; VIENNE, D. M. de; SZÖLLSI, G. J. Zombi: a
phylogenetic simulator of trees, genomes and sequences that accounts for dead linages.
Bioinformatics, Oxford University Press, v. 36, n. 4, p. 1286–1288, 2020. Citado 3 vez na
página 42.
DE PIERRI, C. R.; VOYCEIK, R.; MATTOS, L. G. C. S. de; KULIK, M. G.; CAMARGO, J. O.;
OLIVEIRA, A. M. R. de; LIMA NICHIO, B. T. de; MARCHAUKOSKI, J. N.;
SILVA FILHO, A. C. da; GUIZELINI, D. et al. SWeeP: representing large biological sequences
79
datasets in compact vectors. Scientific reports, Nature Publishing Group, v. 10, n. 1, p. 1–10,
2020. Citado 4 vezes nas páginas 19, 25, 47, 57.
DENCKER, T.; LEIMEISTER, C.-A.; GERTH, M.; BLEIDORN, C.; SNIR, S.;
MORGENSTERN, B. Multi-SpaM: a maximum-likelihood approach to phylogeny
reconstruction using multiple spaced-word matches and quartet trees. NAR Genomics and
Bioinformatics, Oxford University Press, v. 2, n. 1, lqz013, 2020. Citado 1 vez na página 24.
EGAN, A. N.; CRANDALL, K. A. Theory of phylogenetic estimation. Evolutionary Genetics:
Concepts and Case Studies, Oxford University Press London, v. 1, p. 426–436, 2006. Citado 0
vezes nas páginas 30, 31.
EVERITT, B. S.; LANDAU, S.; LEESE, M.; STAHL, D. Cluster analysis 5th ed. [S.l.]: John
Wiley, 2011. Citado 9 vezes nas páginas 26, 29, 35, 36, 38, 40.
EWENS, W. J.; GRANT, G. R. Statistical methods in bioinformatics: an introduction. [S.l.]:
Springer Science & Business Media, 2006. P. 501, 510, 523. Citado 2 vezes nas páginas 19, 22.
FAN, H.; IVES, A. R.; SURGET-GROBA, Y.; CANNON, C. H. An assembly and
alignment-free method of phylogeny reconstruction from next-generation sequencing data. BMC
genomics, BioMed Central, v. 16, n. 1, p. 1–18, 2015. Citado 3 vezes nas páginas 23–25.
FELSENSTEIN, J. Confidence limits on phylogenies: an approach using the bootstrap.
Evolution, Wiley Online Library, v. 39, n. 4, p. 783–791, 1985. Citado 3 vezes nas páginas 16,
22, 23.
. Inferring phylogenies. [S.l.]: Sinauer associates Sunderland, MA, 2004. Citado 7
vezes nas páginas 21, 22, 29, 31, 40, 41.
. Statistical inference of phylogenies. Journal of the Royal Statistical Society: Series
A (General), Wiley Online Library, v. 146, n. 3, p. 246–262, 1983. Citado 1 vez na página 15.
FLETCHER, W.; YANG, Z. INDELible: a flexible simulator of biological sequence evolution.
Molecular biology and evolution, Oxford University Press, v. 26, n. 8, p. 1879–1888, 2009.
Citado 4 vezes nas páginas 42, 46, 52.
FREEMAN, S.; HERRON, J. C. Análise evolutiva. [S.l.]: Artmed Editora, 2009. P. 111, 128.
Citado 1 vez na página 18.
80
GILLESPIE, D. T. Exact stochastic simulation of coupled chemical reactions. The journal of
physical chemistry, ACS Publications, v. 81, n. 25, p. 2340–2361, 1977. Citado 1 vez na
página 42.
GORDON, A. D. A review of hierarchical classification. Journal of the Royal Statistical
Society: Series A (General), Wiley Online Library, v. 150, n. 2, p. 119–137, 1987. Citado 1 vez
na página 35.
GORI, K.; SUCHAN, T.; ALVAREZ, N.; GOLDMAN, N.; DESSIMOZ, C. Clustering genes of
common evolutionary history. Molecular biology and evolution, Oxford University Press,
v. 33, n. 6, p. 1590–1605, 2016. Citado 2 vezes nas páginas 41, 49.
HAGBERG, A.; SWART, P.; S CHULT, D. Exploring network structure, dynamics, and
function using NetworkX. [S.l.], 2008. Citado 1 vez na página 51.
HALL, B. G. Building phylogenetic trees from molecular data with MEGA. Molecular biology
and evolution, Society for Molecular Biology e Evolution, v. 30, n. 5, p. 1229–1235, 2013.
Citado 2 vezes nas páginas 18, 19.
HAUBOLD, B.; WIEHE, T. Introduction to computational biology: an evolutionary
approach. [S.l.]: Springer Science & Business Media, 2006. P. 152, 151. Citado 4 vezes nas
páginas 19–21, 38.
HE, Q. A review of clustering algorithms as applied in IR. Graduate School of Library and
nformation Science University of llinois at Urbana-Compaign, v. 6, p. 1–33, 1999. Citado 1
vez na página 38.
HILLIS, D. M.; MORITZ, C.; MABLE, B. K.; OLMSTEAD, R. G. Molecular systematics.
[S.l.]: Sinauer Associates Sunderland, MA, 1996. v. 23. Citado 1 vez na página 21.
HUERTA-CEPAS, J.; SERRA, F.; BORK, P. ETE 3: reconstruction, analysis, and visualization
of phylogenomic data. Molecular biology and evolution, Society for Molecular Biology e
Evolution, v. 33, n. 6, p. 1635–1638, 2016. Citado 2 vezes nas páginas 41, 48.
JILL HARRISON, C.; LANGDALE, J. A. A step by step guide to phylogeny reconstruction. The
Plant Journal, Wiley Online Library, v. 45, n. 4, p. 561–572, 2006. Citado 1 vez na página 19.
81
JOMBART, T.; DRAY, S. adephylo: exploratory analyses for the phylogenetic comparative
method. Bioinformatics, v. 26, p. 1907–1909, 2010. Disponível em:
10.1093/bioinformatics/btq292. Citado 1 vez na página 41.
JOMBART, T.; KENDALL, M.; ALMAGRO-GARCIA, J.; COLIJN, C. treespace: Statistical
exploration of landscapes of phylogenetic trees. Molecular ecology resources, Wiley Online
Library, v. 17, n. 6, p. 1385–1392, 2017. Citado 2 vezes nas páginas 40, 41.
KAUFMAN, L.; ROUSSEEUW, P. J. Finding groups in data: an introduction to cluster
analysis. [S.l.]: John Wiley & Sons, 2009. v. 344, p. 253. Citado 3 vezes nas páginas 34, 39.
KUPCZOK, A.; HAESELER, A. V.; KLAERE, S. An exact algorithm for the geodesic distance
between phylogenetic trees. Journal of Computational Biology, Mary Ann Liebert, Inc. 2
Madison Avenue Larchmont, NY 10538 USA, v. 15, n. 6, p. 577–591,2008. Citado 1 vez na
página 41.
LEMEY, P.; HONG, S. L.; HILL, V.; BAELE, G.; POLETTO, C.; COLIZZA, V.; OTOOLE, Á.;
MCCRONE, J. T.; ANDERSEN, K. G.; WOROBEY, M. et al. Accommodating individual travel
history and unsampled diversity in Bayesian phylogeographic inference of SARS-CoV-2.
Nature communications, Nature Publishing Group, v. 11, n. 1, p. 1–14, 2020. Citado 1 vez na
página 15.
LEMEY, P.; SALEMI, M.; VANDAMME, A.-M. The phylogenetic handbook: a practical
approach to phylogenetic analysis and hypothesis testing. [S.l.]: Cambridge University Press,
2009. P. 26, 16, 157. Citado 10 vezes nas páginas 15, 19, 22, 23, 27, 28, 31–33.
LEWITUS, E.; MORLON, H. Characterizing and comparing phylogenies from their Laplacian
spectrum. Systematic biology, Oxford University Press, v. 65, n. 3, p. 495–507, 2015. Citado 1
vez na página 15.
LI, T.; LIU, D.; YANG, Y.; GUO, J.; FENG, Y.; ZHANG, X.; CHENG, S.; FENG, J.
Phylogenetic supertree reveals detailed evolution of SARS-CoV-2. Scientific reports, Nature
Publishing Group, v. 10, n. 1, p. 1–9, 2020. Citado 1 vez na página 15.
MA, E. W.; CHOW, T. W. A new shifting grid clustering algorithm. Pattern recognition,
Elsevier, v. 37, n. 3, p. 503–514, 2004. Citado 1 vezes nas páginas 25, 34.
82
MAHAPATRO, G.; MISHRA, D.; SHAW, K.; MISHRA, S.; JENA, T. Phylogenetic tree
construction for DNA sequences using clustering methods. Procedia engineering, Elsevier,
v. 38, p. 1362–1366, 2012. Citado 2 vezes nas páginas 15, 18.
MANNING, C. D.; MANNING, C. D.; SCHÜTZE, H. Foundations of statistical natural
language processing. [S.l.]: MIT press, 1999. P. 503, 506, 507, 513. Citado 4 vezes nas
páginas 35, 37, 39.
MINH, B. Q.; SCHMIDT, H. A.; CHERNOMOR, O.; SCHREMPF, D.; WOODHAMS, M. D.;
VON HAESELER, A.; LANFEAR, R. IQ-TREE 2: New models and efficient methods for
phylogenetic inference in the genomic era. Molecular biology and evolution, Oxford
University Press, v. 37, n. 5, p. 1530–1534, 2020. Citado 1 vez na página 33.
MÜLLER, A. C.; GUIDO, S. Introduction to machine learning with Python: a guide for
data scientists. [S.l.]: "O’Reilly Media, Inc.", 2016. Citado 1 vez na página 43.
MÜLLNER, D. Modern hierarchical, agglomerative clustering algorithms. arXiv preprint
arXiv:1109.2378, 2011. Citado 1 vez na página 38.
NGUYEN, L.-T.; SCHMIDT, H. A.; VON HAESELER, A.; MINH, B. Q. IQ-TREE: a fast and
effective stochastic algorithm for estimating maximum-likelihood phylogenies. Molecular
biology and evolution, Oxford University Press, v. 32, n. 1, p. 268–274, 2015. Citado 1 vez na
página 33.
PARADIS, E.; CLAUDE, J.; STRIMMER, K. APE: analyses of phylogenetics and evolution in R
language. Bioinformatics, Oxford University Press, v. 20, n. 2, p. 289–290, 2004. Citado 1 vez
na página 41.
PEDREGOSA, F.; VAROQUAUX, G.; GRAMFORT, A.; MICHEL, V.; THIRION, B.;
GRISEL, O.; BLONDEL, M.; PRETTENHOFER, P.; WEISS, R.; DUBOURG, V.;
VANDERPLAS, J.; PASSOS, A.; COURNAPEAU, D.; BRUCHER, M.; PERROT, M.;
DUCHESNAY, E. Scikit-learn: Machine Learning in Python. Journal of Machine Learning
Research, v. 12, p. 2825–2830, 2011. Citado 1 vezes nas páginas 43, 51.
POSADA, D.; CRANDALL, K. A. Modeltest: testing the model of DNA substitution.
Bioinformatics (Oxford, England), v. 14, n. 9, p. 817–818, 1998. Citado 1 vez na página 19.
83
PUIGBÒ, P.; WOLF, Y. I.; KOONIN, E. V. Genome-Wide Comparative Analysis of
Phylogenetic Trees: The Prokaryotic Forest of Life. In: EVOLUTIONARY Genomics. [S.l.]:
Springer, 2019. P. 241–269. Citado 1 vez na página 16.
RICE, P.; LONGDEN, I.; BLEASBY, A. EMBOSS: the European molecular biology open
software suite. Trends in genetics, Elsevier current trends, v. 16, n. 6, p. 276–277, 2000. Citado
2 vezes nas páginas 27, 46.
RIZZO, J.; ROUCHKA, E. C. Review of phylogenetic tree construction. University of
Louisville Bioinformatics Laboratory Technical Report Series, p. 2–7, 2007. Citado 3 vezes
nas páginas 16, 18–20.
ROBINSON, D. F.; FOULDS, L. R. Comparison of weighted labelled trees. In:
COMBINATORIAL mathematics VI. [S.l.]: Springer, 1979. P. 119–126. Citado 1 vez na
página 40.
ROHLF, F. J. Adaptive hierarchical clustering schemes. Systematic Biology, Society of
Systematic Zoology, v. 19, n. 1, p. 58–82, 1970. Citado 1 vez na página 34.
SAITOU, N.; NEI, M. The neighbor-joining method: a new method for reconstructing
phylogenetic trees. Molecular biology and evolution, v. 4, n. 4, p. 406–425, 1987. Citado 1 vez
na página 38.
SCHLIEP, K. P. phangorn: phylogenetic analysis in R. Bioinformatics, Oxford University Press,
v. 27, n. 4, p. 592–593, 2011. Citado 1 vez na página 41.
SCHÜTZE, H.; MANNING, C. D.; RAGHAVAN, P. Introduction to information retrieval.
[S.l.]: Cambridge University Press Cambridge, 2008. v. 39. Citado 0 vezes nas páginas 36, 37.
SKIENA, S. S. The algorithm design manual. [S.l.]: Springer International Publishing, 2020.
Citado 1 vez na página 43.
SOKAL, R. R.; ROHLF, F. J. The comparison of dendrograms by objective methods. Taxon,
Wiley Online Library, v. 11, n. 2, p. 33–40, 1962. Citado 1 vez na página 35.
STPOR, K. Evaluating and comparing classifiers: Review, some recommendations and
limitations. In: SPRINGER. INTERNATIONAL Conference on Computer Recognition Systems.
[S.l.: s.n.], 2017. P. 12–21. Citado 2 vez na página 44.
84
STRATHERN, P. Mendeleyev’s dream: the quest for the elements. [S.l.]: Macmillan, 2001.
Citado 1 vez na página 25.
STRICKLER, P. A brief review of the common tree-building methods used in phylogenetic
inference. [S.l.: s.n.], 2014. Citado 1 vez na página 21.
SUKUMARAN, J.; HOLDER, M. T. DendroPy: a Python library for phylogenetic computing.
Bioinformatics, Oxford University Press, v. 26, n. 12, p. 1569–1571, 2010. Citado 2 vezes nas
páginas 41, 49.
TEAM, T. scikit-bio development. scikit-bio: A Bioinformatics Library for Data Scientists,
Students, and Developers. [S.l.], 2020. Disponível em: http://scikit-bio.org. Citado 1 vez na
página 48.
VERLI, H. Bioinformática: da biologia à flexibilidade molecular. Sociedade Brasileira de
Bioqumica e Biologia Molecular, 2014. Citado 2 vezes nas páginas 15, 19.
VINGA, S.; ALMEIDA, J. Alignment-free sequence comparisona review. Bioinformatics,
Oxford University Press, v. 19, n. 4, p. 513–523, 2003. Citado 1 vez na página 19.
VIRTANEN, P.; GOMMERS, R.; OLIPHANT, T. E.; HABERLAND, M.; REDDY, T.;
COURNAPEAU, D.; BUROVSKI, E.; PETERSON, P.; WECKESSER, W.; BRIGHT, J.; VAN
DER WALT, S. J.; BRETT, M.; WILSON, J.; MILLMAN, K. J.; MAYOROV, N.;
NELSON, A. R. J.; JONES, E.; KERN, R.; LARSON, E.; CAREY, C. J.; POLAT, .; FENG, Y.;
MOORE, E. W.; VANDERPLAS, J.; LAXALDE, D.; PERKTOLD, J.; CIMRMAN, R.;
HENRIKSEN, I.; QUINTERO, E. A.; HARRIS, C. R.; ARCHIBALD, A. M.; RIBEIRO, A. H.;
PEDREGOSA, F.; VAN MULBREGT, P.; SCIPY 1.0 CONTRIBUTORS. SciPy 1.0:
Fundamental Algorithms for Scientific Computing in Python. Nature Methods, v. 17,
p. 261–272, 2020. DOI: 10.1038/s41592-019-0686-2. Citado 3 vezes nas páginas 48, 50.
XIA, X. Distance-based phylogenetic methods. In: BIOINFORMATICS and the Cell. [S.l.]:
Springer, 2018. P. 343–379. Citado 1 vez na página 21.
YANG, Z.; RANNALA, B. Molecular phylogenetics: principles and practice. Nature reviews
genetics, Nature Publishing Group, v. 13, n. 5, p. 303–314, 2012. Citado 1 vez na página 21.
ZIELEZINSKI, A.; GIRGIS, H. Z.; BERNARD, G.; LEIMEISTER, C.-A.; TANG, K.;
DENCKER, T.; LAU, A. K.; RÖHLING, S.; CHOI, J. J.; WATERMAN, M. S. et al.
https://doi.org/10.1038/s41592-019-0686-2
85
Benchmarking of alignment-free sequence comparison methods. Genome biology, BioMed
Central, v. 20, n. 1, p. 1–18, 2019. Citado 2 vezes nas páginas 24, 25.
ZUO, G.; XU, Z.; YU, H.; HAO, B. Jackknife and bootstrap tests of the composition vector trees.
Genomics, proteomics & bioinformatics, Elsevier, v. 8, n. 4, p. 262–267, 2010. Citado 1 vez
na página 24.
86
APÊNDICE 1 - SCRIPTS PARA O DESENVOLVIMENTO DO EXPERIMENTO
1.1 OBTENÇÃO DOS DADOS DE REFERÊNCIA - ÁRVORES, SEQUÊNCIAS E ALINHA-
MENTOS
Os códigos 1.1 e 1.2 são arquivos de configuração do INDELible. Aslinhas 13 e 16
contém as letras i, j e k, que são as variáveis de quantidade sequências, taxa de mutação e tamanho
da sequências, respectivamente. Para a edição dessas variáveis o código 1.3 em bash é executado
para se calcular automaticamente todas combinações para as diferentes variáveis. Além disso,
um script 1.4 em Python, chamando pelo código 1.3, serve para alterar as variáveis i,j e k dos
arquivos de controle (Control.txt).
Listing 1.1 – Arquivo Control.txt de entrada do INDELible para geração dados de nucleotídeos
1 [TYPE] NUCLEOTIDE 1
2
3 [SETTINGS]
4 [output] FASTA
5
6 [MODEL] modelname
7 [submodel] F84 1.5
8 [indelmodel] LAV 1.7 541
9 [indelrate] 0.002
10 [statefreq] 0.25 0.25 0.25 0.25
11
12 [TREE] treename
13 [unrooted] i 2.4 1.1 0.2566 j
14
15 [PARTITIONS] partitionname
16 [treename modelname k]
17
18 [EVOLVE] partitionname 1 outputnameRandomTree
Listing 1.2 – Arquivo Control.txt de entrada do INDELible para geração dados de aminoácidos
1 [TYPE] AMINOACID 1
2
3 [SETTINGS]
4 [output] FASTA
5
6 [MODEL] modelname
7 [submodel] Dayhoff
8 [indelmodel] LAV 1.7 541
9 [indelrate] 0.002
10
11
87
12 [TREE] treename
13 [unrooted] i 2.4 1.1 0.2566 j
14
15 [PARTITIONS] partitionname
16 [treename modelname k]
17
18 [EVOLVE] partitionname 1 outputnameRandomTree
Listing 1.3 – Arquivo bash para alteração automática dos valores de i j e k
1 pathProj=’/pasta_output/indelibleFiles/aa’
2
3 pathIndelible=’/pasta_programa_indelible/INDELibleV1.03/src’
4
5 for i in ‘seq 10 10 110‘; do # QUANTIDADE DE SEQUÊNCIA
6 for j in "0.01" "0.1" "0.5" "1.0"; do # TAXAS DE MUTAÇÃO
7 # Chamada do script python para alteração dos valores
8 # de quantidade de sequências e taxa de mutação
9 python3 alterSeqSizeIndelible.py "[unrooted] $i 2.4 1.1 0.2566 $j"
10 for k in ‘seq 50 25 1450‘; do # TAMANHO DAS SEQUÊNCIAS
11 # Chamada so script python para alteração dos valores
12 # de tamanho das sequências
13 python3 alterSeqSizeIndelible.py "[treename modelname $k]"
14
15 # Execução do programa INDELible
16 ./pathIndelible/indelible
17
18 # Move os arquivos gerados para as pastas de destino - árvores,
19 # sequências e alinhamentos
20 mv trees.txt ${pathProj}/trees/${i}_${j}_${k}_tree_aa.txt
21 mv outputnameRandomTree.fas ${pathProj}/seqs/${i}_${j}_${k}_aa.fas
22 mv outputnameRandomTree_TRUE.fas ...
23 ... ${pathProj}/aligns/${i}_${j}_${k}_TRUE_aa.fas
24 done
25 done
26 done
Listing 1.4 – Arquivo python para alteração do arquivo de controle
1 import sys
2 import re
3
4 pathProj=’/pasta_programa_indelible/INDELibleV1.03/src’
5
6 if "[unrooted" in sys.argv[1]:
7 print(sys.argv[1])
8 # Altera quantidade de sequências e Taxa de mutação
9 with open(pathProj+’control.txt’, ’r’) as f:
88
10 new = re.sub("(\[unrooted.*)", sys.argv[1], f.read())
11 with open(pathProj+’control.txt’, ’w’) as f:
12 if new:
13 f.write(new)
14 f.close()
15 elif "[treename modelname" in sys.argv[1]:
16 # Altera tamanho das sequências
17 with open(pathProj+’control.txt’, ’r’) as f:
18 new = re.sub("(\[treename modelname.*)", sys.argv[1], f.read())
19 with open(pathProj+’control.txt’, ’w’) as f:
20 if new:
21 f.write(new)
22 f.close()
23
24 else:
25 print(’Argumento inválido!’)
1.2 SCRIPTS PARA CÁLCULO DAS MATRIZES DE DISTÂNCIA POR MÉTODO DE-
PENDENTES DE ALINHAMENTO (AB)
Nesta etapa calcula-se as matrizes de distâncias com o programa EMBOSS através do
script em bash 1.5 para sequências nucleotídicas e 1.6 para sequências de aminoácidos.
Listing 1.5 – Arquivo bash para cálculo da matriz de distância de todos os alinhamentos gerados com
sequências de nucleotídeo
1 pathIn=’/pasta_input_alinhamentos/indelibleFiles/nt/aligns/’
2 pathOut=’/pasta_ouput_matrizes/indelibleFiles/nt/matrix/’
3
4 arr=(${pathIn}*.fas)
5 for filename in ${arr[@]##*/}; do
6 fdnadist -sequence ${pathIn}${filename} -method f -outfile
7 ${pathOut}${filename}.fdnadist
8 done
Listing 1.6 – Arquivo bash para cálculo da matriz de distância de todos os alinhamentos gerados com
sequências de aminoácidos
1 pathIn=’/pasta_input_alinhamentos/indelibleFiles/aa/aligns/’
2 pathOut=’/pasta_ouput_matrizes/indelibleFiles/aa/matrix/’
3
4 arr=(${pathIn}*.fas)
5 for filename in ${arr[@]##*/}; do
6 fprotdist -sequence ${pathIn}${filename} -method f -outfile
7 ${pathOut}${filename}.fprotdist
8 done
89
1.3 SCRIPTS PARA CÁLCULO DAS MATRIZES DE DISTÂNCIA POR MÉTODO LIVRE
DE ALINHAMENTO (AF)
Listing 1.7 – Arquivo para geração de vetor de dissimilaridade entre as sequências de nucleotídeo com o
SWeeP
1 setGlobalDev(0);
2 global DEV_MODE
3
4 fastasList = dir(’/pasta_sequencias/nt/output/seqs/*fas’);
5 path = ’/pasta_sequencias/nt/output/seqs/’;
6
7 for f = 1:size(fastasList,1)
8 disp(fastasList(f).name)
9 sweep(strcat(path,fastasList(f).name), ’SeqType’,’NT’)
10 end
Listing 1.8 – Arquivo para geração de vetor de dissimilaridade entre as sequências de aminoácidos com o
SWeeP
1 setGlobalDev(0);
2 global DEV_MODE
3
4 fastasList = dir(’/pasta_sequencias/aa/output/seqs/*fas’);
5 path = ’/pasta_sequencias/aa/output/seqs/’;
6
7 for f = 1:size(fastasList,1)
8 disp(fastasList(f).name)
9 sweep(strcat(path,fastasList(f).name))
10 end
1.4 SCRIPTS PARA CÁLCULO DAS ÁRVORES A PARTIR DAS MATRIZES DE DISTÂN-
CIA E CÁLCULO DAS DISTÂNCIAS ENTRE AS ÁRVORES
Listing 1.9 – Classes criadas para cálculo de árvores e distâncias entre árvores para métodos AB
1 from math import sqrt
2 from re import search
3
4 from os import listdir
5 from os.path import isfile, join
6
7 from pickle import dump
8
9 import numpy as np
10
11 from dendropy import TreeList
12 from dendropy.calculate import treecompare
90
13
14 from ete3 import Tree
15
16 import scipy.cluster.hierarchy as hac
17 from scipy.spatial.distance import squareform
18
19 from skbio import DistanceMatrix
20 from skbio.tree import nj
21
22 import tree_distance
23
24 # Importa matriz de distância para gerar árvores métodos diferentes
25 class GenerateTrees():
26 def __init__(self, distFileName, refTreeFileName=’’,
27 refTreeFileType=’newick’):
28
29 # Arquivo de distância gerado pelo EMBOSS
30 self.distFileName = distFileName
31 self.refTreeFileName = refTreeFileName
32 self.refTreeFileType = refTreeFileType
33
34 self.trees = TreeList()
35
36 def getDistFile(self):
37 # Para a matriz gerada com fprotdist e fdnadist do EMBOSS,
38 # faz-se o seguinte para ler os dados do arquivo.
39 # Ao final a matriz deve ser transformada para forma condensada
40 mDist = []
41 ids = []
42
43 with open(self.distFileName) as f:
44 matrix = f.read().replace(’\n’,’ ’).split()
45 i = int(matrix[0])
46 matrix.pop(0)
47 a = 0
48 for j in range(len(matrix)):
49 if j == a:
50 ids.append(int(matrix[j]))
51 a += i+1
52 else:
53 mDist.append(float(matrix[j]))
54 f.close()
55
56 # Transforma a lista em matriz quadrada e depois a condensada
57 mDist = squareform(np.array(mDist).reshape(i, i)).tolist()
58
59 return mDist, ids
91
60
61 def getNewick(self, node, newick, parentdist, leaf_names):
62 # Função transforma objeto tree em sequência newick
63 if node.is_leaf():
64 return "%s:%.2f%s" % (leaf_names[node.id],
65 parentdist - node.dist, newick)
66 else:
67 if len(newick) > 0:
68 newick = "):%.2f%s" % (parentdist - node.dist, newick)
69 else:
70 newick = ");"
71 newick = self.getNewick(node.get_left(),
72 newick, node.dist, leaf_names)
73 newick = self.getNewick(node.get_right(),
74 ",%s" % (newick), node.dist, leaf_names)
75 newick = "(%s" % (newick)
76 return newick
77
78 def getRefTree(self):
79 ## Função importa árvore de referência
80 ## arqName éo nome do arquivo com o caminho
81 ## arqtype éo tipo do arquivo, newick, phylip
82
83 with open(self.refTreeFileName) as f:
84 return self.trees.get(data=(f.read().split()[-1]),
85 schema=self.refTreeFileType,
86 ).as_string(schema=self.refTreeFileType)
87
88 def generateCluster(self, metodo, metrica):
89 dist, ids = self.getDistFile()
90 if metodo== ’nj’:
91 dmNJ = DistanceMatrix(dist, ids)
92 # Transforma a árvore nj em ultramétrica
93 tEte3 = Tree( nj(dmNJ, result_constructor=str) )
94 tEte3.convert_to_ultrametric()
95 return tEte3.write(format=5), np.nan
96 else:
97 # A partir da matriz de distância, clusteriza-se e transforma
98 # o objeto dendrograma em newick
99 # Calcula o cluster por método e métrica específicos
100 # A função np.clip() limita os valores a no mínimo 0.
101 # A métrica cosine pode gerar valores negativos
102 cluster = np.clip(hac.linkage(dist, method=metodo),
103 a_min=0, a_max=None)
104
105 # Calcula coeficiente cofenético
106 cophCorr = hac.cophenet(cluster, dist)
92
107
108 # Convert a linkage matrix into an easy-to-use tree object.
109 treeZ = hac.to_tree(cluster, False)
110
111 # Ordena a ordem do indivíduos do alinhamento
112 # com a ordem da clusterização
113 IDS = np.array(ids)[np.array(treeZ.pre_order())]
114
115 # Transforma o objeto árvore no formato newick
116 return self.getNewick(treeZ, "", treeZ.dist, IDS), cophCorr[0]
117
118 def generateListTrees(self, metodos, metricas):
119 listNewicks = []
120 listMetodosCluster = []
121 listCophCorr = []
122
123 for metodo in metodos:
124 listNewicks.append(self.generateCluster(metodo, ’’))
125 listMetodosCluster.append((metodo, ’’))
126
127 # O retorno da função "generateCluster" éuma tupla,
128 # aqui separa-se a tupla, uma para newicks e
129 # outra para correlação cofenética
130 listNewicks, listCophCorr = list(zip(*listNewicks))
131 listNewicks = list(listNewicks)
132 listCophCorr = list(listCophCorr)
133 if self.refTreeFileName != ’’:
134 # Transforma a árvore referência em ultramétrica
135 tEte3 = Tree( self.getRefTree(), format=1 )
136 tEte3.convert_to_ultrametric()
137
138 listNewicks.insert(0, tEte3.write(format=5))
139 listMetodosCluster.insert(0, (’ref’,’’))#(metodo, metrica))
140 listCophCorr.insert(0, np.nan)
141
142 stringNewicks=’’.join(listNewicks)
143
144 return self.trees.get(data=stringNewicks, schema="newick"),
145 listMetodosCluster, listCophCorr
146
147 def createTreeFiles(self, metodos, metricas, path):
148 treesList, methsList, cophCorrList = self.generateListTrees(metodos,
149 metricas)
150
151 pickle_out = open(path+’ListaCophCorr.pickle’, ’wb’)
152 dump(list(zip(methsList,cophCorrList)), pickle_out)
153 pickle_out.close()
93
154
155 i = 0
156 for t,m in zip(treesList, methsList):
157 name = m[0] + ’_’ + m[1] + ’.nw’
158 t.write(path=path+name, schema=’newick’)
159 i+=1
160
161
162 # Importa todas as árvores para calcular distâncias entre elas
163 class CalcPlotDistTrees():
164 def __init__(self, pathArq, method, treeFileType, fileFilter):
165
166 self.method = method
167 self.treeFileType = treeFileType
168 self.trees = TreeList()
169 self.fileFilter = fileFilter
170
171 pathArq = pathArq[:pathArq.rfind(’/’)+1]
172
173 self.listaArqs = [f for f in listdir(pathArq) if (isfile(join(pathArq,
174 f)) and search(’^’+self.fileFilter, f) and (’.pickle’ not in f) ) ]
175
176 self.treeList = []
177 for file in self.listaArqs:
178 with open(pathArq+file, ’r’) as f:
179 s = f.read()
180 self.treeList.append(s)
181
182 stringNewicks=’’.join(self.treeList).replace(’\n’,’’)
183 print(stringNewicks)
184 # Deve ser UNROOTED de acordo com p. 529 Felsentein 2004
185 self.matrixTrees = self.trees.get(data=stringNewicks,
186 schema="newick",
187 rooting=’force-unrooted’)
188
189 def distPairwiseTrees(self):
190 # Retorna a diferença par a par entre todas as árvores
191 distsTree = []
192 teste = []
193 for tree1 in self.matrixTrees:
194 # Preapara para tree_distance.getEuclideanDistance
195 # precisa ser PhyloTree
196 tree1Phylo = tree_distance.PhyloTree(tree1.encode(), False)
197 for tree2 in self.matrixTrees:
198 if self.method == ’E’:
199 distsTree.append(treecompare.euclidean_distance(tree1, tree2))
200 elif self.method == ’W’:
94
201 distsTree.append(treecompare.
202 weighted_robinson_foulds_distance(tree1, tree2))
203 elif self.method == ’S’:
204 distsTree.append(treecompare.
205 symmetric_difference(tree1, tree2))
206 elif self.method == ’G’:
207 tree2Phylo = tree_distance.PhyloTree(tree2.encode(), False)
208 distsTree.append(tree_distance.
209 getEuclideanDistance(tree1Phylo, tree2Phylo))
210
211 # Normalização dos dados
212 distsTree = np.array(distsTree)
213
214 maxV = max(distsTree)
215 minV = min(distsTree)
216
217 distsTree = distsTree - minV
218 distsTree = distsTree/(maxV - minV)
219
220 i = 1
221 dist = []
222 aux = []
223 for tree in distsTree:
224 if i == sqrt(len(distsTree)):
225 aux.append(tree)
226 dist.append(aux)
227 i=0
228 aux=[]
229 else:
230 aux.append(tree)
231 i+=1
232
233 return dist
234
235 def distTreesAndRef(self):
236 distsTree = []
237 indexRef = self.listaArqs.index(self.fileFilter+’ref_.nw’)
238 ref = self.matrixTrees[indexRef]
239 # Preapara para tree_distance.getEuclideanDistance
240 # precisa ser PhyloTree
241 tree1Phylo = tree_distance.PhyloTree(ref.as_string(
242 ’newick’).encode(), False)
243 for tree in self.matrixTrees:
244 if self.method == ’E’:
245 distsTree.append(treecompare.euclidean_distance(tree, ref))
246 elif self.method == ’W’:
247 distsTree.append(treecompare.
95
248 weighted_robinson_foulds_distance(tree, ref))
249 elif self.method == ’S’:
250 distsTree.append(treecompare.
251 symmetric_difference(tree, ref))
252 elif self.method == ’G’:
253 tree2Phylo = tree_distance.PhyloTree(tree.
254 as_string(’newick’).encode(), False)
255 distsTree.append(tree_distance.getGeodesicDistance(tree1Phylo,
256 tree2Phylo))
257
258 # Normalização dos dados
259 distsTree = np.array(distsTree)
260 maxV = np.max(distsTree)#max(distsTree)
261 minV = np.min(distsTree)#min(distsTree)
262
263 distsTree = distsTree - minV
264 distsTree = distsTree/(maxV - minV)
265
266
267 return distsTree
Listing 1.10 – Arquivo python para criação das árvores a partir do código 1.9
1 from os import listdir
2 from os.path import isfile, join
3
4 import pickle
5
6 import pandas as pd
7
8 from funcoesCalculaDist import CalcPlotDistTrees, GenerateTrees
9
10 ## métricas de clusterização
11 metricas=[’euclidean’, ’cityblock’, ’sqeuclidean’, ’cosine’,
12 ’correlation’, ’hamming’, ’jaccard’, ’chebyshev’,
13 ’braycurtis’, ’yule’, ’dice’,’kulsinski’, ’canberra’,
14 ’rogerstanimoto’, ’russellrao’,’sokalmichener’, ’sokalsneath’]
15
16 ## métodos de clusterização
17 metodos=[’single’, ’complete’, ’average’, ’weighted’,
18 ’centroid’, ’median’, ’ward’ , ’nj’]
19
20 pathProj=’/pasta_matrizes’
21
22 pathINmat = pathProj+’/output/matrices/’
23 pathINrefTree = pathProj+’/output/treesRef/’
24 pathOUT = pathProj+’/output/treesCalc/’
25
96
26 arqsMatrizes = [f for f in listdir(pathINmat) if (isfile(join(pathINmat,
27 f)) and (’.pickle’ not in f) ) ]
28
29 arqsMatrizesOK = []
30 arqsMatrizesNOK = []
31 for arq in arqsMatrizes:
32 with open(pathINmat+arq) as fTemp:
33 fRead = fTemp.read()
34 if (’nan’ in fRead) or (’inf’ in fRead):
35 arqsMatrizesNOK.append(arq)
36 else:
37 arqsMatrizesOK.append(arq.split(’_’)[:-1])
38 fTemp.close()
39
40 del fRead
41
42 pickle.dump( arqsMatrizesOK, open(
43 pathProj+"/output/arqsMatrizesOK.pickle", "wb" ) )
44
45
46 distRef = []
47 listaArqs = []
48 metDist = []
49 print(’Gerando Árvores!!!’)
50 for i,j,k,m in arqsMatrizesOK:
51 GenerateTrees(pathINmat+i+’_’+j+’_’+k+’_TRUE_aa.fas.fprotdist’,
52 pathINrefTree+i+’_’+j+’_’+k+’_tree_aa.txt’,’newick’
53 ).createTreeFiles(metodos, metricas, pathOUT+i+’_’+j+’_’+k+’_’)
Listing 1.11 – Arquivo python para cálculo das distâncias entre das árvores a partir do código 1.9
1 from os import listdir
2 from os.path import isfile, join
3
4 import pickle
5
6 import pandas as pd
7
8 from funcoesCalculaDist import CalcPlotDistTrees, GenerateTrees
9
10 pathProj=’/pasta_matrizes’
11
12 pathINmat = pathProj+’/output/matrices/’
13 pathINrefTree =pathProj+’/output/treesRef/’
14 pathOUT = pathProj+’/output/treesCalc/’
15
16 arqsMatrizesOK = pickle.load(open(
17 pathProj+"/output/arqsMatrizesOK.pickle", "rb" ) )
97
18
19 methodList = [’E’,’W’,’S’,’G’]
20
21 distRef = []
22 listaArqs = []
23 metDist = []
24
25 for i,j,k,m in arqsMatrizesOK:
26
27 for method in methodList:
28 pathArq = pathOUT+i+’_’+j+’_’+k+’_ref_.nw’
29
30 a = CalcPlotDistTrees(pathArq, method, ’newick’, i+’_’+j+’_’+k+’_’)
31 distRef.extend(a.distTreesAndRef())
32 listaArqs.extend(a.listaArqs)
33 metDist.extend([method for i in range(len(a.distTreesAndRef())) ])
34
35 pickle.dump( distRef, open( pathProj+"/output/distRef.pickle", "wb" ) )
36 pickle.dump( listaArqs, open( pathProj+"/output/listaArqs.pickle", "wb" ) )
37 pickle.dump( metDist, open( pathProj+"/output/metDist.pickle", "wb" ) )
38
39 df = pd.DataFrame({’distanciaRef’:distRef,
40 ’listaArqs’:listaArqs,
41 ’metDist’:metDist})
42
43 df.to_csv(pathProj+’/output/dfTrees.csv’, index=False)
	Folha de rosto
	Dedicatória
	Agradecimentos
	Resumo
	ABSTRACT
	Introdução
	Justificativas
	Objetivos Gerais
	Objetivos Específicos
	Fundamentação Teórica
	Árvores Filogenéticas
	Métodos Baseados em Distância
	Métodos Baseados em Caracteres
	Estimativa e teste de hipóteses em filogenia
	Jackknife
	Bootstrapping
	Estimativa e teste de hipótese para método livre de alinhamento
	Processos independentes de alinhamento
	Clusterização
	Medidas de proximidade entre indivíduos
	Correção Modelo Evolutivo
	Tipos de Clusterização
	Métodos aglomerativos: bottom-up
	Métodos divisivos: top-down
	Distância entre árvores
	Processos evolutivos simulados
	Aprendizado de máquina (Machine learning)
	Materiais e Métodos
	ETAPA 1: Simulação de árvores, sequências e alinhamentos
	ETAPA 2: Cálculo das matrizes de dissimilaridade
	Cálculo de matrizes dependentes de alinhamentos - EMBOSS
	Cálculo de matrizes independentes de alinhamentos - SWeeP
	ETAPA 3: Clusterização das matrizes de dissimilaridade
	ETAPA 4: Cálculo de distância entre as árvores
	ETAPAS 5,6 e 7: Construção do modelo de classificação de árvores filogenéticas
	Definição das variáveis de entrada (features)
	Definição do modelo de aprendizado de máquina
	Delimitação do experimento
	Limitações do experimento
	Lista de pacotes e programas utilizados
	Resultados e Discussão
	Resultados dependentes de alinhamento
	Sequências de nucleotídeos
	Sequências de aminoácidos
	Resultados independentes de alinhamento
	Sequências de nucleotídeos
	Sequências de aminoácidos
	Treino e validação do modelo classificador de árvores filogenéticas
	TACos: Pacote python e aplicação web
	Conclusão
	REFERÊNCIAS
	Scripts para o desenvolvimento do experimento
	 APÊNDICE 1 - Scripts para o desenvolvimento do experimento
	Obtenção dos dados de referência - árvores, sequências e alinhamentos
	Scripts para cálculo das matrizes de distância por método dependentes de alinhamento (AB)
	Scripts para cálculo das matrizes de distância por método livre de alinhamento (AF)
	Scripts para cálculo das árvores a partir das matrizes de distância e cálculo das distâncias entre as árvores