{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T08:14:05Z","timestamp":1768551245026,"version":"3.49.0"},"reference-count":40,"publisher":"Proceedings of the National Academy of Sciences","issue":"38","content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2008,9,23]]},"abstract":"<jats:p>We formalize the problem of recovering the evolutionary history of a set of genomes that are related to an unseen common ancestor genome by operations of speciation, deletion, insertion, duplication, and rearrangement of segments of bases. The problem is examined in the limit as the number of bases in each genome goes to infinity. In this limit, the chromosomes are represented by continuous circles or line segments. For such an infinite-sites model, we present a polynomial-time algorithm to find the most parsimonious evolutionary history of any set of related present-day genomes.<\/jats:p>","DOI":"10.1073\/pnas.0805217105","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T01:10:06Z","timestamp":1221181806000},"page":"14254-14261","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":79,"title":["The infinite sites model of genome evolution"],"prefix":"10.1073","volume":"105","author":[{"given":"Jian","family":"Ma","sequence":"first","affiliation":[{"name":"*Center for Biomolecular Science and Engineering, University of California, Santa Cruz, CA 95064; and"}]},{"given":"Aakrosh","family":"Ratan","sequence":"additional","affiliation":[{"name":"Center for Comparative Genomics and Bioinformatics, Pennsylvania State University, University Park, PA 16802."}]},{"given":"Brian J.","family":"Raney","sequence":"additional","affiliation":[{"name":"*Center for Biomolecular Science and Engineering, University of California, Santa Cruz, CA 95064; and"}]},{"given":"Bernard B.","family":"Suh","sequence":"additional","affiliation":[{"name":"*Center for Biomolecular Science and Engineering, University of California, Santa Cruz, CA 95064; and"}]},{"given":"Webb","family":"Miller","sequence":"additional","affiliation":[{"name":"Center for Comparative Genomics and Bioinformatics, Pennsylvania State University, University Park, PA 16802."}]},{"given":"David","family":"Haussler","sequence":"additional","affiliation":[{"name":"*Center for Biomolecular Science and Engineering, University of California, Santa Cruz, CA 95064; and"}]}],"member":"341","published-online":{"date-parts":[[2008,9,23]]},"reference":[{"key":"e_1_3_3_1_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/15.11.909"},{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/978-94-011-4309-7_46","volume-title":"Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and the Evolution of Gene Families","author":"Sankoff D","year":"2000","unstructured":"D Sankoff, N El-Mabrouk, Duplication, rearrangement and reconciliation. Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and the Evolution of Gene Families (Kluwer, Dordrecht, The Netherlands), pp. 537\u2013550 (2000)."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1086132"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.039"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1128\/MCB.16.5.2164"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1128\/mcb.6.12.4295-4304.1986"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1093\/genetics\/61.4.893"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0040-5809(83)90013-8"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti535"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.0030209"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700377177"},{"key":"e_1_3_3_12_2","first-page":"1748","article-title":"Whole genome duplications and contracted breakpoint graphs","volume":"36","author":"Alekseyev MA","year":"2007","unstructured":"MA Alekseyev, PA Pevzner, Whole genome duplications and contracted breakpoint graphs. Soc Indust Appl Math J Comput 36, 1748\u20131763 (2007).","journal-title":"Soc Indust Appl Math J Comput"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-3211-9.50009-7"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01731581"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02101694"},{"key":"e_1_3_3_16_2","doi-asserted-by":"crossref","unstructured":"A Caprara Formulations and complexity of multiple sorting by reversals. (ACM Press New York) pp. 84\u201393 (1999).","DOI":"10.1145\/299432.299461"},{"key":"e_1_3_3_17_2","first-page":"583","article-title":"A new implementation and detailed study of breakpoint analysis","author":"Moret BME","year":"2001","unstructured":"BME Moret, SK Wyman, D A Bader, T Warnow, M Yan, A new implementation and detailed study of breakpoint analysis. Pac Symp Biocomput, pp. 583\u2013594 (2001).","journal-title":"Pac Symp Biocomput"},{"key":"e_1_3_3_18_2","first-page":"26","article-title":"Genome-scale evolution: Reconstructing gene orders in the ancestral species","volume":"12","author":"Bourque G","year":"2002","unstructured":"G Bourque, PA Pevzner, Genome-scale evolution: Reconstructing gene orders in the ancestral species. Genome Res 12, 26\u201336 (2002).","journal-title":"Genome Res"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1101\/gr.5383506"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1111387"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature05805"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.12.006"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.genet.32.1.619"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.genet.37.110801.143214"},{"key":"e_1_3_3_25_2","first-page":"104","article-title":"The reconstruction of evolution","volume":"27","author":"Edwards AWF","year":"1963","unstructured":"AWF Edwards, LL Cavalli-Sforza, The reconstruction of evolution. Ann Hum Genet 27, 104\u2013105 (1963).","journal-title":"Ann Hum Genet"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1558-5646.1965.tb01722.x"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_3_3_28_2","doi-asserted-by":"crossref","unstructured":"S Hannenhalli PA Pevzner Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). (ACM Press New York) pp. 178\u2013189","DOI":"10.1145\/225058.225112"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0603984103"},{"key":"e_1_3_3_30_2","first-page":"90","article-title":"Constructing a tree on the basis of a set of distances between the hanging vertices","volume":"20","author":"Zaretskii KA","year":"1965","unstructured":"KA Zaretskii, Constructing a tree on the basis of a set of distances between the hanging vertices. Uspekhi Mat Nauk 20, 90\u201392 (1965).","journal-title":"Uspekhi Mat Nauk"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(77)90351-4"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.2307\/2412448"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9525(00)02005-9"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1101\/gr.809403"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2005.12.812"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2008.0069"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1101\/gr.3002305"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1101\/gr.5918807"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth931"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature06862"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.0805217105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T22:23:40Z","timestamp":1738362220000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.0805217105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9,23]]},"references-count":40,"journal-issue":{"issue":"38","published-print":{"date-parts":[[2008,9,23]]}},"alternative-id":["10.1073\/pnas.0805217105"],"URL":"https:\/\/doi.org\/10.1073\/pnas.0805217105","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9,23]]},"assertion":[{"value":"2008-03-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}