«« Voltar
Filogenia viva baseada em distância: caracterização do problema e algoritmos.
Protocolo do SIGProj:   285499.1430.85659.31102017
De:01/12/2017  à  30/06/2019
 
Coordenador-Extensionista
  Graziela Santos de Araújo
Instituição
  UFMS - Universidade Federal de Mato Grosso do Sul
Unidade Geral
  FACOM - Faculdade de Computação
Unidade de Origem
  CPQ - Comissão Setorial de Pesquisa
Resumo da Ação de Extensão
  O Problema da Filogenia Viva baseado em distâncias generaliza o conhecido Problema da Filogenia baseado em Distâncias por admitir ancestrais vivos entre os objetos taxonômicos. Este problema é adequado para casos de espécies de evolução rápida que coexistem e são ancestrais/descendentes ao mesmo tempo, como vírus, filogenias de objetos não biológicos como documentos e registros de banco de dados. Para n objetos, a entrada é uma matriz de ordem n, onde a posição i e j representa a distância evolutiva entre os objetos i e j. A saída é uma árvore sem raiz, com peso nas arestas, onde os objetos podem ser representados como folhas ou nós internos, e a distância entre pares de objetos na árvore é igual às distâncias nas posições correspondentes na matriz. Quando a matriz é aditiva, é fácil encontrar tal árvore. No contrário, o problema é computacionalmente difícil. Neste trabalho vamos explorar o caso em que dada uma topologia de árvore e uma matriz de distâncias não aditiva, queremos atribuir pesos às arestas de forma que as distâncias entre os objetos na árvore sejam o mais próximas possível das distâncias dos objetos na matriz. Nossa proposta é caracterizar melhor o problema da filogenia viva baseada em distâncias, estudar soluções existentes para o problema tradicional e aplicá-los à filogenia viva; além de descrever novas abordagens e heurísticas para solucionar o problema da filogenia viva.
Palavras-chave
   evolução, filogenia, filogenia viva, neighbor-joining
Público-Alvo
  
Situação
  Atividade EM ANDAMENTO
Contato
  
«« Voltar