Repository: Freie Universität Berlin, Math Department

Hidden Breakpoints in Genome Alignments

Kehr, B. and Reinert, K. and Darling, A. E. (2012) Hidden Breakpoints in Genome Alignments. In: Lecture Notes in Computer Science: Algorithms in Bioinformatics. Springer-Verlag, Berlin, pp. 391-403. ISBN 978-3-642-33121-3

Full text not available from this repository.

Official URL:


During the course of evolution, an organism’s genome can undergo changes that affect the large-scale structure of the genome. These changes include gene gain, loss, duplication, chromosome fusion, fission, and rearrangement. When gene gain and loss occurs in addition to other types of rearrangement, breakpoints of rearrangement can exist that are only detectable by comparison of three or more genomes. An arbitrarily large number of these “hidden” breakpoints can exist among genomes that exhibit no rearrangements in pairwise comparisons. We present an extension of the multichromosomal breakpoint median problem to genomes that have undergone gene gain and loss. We then demonstrate that the median distance among three genomes can be used to calculate a lower bound on the number of hidden breakpoints present. We provide an implementation of this calculation including the median distance, along with some practical improvements on the time complexity of the underlying algorithm. We apply our approach to measure the abundance of hidden breakpoints in simulated data sets under a wide range of evolutionary scenarios. We demonstrate that in simulations the hidden breakpoint counts depend strongly on relative rates of inversion and gene gain/loss. Finally we apply current multiple genome aligners to the simulated genomes, and show that all aligners introduce a high degree of error in hidden breakpoint counts, and that this error grows with evolutionary distance in the simulation. Our results suggest that hidden breakpoint error may be pervasive in genome alignments.

Item Type:Book Section
Subjects:Mathematical and Computer Sciences > Computer Science
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:1168
Deposited By: Anja Kasseckert
Deposited On:16 Oct 2012 11:59
Last Modified:16 Oct 2012 12:04

Repository Staff Only: item control page