A cubic algorithm for the generalized rank median of three genomes

Autor(es)

Chindelevitch, Leonid ^[1] ; La, Sean ^[1] ; Meidanis, Joao ^[2]

Afiliação do(s) autor(es)

^[1] Simon Fraser Univ, Sch Comp Sci, Burnaby, BC - Canada

^[2] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Algorithms for Molecular Biology; v. 14, JUL 26 2019.
• Citações Web of Science: 0

Resumo

BackgroundThe area of genome rearrangements has given rise to a number of interesting biological, mathematical and algorithmic problems. Among these, one of the most intractable ones has been that of finding the median of three genomes, a special case of the ancestral reconstruction problem. In this work we re-examine our recently proposed way of measuring genome rearrangement distance, namely, the rank distance between the matrix representations of the corresponding genomes, and show that the median of three genomes can be computed exactly in polynomial time O(n omega), where omega <= 3, with respect to this distance, when the median is allowed to be an arbitrary orthogonal matrix.ResultsWe define the five fundamental subspaces depending on three input genomes, and use their properties to show that a particular action on each of these subspaces produces a median. In the process we introduce the notion of M-stable subspaces. We also show that the median found by our algorithm is always orthogonal, symmetric, and conserves any adjacencies or telomeres present in at least 2 out of 3 input genomes.ConclusionsWe test our method on both simulated and real data. We find that the majority of the realistic inputs result in genomic outputs, and for those that do not, our two heuristics perform well in terms of reconstructing a genomic matrix attaining a score close to the lower bound, while running in a reasonable amount of time. We conclude that the rank distance is not only theoretically intriguing, but also practically useful for median-finding, and potentially ancestral genome reconstruction. (AU)

• Processo FAPESP: 16/01511-7 - Algoritmos para genômica comparativa de culturas e outras plantas com flores
• Beneficiário: João Meidanis
• Modalidade de apoio: Bolsas no Exterior - Pesquisa