{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T16:34:36Z","timestamp":1720802076114},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2014,12]]},"DOI":"10.1186\/1471-2105-15-206","type":"journal-article","created":{"date-parts":[[2014,6,19]],"date-time":"2014-06-19T17:16:29Z","timestamp":1403198189000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A unifying model of genome evolution under parsimony"],"prefix":"10.1186","volume":"15","author":[{"given":"Benedict","family":"Paten","sequence":"first","affiliation":[]},{"given":"Daniel R","family":"Zerbino","sequence":"additional","affiliation":[]},{"given":"Glenn","family":"Hickey","sequence":"additional","affiliation":[]},{"given":"David","family":"Haussler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,6,19]]},"reference":[{"issue":"7","key":"6473_CR1","doi-asserted-by":"publisher","first-page":"1323","DOI":"10.1089\/cmb.2006.13.1323","volume":"13","author":"I Elias","year":"2006","unstructured":"Elias I: Settling the intractability of multiple alignment. J Comput Biol. 2006, 13 (7): 1323-1339.","journal-title":"J Comput Biol"},{"issue":"12","key":"6473_CR2","first-page":"1797","volume":"17","author":"W Miller","year":"2007","unstructured":"Miller W, Rosenbloom K, Hardison RC, Hou M, Taylor J, Raney B, Burhans R, King DC, Baertsch R, Blankenberg D, Kosakovsky Pond SL, Nekrutenko A, Giardine B, Harris RS, Tyekucheva S, Diekhans M, Pringle TH, Murphy WJ, Lesk S, Weinstock GM, Lindblad-Toh K, Gibbs RA, Lander ES, Siepel A, Haussler D, Kent WJ: 28-way vertebrate alignment and conservation track in the UCSC Genome browser. Genes Dev. 2007, 17 (12): 1797-1808.","journal-title":"Genes Dev"},{"issue":"6","key":"6473_CR3","doi-asserted-by":"publisher","first-page":"e11147","DOI":"10.1371\/journal.pone.0011147","volume":"5","author":"AE Darling","year":"2010","unstructured":"Darling AE, Mau B, Perna NT: Progressivemauve: multiple genome alignment with gene gain, loss and rearrangement. PloS one. 2010, 5 (6): e11147-","journal-title":"PloS one"},{"issue":"9","key":"6473_CR4","doi-asserted-by":"publisher","first-page":"1512","DOI":"10.1101\/gr.123356.111","volume":"21","author":"B Paten","year":"2011","unstructured":"Paten B, Earl D, Nguyen N, Diekhans M, Zerbino D, Haussler D: Cactus: algorithms for genome multiple sequence alignment. Genome Res. 2011, 21 (9): 1512-1528.","journal-title":"Genome Res"},{"key":"6473_CR5","volume-title":"Inferring Phylogenies","author":"J Felsenstein","year":"2004","unstructured":"Felsenstein J: Inferring Phylogenies. 2004, Sinauer Associates: Sunderland"},{"issue":"12","key":"6473_CR6","doi-asserted-by":"publisher","first-page":"2412","DOI":"10.1101\/gr.2800104","volume":"14","author":"M Blanchette","year":"2004","unstructured":"Blanchette M, Green ED, Miller W, Haussler D: Reconstructing large regions of an ancestral mammalian genome in silico. Genome Res. 2004, 14 (12): 2412-2423.","journal-title":"Genome Res"},{"issue":"3","key":"6473_CR7","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1093\/bioinformatics\/btl578","volume":"23","author":"J Kim","year":"2007","unstructured":"Kim J, Sinha S: Indelign: a probabilistic framework for annotation of insertions and deletions in a multiple alignment. Bioinformatics (Oxford, England). 2007, 23 (3): 289-297.","journal-title":"Bioinformatics (Oxford, England)"},{"issue":"11","key":"6473_CR8","doi-asserted-by":"publisher","first-page":"1829","DOI":"10.1101\/gr.076521.108","volume":"18","author":"B Paten","year":"2008","unstructured":"Paten B, Herrero J, Fitzgerald S, Beal K, Flicek P, Holmes I, Birney E: Genome-wide nucleotide-level mammalian ancestor reconstruction. Genome Res. 2008, 18 (11): 1829-1843.","journal-title":"Genome Res"},{"issue":"4","key":"6473_CR9","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF02458863","volume":"49","author":"W Day","year":"1987","unstructured":"Day W: Computational complexity of inferring phylogenies from dissimilarity matrices. Bull Math Biol. 1987, 49 (4): 461-467.","journal-title":"Bull Math Biol"},{"issue":"3","key":"6473_CR10","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1142\/S0219720006002168","volume":"4","author":"L Chindelevitch","year":"2006","unstructured":"Chindelevitch L, Li Z, Blais E, Blanchette M: On the inference of parsimonious indel evolutionary scenarios. J Bioinform Comput Biol. 2006, 4 (3): 721-744.","journal-title":"J Bioinform Comput Biol"},{"issue":"2","key":"6473_CR11","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1089\/cmb.2005.12.147","volume":"12","author":"YS Song","year":"2005","unstructured":"Song YS, Hein J: Constructing minimal ancestral recombination graphs. J Comput Biol. 2005, 12 (2): 147-169.","journal-title":"J Comput Biol"},{"issue":"3","key":"6473_CR12","doi-asserted-by":"publisher","first-page":"e1000318","DOI":"10.1371\/journal.pcbi.1000318","volume":"5","author":"O Westesson","year":"2009","unstructured":"Westesson O, Holmes I: Accurate detection of recombinant breakpoints in whole-genome alignments. PLoS Comput Biol. 2009, 5 (3): e1000318-","journal-title":"PLoS Comput Biol"},{"issue":"1","key":"6473_CR13","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1089\/106652701300099119","volume":"8","author":"LL Wang","year":"2001","unstructured":"Wang LL, Zhang KK, Zhang LL: Perfect phylogenetic networks with recombination. J Comput Biol. 2001, 8 (1): 69-78.","journal-title":"J Comput Biol"},{"key":"6473_CR14","doi-asserted-by":"crossref","unstructured":"Bergeron A, Mixtacki J, Stoye J: A unifying view of genome rearrangements. Lecture Notes in Bioinformatics. 4175: 163-173.","DOI":"10.1007\/11851561_16"},{"issue":"2\u20133","key":"6473_CR15","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/j.tcs.2008.01.013","volume":"395","author":"M Alekseyev","year":"2008","unstructured":"Alekseyev M, Pevzner P: Multi-break rearrangements and chromosomal evolution. Theor Comput Sci. 2008, 395 (2\u20133): 193-202.","journal-title":"Theor Comput Sci"},{"issue":"1","key":"6473_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S Hannenhalli","year":"1999","unstructured":"Hannenhalli S, Pevzner PA: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J ACM. 1999, 46 (1): 1-27.","journal-title":"J ACM"},{"issue":"2","key":"6473_CR17","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1089\/cmb.2006.13.567","volume":"13","author":"A Bergeron","year":"2006","unstructured":"Bergeron A, Mixtacki J, Stoye J: On sorting by translocations. J Comput Biol. 2006, 13 (2): 567-578.","journal-title":"J Comput Biol"},{"issue":"16","key":"6473_CR18","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 (16): 3340-3346.","journal-title":"Bioinformatics"},{"key":"6473_CR19","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1145\/299432.299461","volume":"1","author":"A Caprara","year":"1999","unstructured":"Caprara A: Formulations and hardness of multiple sorting by reversals. Proc. 3rd Conf. Computational Molecular Biology RECOMB99. 1999, 1: 84-93.","journal-title":"Proc. 3rd Conf. Computational Molecular Biology RECOMB99"},{"issue":"10","key":"6473_CR20","doi-asserted-by":"publisher","first-page":"1369","DOI":"10.1089\/cmb.2009.0087","volume":"16","author":"AW Xu","year":"2009","unstructured":"Xu AW: A fast and exact algorithm for the median of three problem: a graph decomposition approach. J Comput Biol. 2009, 16 (10): 1369-1381.","journal-title":"J Comput Biol"},{"issue":"1","key":"6473_CR21","first-page":"26","volume":"12","author":"G Bourque","year":"2002","unstructured":"Bourque G, Pevzner PA: Genome-scale evolution: reconstructing gene orders in the ancestral species. Genome Res. 2002, 12 (1): 26-36.","journal-title":"Genome Res"},{"issue":"38","key":"6473_CR22","doi-asserted-by":"publisher","first-page":"14254","DOI":"10.1073\/pnas.0805217105","volume":"105","author":"J Ma","year":"2008","unstructured":"Ma J, Ratan A, Raney BJ, Suh BB, Miller W, Haussler D: The infinite sites model of genome evolution. Proc Natl Acad Sci USA. 2008, 105 (38): 14254-14261.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"1","key":"6473_CR23","first-page":"105","volume":"1","author":"N El-Mabrouk","year":"2000","unstructured":"El-Mabrouk N: Sorting signed permutations by reversals and insertions\/deletions of contiguous segments. J Discrete Algorithm. 2000, 1 (1): 105-121.","journal-title":"J Discrete Algorithm"},{"issue":"10","key":"6473_CR24","doi-asserted-by":"publisher","first-page":"1311","DOI":"10.1089\/cmb.2009.0092","volume":"16","author":"S Yancopoulos","year":"2009","unstructured":"Yancopoulos S, Friedberg R: DCJ path formulation for genome transformations which include insertions, deletions, and duplications. J Comput Biol. 2009, 16 (10): 1311-1338.","journal-title":"J Comput Biol"},{"issue":"9","key":"6473_CR25","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1089\/cmb.2011.0118","volume":"18","author":"MD Braga","year":"2011","unstructured":"Braga MD, Willing E, Stoye J: Double cut and join with insertions and deletions. J Comput Biol. 2011, 18 (9): 1167-1184.","journal-title":"J Comput Biol"},{"key":"6473_CR26","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/978-1-61779-582-4_15","volume":"855","author":"N El-Mabrouk","year":"2012","unstructured":"El-Mabrouk N, Sankoff D: Analysis of gene order evolution beyond single-copy genes. Methods Mol Biol. 2012, 855: 397-429.","journal-title":"Methods Mol Biol"},{"key":"6473_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5298-9","volume-title":"Models and Algorithms for Genome Evolution","author":"C Chauve","year":"2013","unstructured":"Chauve C, El-Mabrouk N, Gueguen L, Semeria M, Tannier E: Models and Algorithms for Genome Evolution. 2013, London: Springer-Verlag"},{"issue":"Suppl 1","key":"6473_CR28","doi-asserted-by":"publisher","first-page":"S27","DOI":"10.1186\/1471-2105-11-S1-S27","volume":"11","author":"M Bader","year":"2010","unstructured":"Bader M: Genome rearrangements with duplications. BMC Bioinformatics. 2010, 11 (Suppl 1): S27-S27.","journal-title":"BMC Bioinformatics"},{"issue":"Suppl 19","key":"6473_CR29","doi-asserted-by":"publisher","first-page":"S13","DOI":"10.1186\/1471-2105-13-S19-S13","volume":"13","author":"M Shao","year":"2012","unstructured":"Shao M, Lin Y: Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion. BMC Bioinformatics. 2012, 13 (Suppl 19): S13-","journal-title":"BMC Bioinformatics"},{"issue":"11","key":"6473_CR30","doi-asserted-by":"publisher","first-page":"2336","DOI":"10.1101\/gr.2657504","volume":"14","author":"B Raphael","year":"2004","unstructured":"Raphael B, Zhi D, Tang H, Pevzner P: A novel method for multiple alignment of sequences with repeated and shuffled elements. Genome Res. 2004, 14 (11): 2336-2346.","journal-title":"Genome Res"},{"issue":"3","key":"6473_CR31","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1089\/cmb.2010.0252","volume":"18","author":"B Paten","year":"2011","unstructured":"Paten B, Diekhans M, Earl D, John JS, Ma J, Suh B, Haussler D: Cactus graphs for genome comparisons. J Comput Biol. 2011, 18 (3): 469-481.","journal-title":"J Comput Biol"},{"issue":"8","key":"6473_CR32","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1089\/cmb.2009.0047","volume":"16","author":"P Medvedev","year":"2009","unstructured":"Medvedev P, Brudno M: Maximum likelihood genome assembly. J Comput Biol. 2009, 16 (8): 1101-1116.","journal-title":"J Comput Biol"},{"key":"6473_CR33","first-page":"27","volume-title":"Matching: A Well-Solved Class of Integer Linear Programs","author":"J Edmonds","year":"1970","unstructured":"Edmonds J, Johnson EL: Matching: A Well-Solved Class of Integer Linear Programs. 1970, 27-30."},{"key":"6473_CR34","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1186\/1471-2105-10-120","volume":"10","author":"E Tannier","year":"2009","unstructured":"Tannier E, Zheng C, Sankoff D: Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics. 2009, 10: 120-","journal-title":"BMC Bioinformatics"},{"key":"6473_CR35","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/S0927-0507(05)80125-2","volume":"7","author":"D Bienstock","year":"1994","unstructured":"Bienstock D, Langston MA: Algorithmic implications of the graph minor theorem. Handbooks in Operations Research and Management Science. 1994, 7: 481-502.","journal-title":"Handbooks in Operations Research and Management Science"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-15-206.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T12:10:02Z","timestamp":1689336602000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-15-206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,19]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["6473"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-15-206","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,19]]},"assertion":[{"value":"12 December 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2014","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2014","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"206"}}