{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:41:09Z","timestamp":1773272469123,"version":"3.50.1"},"reference-count":15,"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":[[2010,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>There has been a trend in increasing the phylogenetic scope of genome sequencing without finishing the sequence of the genome. Increasing numbers of genomes are being published in scaffold or contig form. Rearrangement algorithms, however, including gene order-based phylogenetic tools, require whole genome data on gene order or syntenic block order. How then can we use rearrangement algorithms to compare genomes available in scaffold form only? Can the comparative evidence predict the location of unsequenced genes?<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>Our method involves optimally filling in genes missing from the scaffolds, while incorporating the augmented scaffolds directly into the rearrangement algorithms as if they were chromosomes. This is accomplished by an exact, polynomial-time algorithm. We then correct for the number of extra fusion\/fission operations required to make scaffolds comparable to full assemblies. We model the relationship between the ratio of missing genes actually absent from the genome versus merely unsequenced ones, on one hand, and the increase of genomic distance after scaffold filling, on the other. We estimate the parameters of this model through simulations and by comparing the angiosperm genomes <jats:italic>Ricinus communis<\/jats:italic> and <jats:italic>Vitis vinifera<\/jats:italic>.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>The algorithm solves the comparison of genomes with 18,300 genes, including 4500 missing from one genome, in less than a minute on a MacBook, putting virtually all genomes within range of the method.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-11-304","type":"journal-article","created":{"date-parts":[[2010,6,4]],"date-time":"2010-06-04T18:14:45Z","timestamp":1275675285000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":52,"title":["Scaffold filling, contig fusion and comparative gene order inference"],"prefix":"10.1186","volume":"11","author":[{"given":"Adriana","family":"Mu\u00f1oz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chunfang","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qian","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor A","family":"Albert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steve","family":"Rounsley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Sankoff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,6,4]]},"reference":[{"key":"3761_CR1","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1126\/science.1180614","volume":"326","author":"PS Chain","year":"2009","unstructured":"Chain PS, Grafham DV, Fulton RS, Fitzgerald MG, Hostetler J, Muzny D, Ali J, Birren B, Bruce DC, Buhay C, Cole JR, Ding Y, Dugan S, Field D, Garrity GM, Gibbs R, Graves T, Han CS, Harrison SH, Highlander S, Hugenholtz P, Khouri HM, Kodira CD, Kolker E, Kyrpides NC, Lang D, Lapidus A, Malfatti SA, Markowitz V, Metha T, Nelson KE, Parkhill J, Pitluck S, Qin X, Read TD, Schmutz J, Sozhamannan S, Sterk P, Strausberg RL, Sutton G, Thomson NR, Tiedje JM, Weinstock G, Wollam A, Genomic Standards Consortium Human Microbiome Project Jumpstart Consortium, Detter JC: Genome project standards in a new era of sequencing. Science 2009, 326: 236\u2013237. 10.1126\/science.1180614","journal-title":"Science"},{"key":"3761_CR2","doi-asserted-by":"publisher","first-page":"1353","DOI":"10.1089\/cmb.2009.0103","volume":"16","author":"D Sankoff","year":"2009","unstructured":"Sankoff D, Zheng C, Wall PK, dePamphilis C, Leebens-Mack J, Albert VA: Towards improved reconstruction of ancestral gene order in angiosperm phylogeny. Journal of Computational Biology 2009, 16: 1353\u20131367. 10.1089\/cmb.2009.0103","journal-title":"Journal of Computational Biology"},{"key":"3761_CR3","volume-title":"Transactions in Computational Biology and Bioinformatics","author":"A Mu\u00f1oz","year":"2010","unstructured":"Mu\u00f1oz A, Sankoff D: Rearrangement phylogeny of genomes in contig form. Transactions in Computational Biology and Bioinformatics 2010, in press."},{"key":"3761_CR4","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\u20136. 10.1093\/bioinformatics\/bti535","journal-title":"Bioinformatics"},{"key":"3761_CR5","first-page":"163","volume":"4175","author":"A Bergeron","year":"2006","unstructured":"Bergeron A, Mixtacki J, Stoye J: A unifying view of genome rearrangements. In Algorithms in Bioinformatics. Proceedings of WABI 2006. Lecture Notes in Computer Science 2006, 4175: 163\u2013173.","journal-title":"Algorithms in Bioinformatics. Proceedings of WABI 2006. Lecture Notes in Computer Science"},{"key":"3761_CR6","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1016\/S0022-0000(02)00011-9","volume":"65","author":"G Tesler","year":"2002","unstructured":"Tesler G: Efficient algorithms for multichromosomal genome rearrangements. Journal of Computer and System Sciences 2002, 65: 587\u2013609. 10.1016\/S0022-0000(02)00011-9","journal-title":"Journal of Computer and System Sciences"},{"key":"3761_CR7","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1142\/S0219720009004199","volume":"27","author":"C Zheng","year":"2009","unstructured":"Zheng C, Wall PK, Leebens-Mack J, dePamphilis C, Albert VA, Sankoff D: Gene loss under neighbourhood selection following whole genome duplication and the reconstruction of the ancestral populus genome. Journal of Bioinformatics and Computational Biology 2009, 27: 499\u2013520. 10.1142\/S0219720009004199","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"3761_CR8","first-page":"277","volume-title":"Genetic diversity of cultivated tropical plants","author":"M Seguin","year":"2003","unstructured":"Seguin M, Flori A, Legnat\u00e9 H, Cl\u00e9ment-Demange A: Rubber tree. In Genetic diversity of cultivated tropical plants. Edited by: Hamon P, Seguin M, Perrier X, Glaszmann C. Montpellier: CIRAD; 2003:277\u2013306."},{"key":"3761_CR9","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.1089\/cmb.2009.0139","volume":"16","author":"JG Burleigh","year":"2009","unstructured":"Burleigh JG, Bansal MS, Wehe A, Eulenstein O: Locating large-scale gene duplication events through reconciled trees: implications for identifying ancient polyploidy events in plants. Journal of Computational Biology 2009, 16: 1071\u20131083. 10.1089\/cmb.2009.0139","journal-title":"Journal of Computational Biology"},{"key":"3761_CR10","doi-asserted-by":"publisher","first-page":"e1326","DOI":"10.1371\/journal.pone.0001326","volume":"2","author":"R Velasco","year":"2007","unstructured":"Velasco R, Zharkikh A, Troggio M, Cartwright DA, Cestaro A, Pruss D, Pindo M, Fitzgerald LM, Vezzulli S, Reid J, Malacarne G, Iliev D, Coppola G, Wardell B, Micheletti D, Macalma T, Facci M, Mitchell JT, Perazzolli M, Eldredge G, Gatto P, Oyzerski R, Moretto M, Gutin N, Stefanini M, Chen Y, Segala C, Davenport C, Dematt\u00e8 L, Mraz A, Battilana J, Stormo K, Costa F, Tao Q, Si-Ammour A, Harkins T, Lackey A, Perbost C, Taillon B, Stella A, Solovyev V, Fawcett JA, Sterck L, Vandepoele K, Grando SM, Toppo S, Moser C, Lanchbury J, Bogden R, Skolnick M, Sgaramella V, Bhatnagar SK, Fontana P, Gutin A, Van de Peer Y, Salamini F, Viola R: A high quality draft consensus sequence of the genome of a heterozygous grapevine variety. PLoS ONE 2007, 2: e1326. 10.1371\/journal.pone.0001326","journal-title":"PLoS ONE"},{"key":"3761_CR11","doi-asserted-by":"publisher","first-page":"336","DOI":"10.3732\/ajb.0800079","volume":"96","author":"DE Soltis","year":"2009","unstructured":"Soltis DE, Albert VA, Leebens-Mack J, Bell CD, Paterson AH, Zheng C, Sankoff D, dePamphilis CW, Wall PK, Soltis PS: Polyploidy and angiosperm diversification. American Journal of Botany 2009, 96: 336\u2013348. 10.3732\/ajb.0800079","journal-title":"American Journal of Botany"},{"key":"3761_CR12","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1038\/nature06148","volume":"449","author":"O Jaillon","year":"2007","unstructured":"Jaillon O, Aury JM, Noel B, Policriti A, Clepet C, Casagrande A, Choisne N, Aubourg S, Vitulo N, Jubin C, Vezzi A, Legeai F, Hugueney P, Dasilva C, Horner D, Mica E, Jublot D, Poulain J, Bruy\u00e8re C, Billault A, Segurens B, Gouyvenoux M, Ugarte E, Cattonaro F, Anthouard V, Vico V, Del Fabbro C, Alaux M, Di Gaspero G, Dumas V, Felice N, Paillard S, Juman I, Moroldo M, Scalabrin S, Canaguier A, Le Clainche I, Malacrida G, Durand E, Pesole G, Laucou V, Chatelet P, Merdinoglu D, Delledonne M, Pezzotti M, Lecharny A, Scarpelli C, Artiguenave F, P\u00e8 ME, Valle G, Morgante M, Caboche M, Adam-Blondon AF, Weissenbach J, Qu\u00e9tier F, Wincker P, French-Italian Public Consortium for Grapevine Genome Characterization: The grapevine genome sequence suggests ancestral hexaploidization in major angiosperm phyla. Nature 2007, 449: 463\u2013467. 10.1038\/nature06148","journal-title":"Nature"},{"key":"3761_CR13","doi-asserted-by":"publisher","first-page":"2178","DOI":"10.1101\/gr.1224503","volume":"13","author":"L Li","year":"2003","unstructured":"Li L, Stoeckert CJ Jr, Roos DS: OrthoMCL: identification of ortholog groups for eukaryotic genomes. Genome Research 2003, 13: 2178\u20132189. 10.1101\/gr.1224503","journal-title":"Genome Research"},{"key":"3761_CR14","doi-asserted-by":"publisher","first-page":"D476","DOI":"10.1093\/nar\/gki107","volume":"33","author":"KP O'Brien","year":"2005","unstructured":"O'Brien KP, Remm M, Sonnhammer EL: Inparanoid: a comprehensive database of eukaryotic orthologs. Nucleic Acids Research 2005, 33: D476\u201380. 10.1093\/nar\/gki107","journal-title":"Nucleic Acids Research"},{"key":"3761_CR15","unstructured":"MSOAR. A high-throughput ortholog assignment system[http:\/\/msoar.cs.ucr.edu\/]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-11-304.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T12:08:47Z","timestamp":1630498127000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-11-304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,4]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["3761"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-11-304","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,4]]},"assertion":[{"value":"23 December 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"304"}}