{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:03Z","timestamp":1759637943054},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"S19","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Recovering the structure of ancestral genomes can be formalized in terms of properties of binary matrices such as the Consecutive-Ones Property (C1P). The <jats:italic>Linearization Problem<\/jats:italic> asks to extract, from a given binary matrix, a maximum weight subset of rows that satisfies such a property. This problem is in general intractable, and in particular if the ancestral genome is expected to contain only linear chromosomes or a unique circular chromosome. In the present work, we consider a relaxation of this problem, which allows ancestral genomes that can contain several chromosomes, each either linear or circular.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Result<\/jats:title>\n            <jats:p>We show that, when restricted to binary matrices of degree two, which correspond to adjacencies, the genomic characters used in most ancestral genome reconstruction methods, this relaxed version of the Linearization Problem is polynomially solvable using a reduction to a matching problem. This result holds in the more general case where columns have bounded multiplicity, which models possibly duplicated ancestral genes. We also prove that for matrices with rows of degrees 2 and 3, without multiplicity and without weights on the rows, the problem is NP-complete, thus tracing sharp tractability boundaries.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>As it happened for the breakpoint median problem, also used in ancestral genome reconstruction, relaxing the definition of a genome turns an intractable problem into a tractable one. The relaxation is adapted to some biological contexts, such as bacterial genomes with several replicons, possibly partially assembled. Algorithms can also be used as heuristics for hard variants. More generally, this work opens a way to better understand linearization results for ancestral genome structure inference.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-13-s19-s11","type":"journal-article","created":{"date-parts":[[2019,12,11]],"date-time":"2019-12-11T01:59:39Z","timestamp":1576029579000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Linearization of ancestral multichromosomal genomes"],"prefix":"10.1186","volume":"13","author":[{"given":"J\u00e1n","family":"Ma\u0148uch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Murray","family":"Patterson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roland","family":"Wittler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cedric","family":"Chauve","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Tannier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,12,19]]},"reference":[{"key":"5520_CR1","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/BF02982303","volume":"34","author":"A Sturtevant","year":"1937","unstructured":"Sturtevant A, Tan C: The comparative genetics of Drosophila Pseudoobscura and Drosophila Melanogaster. Journal of Genetics. 1937, 34: 415-432. 10.1007\/BF02982303.","journal-title":"Journal of Genetics"},{"key":"5520_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-5193(82)90384-8","volume":"99","author":"GA Watterson","year":"1982","unstructured":"Watterson GA, Ewens WJ, Hall TE, Morgan A: The chromosome inversion problem. Journal of Theoretical Biology. 1982, 99: 1-7. 10.1016\/0022-5193(82)90384-8.","journal-title":"Journal of Theoretical Biology"},{"key":"5520_CR3","volume-title":"MIT press","author":"G Fertin","year":"2009","unstructured":"Fertin G, Labarre A, Rusu I, Tannier E, Vialette S: Combinatorics of genome rearrangements. MIT press. 2009"},{"key":"5520_CR4","first-page":"581","volume-title":"36th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA","author":"S Hannenhalli","year":"1995","unstructured":"Hannenhalli S, Pevzner P: Transforming men into mice (polynomial algorithm for genomic distance problem). 36th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA. 1995, 581-592."},{"key":"5520_CR5","volume-title":"Tech Rep CRM-2579","author":"D Bryant","year":"1998","unstructured":"Bryant D: The complexity of the breakpoint median problem. Tech Rep CRM-2579. 1998, Centre de Recherches Math\u00e9matiques, Universit\u00e9 de Montr\u00e9al"},{"key":"5520_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1287\/ijoc.15.1.93.15155","volume":"15","author":"A Caprara","year":"2003","unstructured":"Caprara A: The reversal median problem. INFORMS Journal on Computing. 2003, 15: 93-113. 10.1287\/ijoc.15.1.93.15155.","journal-title":"INFORMS Journal on Computing"},{"key":"5520_CR7","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1109\/TCBB.2007.1069","volume":"4","author":"G Blin","year":"2007","unstructured":"Blin G, Chauve C, Fertin G, Rizzi R, Vialette S: Comparing Genomes with Duplications: a Computational Complexity Point of View. ACM\/IEEE Transactions on Computational Biology and Bioinformatics. 2007, 4: 523-534.","journal-title":"ACM\/IEEE Transactions on Computational Biology and Bioinformatics"},{"key":"5520_CR8","first-page":"163","volume-title":"Algorithms in Bioinformatics, Proceedings of WABI'06, Volume 4175 of Lecture Notes in Computer Science","author":"A Bergeron","year":"2006","unstructured":"Bergeron A, Mixtacki J, Stoye J: A Unifying View of Genome Rearrangements. Algorithms in Bioinformatics, Proceedings of WABI'06, Volume 4175 of Lecture Notes in Computer Science. 2006, 163-173."},{"key":"5520_CR9","doi-asserted-by":"publisher","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","volume":"21","author":"S Yancopoulos","year":"2005","unstructured":"Yancopoulos S, Attie O, Friedberg R: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics. 2005, 21: 3340-3346. 10.1093\/bioinformatics\/bti535.","journal-title":"Bioinformatics"},{"key":"5520_CR10","first-page":"1","volume-title":"Comparative Genomics, Proceedings of RECOMB-CG'09, Volume 5817 of Lecture Notes in Computer Science","author":"E Tannier","year":"2009","unstructured":"Tannier E: Yeast Ancestral Genome reconstruction: the possibilities of computational methods. Comparative Genomics, Proceedings of RECOMB-CG'09, Volume 5817 of Lecture Notes in Computer Science. 2009, 1-12."},{"key":"5520_CR11","doi-asserted-by":"publisher","first-page":"1318","DOI":"10.1109\/TCBB.2011.34","volume":"8","author":"P Feijao","year":"2011","unstructured":"Feijao P, Meidanis J: SCJ: a breakpoint-like distance that simplifies several rearrangement problems. IEEE\/ACM Transactions on Computational Biology and Bioinformatics. 2011, 8: 1318-1329.","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"5520_CR12","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1101\/gr.5383506","volume":"16","author":"J Ma","year":"2006","unstructured":"Ma J, Zhang L, Suh B, Raney B, Burhans R, Kent W, Blanchette M, Haussler D, Miller W: Reconstructing contiguous regions of an ancestral genome. Genome Research. 2006, 16: 1557-1565. 10.1101\/gr.5383506.","journal-title":"Genome Research"},{"key":"5520_CR13","first-page":"78","volume-title":"Algorithms in Bioinformatics, Proceedings of WABI'10, Volume 6293 of Lecture Notes in Bioinformatics","author":"D Bertrand","year":"2010","unstructured":"Bertrand D, Gagnon Y, Blanchette M, El-Mabrouk N: Reconstruction of Ancestral Genome subject to Whole Genome Duplication, Speciation, Rearrangement and Loss. Algorithms in Bioinformatics, Proceedings of WABI'10, Volume 6293 of Lecture Notes in Bioinformatics. 2010, 78-89."},{"key":"5520_CR14","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1093\/bioinformatics\/btq079","volume":"26","author":"M Muffato","year":"2010","unstructured":"Muffato M, Louis A, Poisnel CE, Crollius HR: Genomicus: a database and a browser to study gene synteny in modern and ancestral genomes. Bioinformatics. 2010, 26: 1119-1121. 10.1093\/bioinformatics\/btq079.","journal-title":"Bioinformatics"},{"key":"5520_CR15","doi-asserted-by":"publisher","first-page":"e1000234","DOI":"10.1371\/journal.pcbi.1000234","volume":"4","author":"C Chauve","year":"2008","unstructured":"Chauve C, Tannier E: A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes. PLoS Computational Biology. 2008, 4: e1000234-10.1371\/journal.pcbi.1000234.","journal-title":"PLoS Computational Biology"},{"issue":"3","key":"5520_CR16","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1109\/TCBB.2008.135","volume":"6","author":"J Stoye","year":"2009","unstructured":"Stoye J, Wittler R: A Unified Approach for Reconstructing Ancient Gene Clusters. IEEE\/ACM Trans Comput Biol Bioinf. 2009, 6 (3): 387-400.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"5520_CR17","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1089\/cmb.2010.0092","volume":"17","author":"C Chauve","year":"2010","unstructured":"Chauve C, Gavranovi\u0107 H, Ouangraoua A, Tannier E: Yeast ancestral genome reconstructions: the possibilities of computational methods II. Journal of Computational Biology. 2010, 17: 1097-1112. 10.1089\/cmb.2010.0092.","journal-title":"Journal of Computational Biology"},{"key":"5520_CR18","volume-title":"Bioinformatics","author":"BR Jones","year":"2012","unstructured":"Jones BR, Rajaraman A, Tannier E, Chauve C: ANGES: Reconstructing ANcestral GEnomeS maps. Bioinformatics. 2012, 18:"},{"key":"5520_CR19","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1089\/cmb.2008.0069","volume":"15","author":"J Ma","year":"2008","unstructured":"Ma J, Ratan A, Raney BJ, Suh BB, Zhang L, Miller W, Haussler D: DUPCAR: reconstructing contiguous ancestral regions with duplications. Journal of Computational Biology. 2008, 15: 1007-1027. 10.1089\/cmb.2008.0069.","journal-title":"Journal of Computational Biology"},{"key":"5520_CR20","volume-title":"Bioinformatics","author":"S B\u00e9rard","year":"2012","unstructured":"B\u00e9rard S, Gallien C, Boussau B, Szollosi G, Daubin V, E T: Evolution of gene neighborhood within reconciled phylogenies. Bioinformatics. 2012"},{"issue":"9","key":"5520_CR21","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1089\/cmb.2011.0083","volume":"18","author":"R Wittler","year":"2011","unstructured":"Wittler R, Ma\u0148uch J, Patterson M, Stoye J: Consistency of sequence-based gene clusters. Journal of Computational Biology. 2011, 18 (9): 1023-1039. 10.1089\/cmb.2011.0083.","journal-title":"Journal of Computational Biology"},{"key":"5520_CR22","first-page":"90","volume-title":"Combinatorial Pattern Matching, Proceedings of CPM'11, Volume 6661 of Lecture Notes in Computer Science","author":"C Chauve","year":"2011","unstructured":"Chauve C, Ma\u0148uch J, Patterson M, Wittler R: Tractability results for the Consecutive-Ones Property with multiplicity. Combinatorial Pattern Matching, Proceedings of CPM'11, Volume 6661 of Lecture Notes in Computer Science. 2011, 90-103."},{"key":"5520_CR23","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D: Computers and Intractability: A Guide to the Theory of NP-completeness. 1979, W. H. Freeman & Co"},{"key":"5520_CR24","volume-title":"Matching Theory, Volume 29 of Annals of Discrete Mathematics","author":"L Lovasz","year":"1986","unstructured":"Lovasz L, Plummer MD: Matching Theory, Volume 29 of Annals of Discrete Mathematics. 1986, North Holland"},{"key":"5520_CR25","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/3-540-58338-6_78","volume-title":"Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science 1994","author":"A Dessmark","year":"1994","unstructured":"Dessmark A, Lingas A, Garrido O: On Parallel Complexity of Maximum f-matching and the Degree Sequence Problem. Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science 1994. 1994, MFCS '94, Springer-Verlag, 316-325."},{"key":"5520_CR26","first-page":"17","volume-title":"Proceedings of FOCS'80","author":"S Micali","year":"1980","unstructured":"Micali S, Vazirani VV: An \"Equation missing\"  No EquationSource Format=\"TEX\", only image and EquationSource Format=\"MATHML\"  algorithm for finding maximum matching in general graphs. Proceedings of FOCS'80. 1980, 17-27."},{"key":"5520_CR27","volume-title":"Computational Complexity","author":"C Papadimitriou","year":"1994","unstructured":"Papadimitriou C: Computational Complexity. 1994, Addison Wesley"},{"key":"5520_CR28","doi-asserted-by":"publisher","first-page":"3012","DOI":"10.1093\/bioinformatics\/btq574","volume":"26","author":"I Mikl\u00f3s","year":"2010","unstructured":"Mikl\u00f3s I, Tannier E: Bayesian sampling of genomic rearrangement scenarios via double cut and join. Bioinformatics. 2010, 26: 3012-3019. 10.1093\/bioinformatics\/btq574.","journal-title":"Bioinformatics"},{"key":"5520_CR29","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.tcs.2012.03.006","volume":"439","author":"I Mikl\u00f3s","year":"2011","unstructured":"Mikl\u00f3s I, Tannier E: Approximating the number of double cut-an-join scenarios. Theoretical Computer Science. 2011, 439: 30-40.","journal-title":"Theoretical Computer Science"},{"key":"5520_CR30","doi-asserted-by":"publisher","first-page":"e1000128","DOI":"10.1371\/journal.pgen.1000128","volume":"4","author":"AE Darling","year":"2008","unstructured":"Darling AE, Mikl\u00f3s I, Ragan MA: Dynamics of genome rearrangement in bacterial populations. PLoS Genetics. 2008, 4: e1000128-10.1371\/journal.pgen.1000128.","journal-title":"PLoS Genetics"},{"key":"5520_CR31","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1748-7188-5-3","volume":"5","author":"P Husemann","year":"2010","unstructured":"Husemann P, Stoye J: Phylogenetic Comparative Assembly. Algorithms for Molecular Biology. 2010, 5: 3-10.1186\/1748-7188-5-3.","journal-title":"Algorithms for Molecular Biology"},{"key":"5520_CR32","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1093\/bib\/bbp026","volume":"10","author":"M Pop","year":"2009","unstructured":"Pop M: Genome assembly reborn: recent computational challenges. Briefings in Bioinformatics. 2009, 10: 354-366. 10.1093\/bib\/bbp026.","journal-title":"Briefings in Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-13-S19-S11.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1471-2105-13-S19-S11\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-13-S19-S11.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T21:19:41Z","timestamp":1630531181000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-13-S19-S11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":32,"journal-issue":{"issue":"S19","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["5520"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-13-s19-s11","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"19 December 2012","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S11"}}