Sobre a Mediana Relativa à Distância de Posto de 3 Permutações

• Processo: 18/05254-4
• Modalidade de apoio: Auxílio à Pesquisa - Publicações científicas - Artigo
• Data de Início da vigência: 01 de maio de 2018
• Data de Término da vigência: 31 de outubro de 2018
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: João Meidanis
• Beneficiário: João Meidanis
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Biologia computacional
• Palavra(s)-Chave do Pesquisador: Algoritmos polinomiais | Distância genômica | Rearranjos de Genomas | Biologia Computacional

Resumo

Recentemente, Pereira Zanetti, Biller e Meidanis propuseram uma nova definição de distância de rearranjo entre genomas. Nesta formulação, cada genoma é representado como uma matriz, e a distância d é a distância de posto entre estas matrizes. Embora definida através de matrizes, a distância de posto é igual ao peso total mínimo de uma série ponderada de operações que leva de um genoma ao outro, incluindo inversões, translocações, transposições e outras. A complexidade computacional do problema da mediana-de-três com respeito a esta distância é no momento desconhecida. As matrizes de genomas são um caso especial de matrizes de permutações, que estudamos neste artigo. Em seu artigo, os autores fornecem um algoritmo O(n^3) para determinar três candidatas a medianas, provam a razão de aproximação justa 4/3 e fornecem uma condição suficiente para as suas candidatas serem medianas. Também conduzem alguns experimentos que sugerem que seu método é acurado em dados simulados e reais.Resultados: Neste artigo, estendemos os resultados de Pereira Zanetti e colegas e fornecemos:- 3 invariantes caracterizando o problema de achar a mediana de 3 matrizes- uma condição suficiente para unicidade de medianas que pode ser verificada em tempo O(n)- um algoritmo mais rápido, O(n^2), para determinar a mediana sob esta condição- um novo algoritmo heurístico para este problema baseado em `compressed sensing'- um algoritmo O(n^4) que resolve o problems de forma exata quando as entradas são matrizes ortogonais, uma classe que inclui tanto permutações como genomas.Conclusões: Nosso trabalho fornece a primeira prova de que, com respeito à distância de posto, o problema de achar medianas de 3 genomas, bem como a mediana de 3 permutações, têm solução exata em tempo polinomial, um resultado que deve ser contrastado com a NP-dificuldade para a distância DCJ (double cut-and-join) e a maior parte das outras famílias de operações de rearranjo de genomas. Este resultado, amparado pelos nossos testes experimentais, indica que a distância de posto é uma alternativa viável à distância DCJ, amplamente utilizada em comparações de genomas. (AU)