A Cubic Algorithm for the Generalized Rank Median of Three Genomes

Resource type
Date created
2018-09-08
Authors/Contributors
Abstract
The 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ω) , where ω≤3 , with respect to this distance, when the median is allowed to be an arbitrary orthogonal matrix.We 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.We 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.
Document
Published as
Chindelevitch L., Meidanis J. (2018) A Cubic Algorithm for the Generalized Rank Median of Three Genomes. In: Blanchette M., Ouangraoua A. (eds) Comparative Genomics. RECOMB-CG 2018. Lecture Notes in Computer Science, vol 11183. Springer, Cham
Publication title
Comparative Genomics
Document title
A Cubic Algorithm for the Generalized Rank Median of Three Genomes
Editor
Blanchette M., Ouangraoua A
Publisher
Springer
Date
2018
Copyright statement
Copyright is held by the author(s).
Scholarly level
Peer reviewed?
Yes
Language
Member of collection