{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T21:46:37Z","timestamp":1722721597814},"reference-count":29,"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>The \"small phylogeny\" problem consists in inferring ancestral genomes associated with each internal node of a phylogenetic tree of a set of extant species. Existing methods can be grouped into two main categories: the distance-based methods aiming at minimizing a total branch length, and the synteny-based (or mapping) methods that first predict a collection of relations between ancestral markers in term of \"synteny\", and then assemble this collection into a set of Contiguous Ancestral Regions (CARs). The predicted CARs are likely to be more reliable as they are more directly deduced from observed conservations in extant species. However the challenge is to end up with a completely assembled genome.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We develop a new synteny-based method that is flexible enough to handle a model of evolution involving whole genome duplication events, in addition to rearrangements, gene insertions, and losses. Ancestral relationships between markers are defined in term of <jats:italic>Gapped Adjacencies<\/jats:italic>, i.e. pairs of markers separated by up to a given number of markers. It improves on a previous restricted to direct adjacencies, which revealed a high accuracy for adjacency prediction, but with the drawback of being overly conservative, i.e. of generating a large number of CARs. Applying our algorithm on various simulated data sets reveals good performance as we usually end up with a completely assembled genome, while keeping a low error rate.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Availability<\/jats:title>\n            <jats:p>All source code is available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/www.iro.umontreal.ca\/~mabrouk\" ext-link-type=\"uri\">http:\/\/www.iro.umontreal.ca\/~mabrouk<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-13-s19-s4","type":"journal-article","created":{"date-parts":[[2019,12,11]],"date-time":"2019-12-11T01:59:28Z","timestamp":1576029568000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["A flexible ancestral genome reconstruction method based on gapped adjacencies"],"prefix":"10.1186","volume":"13","author":[{"given":"Yves","family":"Gagnon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Blanchette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,12,19]]},"reference":[{"key":"5513_CR1","first-page":"14","volume-title":"LNCS, vol 3240 WABI","author":"A Bergeron","year":"2004","unstructured":"Bergeron A, Blanchette M, Chateau A, Chauve C: Reconstruction of ancestral gene order using conserved intervals. LNCS, vol 3240 WABI. 2004, 14-25."},{"key":"5513_CR2","first-page":"78","volume-title":"LNCS, Volume 6293 of WABI","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. LNCS, Volume 6293 of WABI. 2010, Springer, 78-89."},{"key":"5513_CR3","first-page":"26","volume":"12","author":"G Bourque","year":"2002","unstructured":"Bourque G, Pevzner P: Genome-Scale Evolution: Reconstructing Gene Orders in the Ancestral Species. Genome Research. 2002, 12: 26-36.","journal-title":"Genome Research"},{"key":"5513_CR4","doi-asserted-by":"publisher","first-page":"11","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 Comp Biol. 2008, 4: 11-10.1371\/journal.pcbi.0040011.","journal-title":"Plos Comp Biol"},{"key":"5513_CR5","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":"5513_CR6","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1089\/cmb.1998.5.555","volume":"5","author":"D Sankoff","year":"1998","unstructured":"Sankoff D, Blanchette M: Multiple genome rearrangement and breakpoint phylogeny. Journal of Computational Biology. 1998, 5: 555-570. 10.1089\/cmb.1998.5.555.","journal-title":"Journal of Computational Biology"},{"key":"5513_CR7","first-page":"S4","volume":"12","author":"C Zheng","year":"2011","unstructured":"Zheng C, Sankoff D: On the Pathgroups approach to rapid small phylogeny. BMC Bioinfo. 2011, 12: S4-","journal-title":"BMC Bioinfo"},{"key":"5513_CR8","volume-title":"BMC Bioinfo, Volume 5 of Electronic colloquium on computational complexity","author":"I Pe'er","year":"1998","unstructured":"Pe'er I, Shamir R: The median problems for breakpoints are NP-complete. BMC Bioinfo, Volume 5 of Electronic colloquium on computational complexity. 1998"},{"key":"5513_CR9","doi-asserted-by":"crossref","unstructured":"Chauve C, Gavranovic H, Ouangraoua A, Tannier E: Yeast ancestral genome reconstruction. Plos Comput Biol. 2008, 4 (11):","DOI":"10.1371\/journal.pcbi.1000234"},{"key":"5513_CR10","unstructured":"El-Mabrouk N, Sankoff D: Analysis of Gene Order Evolution beyond Single-Copy Genes, Springer (Humana), Volume Evolutionary Genomics: statistical and computational methods of Methods in Mol. Biol. chap. Part II"},{"issue":"8","key":"5513_CR11","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 C, Crollius HR: Genomicus: a database and a browser to study gene synteny in modern and ancestral genomes. Bioinformatics. 2010, 26 (8): 1119-1121. 10.1093\/bioinformatics\/btq079.","journal-title":"Bioinformatics"},{"issue":"ISMB 2011","key":"5513_CR12","doi-asserted-by":"publisher","first-page":"i257","DOI":"10.1093\/bioinformatics\/btr224","volume":"27","author":"H Gavranovic","year":"2011","unstructured":"Gavranovic H, Chauve C, Salse J, Tannier E: Mapping ancestral genomes with massive gene loss. Bioinformatics. 2011, 27 (ISMB 2011): i257-i265.","journal-title":"Bioinformatics"},{"key":"5513_CR13","first-page":"247","volume":"235","author":"D Bryant","year":"2000","unstructured":"Bryant D: A Lower Bound for the Breakpoint Phylogeny Problem. CPM'00. 2000, 235: 247-","journal-title":"CPM'00"},{"key":"5513_CR14","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1137\/S0097539700377177","volume":"32","author":"N El-Mabrouk","year":"2003","unstructured":"El-Mabrouk N, Sankoff D: The Reconstruction of Doubled Genomes. SIAM Journal on Computing. 2003, 32: 754-792. 10.1137\/S0097539700377177.","journal-title":"SIAM Journal on Computing"},{"key":"5513_CR15","first-page":"21","volume-title":"SIAM Journal on Computing, Volume 15 of Pacific Symposium on Biocomputing","author":"H Gavranovi\u0107","year":"2010","unstructured":"Gavranovi\u0107 H, Tannier E: Guided genome halving. SIAM Journal on Computing, Volume 15 of Pacific Symposium on Biocomputing. 2010, 21-30."},{"key":"5513_CR16","first-page":"96","volume-title":"SIAM Journal on Computing, ISMB","author":"C Zheng","year":"2008","unstructured":"Zheng C, Zhu Q, Adam Z, Sankoff D: Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes. SIAM Journal on Computing, ISMB. 2008, 96-104."},{"issue":"8","key":"5513_CR17","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1089\/cmb.2008.0118","volume":"15","author":"C Zheng","year":"2008","unstructured":"Zheng C, Zhu Q, Sankoff D: Descendants of Whole Genome Dup. within Gene Order Phylogeny. Journal of Computational Biology. 2008, 15 (8): 947-964. 10.1089\/cmb.2008.0118.","journal-title":"Journal of Computational Biology"},{"key":"5513_CR18","doi-asserted-by":"crossref","unstructured":"Gordon J, Byrne K, Wolfe K: Additions, Losses, and Rearrangements on the Evolutionary Route from a Reconstructed Ancestor to the Modern S. cerevisiae Genome. PloS Genetics. 2009, 5 (5):","DOI":"10.1371\/journal.pgen.1000485"},{"issue":"19","key":"5513_CR19","doi-asserted-by":"publisher","first-page":"2664","DOI":"10.1093\/bioinformatics\/btr461","volume":"27","author":"A Ouangraoua","year":"2011","unstructured":"Ouangraoua A, Tannier E, Chauve C: Reconstructing the architecture of the ancestral amniote genome. Bioinformatics. 2011, 27 (19): 2664-2671. 10.1093\/bioinformatics\/btr461.","journal-title":"Bioinformatics"},{"key":"5513_CR20","volume-title":"Bioinformatics algorithms: techniques and applications, Wiley","author":"A Bergeron","year":"2008","unstructured":"Bergeron A, Chauve C, Gingras Y: Formal models of gene clusters. Bioinformatics algorithms: techniques and applications, Wiley. 2008"},{"issue":"20","key":"5513_CR21","doi-asserted-by":"publisher","first-page":"11484","DOI":"10.1073\/pnas.1932072100","volume":"100","author":"WJ Kent","year":"2003","unstructured":"Kent WJ, Haussler D: Evolution's cauldron: duplication, deletion, and rearrangement in the mouse and human genomes. Proc Natl Acad Sci USA. 2003, 100 (20): 11484-11489. 10.1073\/pnas.1932072100.","journal-title":"Proc Natl Acad Sci USA"},{"key":"5513_CR22","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin S, Kernighan B: An effective heuristic algorithm for the traveling salesman problem. Operations Research. 1973, 21: 498-516. 10.1287\/opre.21.2.498.","journal-title":"Operations Research"},{"key":"5513_CR23","volume-title":"Genome Research","author":"F Murat","year":"2010","unstructured":"Murat F, Xu J, Tannier E, Abrouk M, Guilhot N, Pont C, Messing J, Salse J: Ancestral grass karyotype reconstruction unravels new mechanisms of genome shuffling as a source of plant evolution. Genome Research. 2010"},{"key":"5513_CR24","doi-asserted-by":"publisher","first-page":"D883","DOI":"10.1093\/nar\/gkl976","volume":"35","author":"S Ouyang","year":"2007","unstructured":"Ouyang S: The TIGR Rice Genome Annotation Resource: improvements and new features. Nucleic Acids Research. 2007, 35: D883-D885. 10.1093\/nar\/gkl976.","journal-title":"Nucleic Acids Research"},{"key":"5513_CR25","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1038\/nature07723","volume":"457","author":"A Paterson","year":"2009","unstructured":"Paterson A: The Sorghum bicolor genome and the diversification of grasses. Nature. 2009, 457: 551-556. 10.1038\/nature07723.","journal-title":"Nature"},{"key":"5513_CR26","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1038\/nature08747","volume":"463","author":"International Brachypodium Initiative","year":"2010","unstructured":"International Brachypodium Initiative: Genome sequencing and analysis of the model grass Brachypodium distachyon. Nature. 2010, 463: 763-768. 10.1038\/nature08747.","journal-title":"Nature"},{"key":"5513_CR27","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1186\/1471-2105-8-82","volume":"8","author":"A Sinha","year":"2007","unstructured":"Sinha A, Meller J: Cinteny: flexible analysis and visualization of synteny and genome rearrangements. BMC Bioinformatics. 2007, 8: 82-10.1186\/1471-2105-8-82.","journal-title":"BMC Bioinformatics"},{"issue":"10","key":"5513_CR28","doi-asserted-by":"publisher","first-page":"1456","DOI":"10.1101\/gr.3672305","volume":"15","author":"K Byrne","year":"2005","unstructured":"Byrne K, Wolfe K: The Yeast Gene Order Browser: combining curated homology and syntenic context reveals gene fate in polyploid species. Genome Research. 2005, 15 (10): 1456-61. 10.1101\/gr.3672305.","journal-title":"Genome Research"},{"key":"5513_CR29","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1080\/10635150600697358","volume":"55","author":"S Hedtke","year":"2006","unstructured":"Hedtke S, Townsend T, Hillis D: Resolution of phylogenetic conflict in large data sets by increased taxon sampling. Systematic Biology. 2006, 55: 522-529. 10.1080\/10635150600697358.","journal-title":"Systematic Biology"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-13-S19-S4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1471-2105-13-S19-S4\/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-S4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T21:09:51Z","timestamp":1630530591000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-13-S19-S4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":29,"journal-issue":{"issue":"S19","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["5513"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-13-s19-s4","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":"S4"}}