Abstract
Comparing genomes of different species is a crucial problem in comparative genomics. Different measures have been proposed to compare two genomes: number of common intervals, number of adjacencies, number of reversals, etc. These measures are classically used between two totally ordered genomes. However, genetic mapping techniques often give rise to different maps with some unordered genes. Starting from a partial order between genes of a genome, one method to find a total order consists in optimizing a given measure between a linear extension of this partial order and a given total order of a close and well-known genome. However, for most common measures, the problem turns out to be NP-hard. In this paper, we propose a (0,1)-linear programming approach to compute a linear extension of one genome that maximizes the number of common intervals (resp. the number of adjacencies) between this linear extension and a given total order. Next, we propose an algorithm to find linear extensions of two partial orders that maximize the number of adjacencies.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angibaud, S., Fertin, G., Rusu, I., Thévenin, A., Vialette, S.: Efficient tools for computing the number of breakpoints and the number of adjacencies between two genomes with duplicate genes. J. Computational Biology 15(8), 1093–1115 (2008)
Angibaud, S., Fertin, G., Rusu, I., Vialette, S.: A pseudo-boolean general framework for computing rearrangement distances between genomes with duplicates. J. Computational Biology 14(4), 379–393 (2007)
Bergeron, A., Stoye, J.: On the similarity of sets of permutations and its applications to genome comparison. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 68–79. Springer, Heidelberg (2003)
Blin, G., Blais, E., Hermelin, D., Guillon, P., Blanchette, M., El-Mabrouk, N.: Gene maps linearization using genomic rearrangement distances. J. Computational Biology 14(4), 394–407 (2007)
Eén, N., Sörensson, N.: Translating pseudo-boolean constraints into SAT. Journal on Satisfiability, Boolean Modeling and Computation 2, 1–26 (2006)
Fu, Z., Jiang, T.: Computing the breakpoint distance between partially ordered genomes. J. Bioinformatics and Computational Biology 5(5), 1087–1101 (2007)
Schrijver, A.: Theory of Linear and Integer Programming. J. Wiley & Sons, Chichester (1998)
Uno, T., Yagiura, M.: Fast algorithms to enumerate all common intervals of two permutations. Algorithmica 26(2), 290–309 (2000)
Watterson, G.A., Ewens, W.J., Hall, T.E., Morgan, A.: The chromosome inversion problem. Journal of Theoretical Biology 99(1), 1–7 (1982)
Zheng, C., Lenert, A., Sankoff, D.: Reversal distance for partially ordered genomes. Bioinformatics 21(1), 502–508 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Angibaud, S., Fertin, G., Thévenin, A., Vialette, S. (2009). Pseudo Boolean Programming for Partially Ordered Genomes. In: Ciccarelli, F.D., Miklós, I. (eds) Comparative Genomics. RECOMB-CG 2009. Lecture Notes in Computer Science(), vol 5817. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04744-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-04744-2_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04743-5
Online ISBN: 978-3-642-04744-2
eBook Packages: Computer ScienceComputer Science (R0)