{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T10:35:57Z","timestamp":1722767757233},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"18","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1490,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,9,15]]},"abstract":"Abstract<\/jats:title>\n Motivation: Most models of genome evolution integrating gene duplications, losses and chromosomal rearrangements are computationally intract able, even when comparing only two genomes. This prevents large-scale studies that consider different types of genome structural variations.<\/jats:p>\n Results: We define an \u2018adjacency phylogenetic tree\u2019 that describes the evolution of an adjacency, a neighborhood relation between two genes, by speciation, duplication or loss of one or both genes, and rearrangement. We describe an algorithm that, given a species tree and a set of gene trees where the leaves are connected by adjacencies, computes an adjacency forest that minimizes the number of gains and breakages of adjacencies (caused by rearrangements) and runs in polynomial time. We use this algorithm to reconstruct contiguous regions of mammalian and plant ancestral genomes in a few minutes for a dozen species and several thousand genes. We show that this method yields reduced conflict between ancestral adjacencies. We detect duplications involving several genes and compare the different modes of evolution between phyla and among lineages.<\/jats:p>\n Availability: C++ implementation using BIO++ package, available upon request to S\u00e8verine B\u00e9rard.<\/jats:p>\n Contact: \u00a0Severine.Berard@cirad.fr or Eric.Tannier@inria.fr<\/jats:p>\n Supplementary information: \u00a0Supplementary material is available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts374","type":"journal-article","created":{"date-parts":[[2012,9,7]],"date-time":"2012-09-07T20:35:22Z","timestamp":1347050122000},"page":"i382-i388","source":"Crossref","is-referenced-by-count":33,"title":["Evolution of gene neighborhoods within reconciled phylogenies"],"prefix":"10.1093","volume":"28","author":[{"given":"S\u00e8verine","family":"B\u00e9rard","sequence":"first","affiliation":[{"name":"1 Univ Montpellier2, UMR AMAP, Montpellier F-34000"},{"name":"2 LIRMM, CNRS, Univ Montpellier2, Montpellier F-34392, France"}]},{"given":"Coralie","family":"Gallien","sequence":"additional","affiliation":[{"name":"1 Univ Montpellier2, UMR AMAP, Montpellier F-34000"}]},{"given":"Bastien","family":"Boussau","sequence":"additional","affiliation":[{"name":"3 LBBE, UMR CNRS 5558, Universit\u00e9 de Lyon 1, Villeurbanne F-69622, France"},{"name":"4 Department of Integrative Biology, UC Berkeley 4163A Valley Life Sciences Bldg Berkeley, CA 94720-3140, USA"}]},{"given":"Gergely J.","family":"Sz\u00f6ll\u0151si","sequence":"additional","affiliation":[{"name":"3 LBBE, UMR CNRS 5558, Universit\u00e9 de Lyon 1, Villeurbanne F-69622, France"}]},{"given":"Vincent","family":"Daubin","sequence":"additional","affiliation":[{"name":"3 LBBE, UMR CNRS 5558, Universit\u00e9 de Lyon 1, Villeurbanne F-69622, France"}]},{"given":"Eric","family":"Tannier","sequence":"additional","affiliation":[{"name":"3 LBBE, UMR CNRS 5558, Universit\u00e9 de Lyon 1, Villeurbanne F-69622, France"},{"name":"5 INRIA Rh\u00f4ne-Alpes, Montbonnot F-38322, France"}]}],"member":"286","published-online":{"date-parts":[[2012,9,3]]},"reference":[{"key":"2023012513030829600_B1","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1101\/gr.082784.108","article-title":"Breakpoint graphs and ancestral genome reconstructions","volume":"19","author":"Alekseyev","year":"2009","journal-title":"Genome Res"},{"key":"2023012513030829600_B2","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/978-3-642-15294-8_7","article-title":"Reconstruction of ancestral genome subject to whole genome duplication, speciation, rearrangement and loss","volume-title":"Proceedings of WABI\u201810, Algorithms in Bioinformatics","author":"Bertrand","year":"2010"},{"key":"2023012513030829600_B3","article-title":"Genome-scale coestimation of species and gene trees, in revision","author":"Boussau","year":"2012"},{"key":"2023012513030829600_B4","doi-asserted-by":"crossref","first-page":"e1000234","DOI":"10.1371\/journal.pcbi.1000234","article-title":"A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes","volume":"4","author":"Chauve","year":"2008","journal-title":"PLoS Comput. Biol"},{"key":"2023012513030829600_B5","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1089\/cmb.2010.0092","article-title":"Yeast ancestral genome reconstructions: the possibilities of computational methods II","volume":"17","author":"Chauve","year":"2010","journal-title":"J. Comput. Biol"},{"key":"2023012513030829600_B6","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1093\/bib\/bbr045","article-title":"Models, algorithms and programs for phylogeny reconciliation","volume":"12","author":"Doyon","year":"2011","journal-title":"Brief. Bioinform."},{"key":"2023012513030829600_B7","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1186\/1471-2105-7-188","article-title":"Bio++: a set of c++ libraries for sequence analysis, phylogenetics, molecular evolution and population genetics","volume":"7","author":"Dutheil","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012513030829600_B8","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1186\/1471-2105-10-393","article-title":"Phylogeny-guided interaction mapping in seven eukaryotes","volume":"10","author":"Dutkowski","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023012513030829600_B9","doi-asserted-by":"crossref","first-page":"1318","DOI":"10.1109\/TCBB.2011.34","article-title":"SCJ: a breakpoint-like distance that simplifies several rearrangement problems","volume":"8","author":"Feijao","year":"2011","journal-title":"IEEE\/ACM Trans. Comp. Biol. Bioinf"},{"key":"2023012513030829600_B10","doi-asserted-by":"crossref","first-page":"406","DOI":"10.2307\/2412116","article-title":"Toward defining the course of evolution: minimum change for a specified tree topology","volume":"20","author":"Fitch","year":"1971","journal-title":"Sys. Zool."},{"key":"2023012513030829600_B11","doi-asserted-by":"crossref","first-page":"132","DOI":"10.2307\/2412519","article-title":"Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences","volume":"28","author":"Goodman","year":"1979","journal-title":"Syst. Zool."},{"key":"2023012513030829600_B12","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1093\/molbev\/msp271","article-title":"Inferring the evolutionary history of gene clusters from phylogenetic and gene order data","volume":"27","author":"Lajoie","year":"2010","journal-title":"Mol. Biol. Evol."},{"key":"2023012513030829600_B13","doi-asserted-by":"crossref","first-page":"1557","DOI":"10.1101\/gr.5383506","article-title":"Reconstructing contiguous regions of an ancestral genome","volume":"16","author":"Ma","year":"2006","journal-title":"Genome Res."},{"key":"2023012513030829600_B14","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1089\/cmb.2008.0069","article-title":"Dupcar: reconstructing contiguous ancestral regions with duplications","volume":"15","author":"Ma","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023012513030829600_B15","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1093\/bioinformatics\/btq079","article-title":"Genomicus: a database and a browser to study gene synteny in modern and ancestral genomes","volume":"26","author":"Muffato","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012513030829600_B16","doi-asserted-by":"crossref","first-page":"2664","DOI":"10.1093\/bioinformatics\/btr461","article-title":"Reconstructing the architecture of the ancestral amniote genome","volume":"27","author":"Ouangraoua","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012513030829600_B17","first-page":"237249","article-title":"Parsimonious reconstruction of network evolution","volume":"LNBI 6833","author":"Patro","year":"2011","journal-title":"Proceedings of WABI\u201811"},{"key":"2023012513030829600_B18","doi-asserted-by":"crossref","first-page":"20449","DOI":"10.1073\/pnas.0706339104","article-title":"Reconstruction of ancestral protein interaction networks for the bzip transcription factors","volume":"104","author":"Pinney","year":"2007","journal-title":"Proc. Natl. Aca. Sa. USA"},{"key":"2023012513030829600_B19","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1101\/gr.123901.111","article-title":"Unified modeling of gene duplication, loss, and coalescence using a locus tree","volume":"22","author":"Rasmussen","year":"2012","journal-title":"Genome Res."},{"key":"2023012513030829600_B20","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1186\/1748-7188-6-17","article-title":"A new, fast algorithm for detecting protein coevolution using maximum compatible cliques","volume":"6","author":"Rodionov","year":"2011","journal-title":"Algorithms Mol. Biol."},{"key":"2023012513030829600_B21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/0128004","article-title":"Minimal mutation trees of sequences","volume":"28","author":"Sankoff","year":"1975","journal-title":"SIAM J. Appl. Math."},{"key":"2023012513030829600_B22","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/978-94-011-4309-7_46","article-title":"Duplication, rearrangement and reconciliation","volume-title":"Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map alignment and the Evolution of Gene Families, Vol. 1 of Computational Biology","author":"Sankoff","year":"2000"},{"key":"2023012513030829600_B23","first-page":"137","article-title":"Improving genome rearrangement phylogeny using sequence-style parsimony","volume-title":"Proceedings 5th IEEE Conference on Bioinformatics and Bioengineering (BIBE 2005)","author":"Tang","year":"2005"},{"key":"2023012513030829600_B24","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1101\/gr.096115.109","article-title":"Reconstructing ancestral gene content by coevolution","volume":"20","author":"Tuller","year":"2010","journal-title":"Genome Res."},{"key":"2023012513030829600_B25","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1101\/gr.073585.107","article-title":"Ensemblcompara genetrees: Complete, duplication-aware phylogenetic trees in vertebrates","volume":"19","author":"Vilella","year":"2009","journal-title":"Genome Res."},{"issue":"Suppl. 1","key":"2023012513030829600_B26","doi-asserted-by":"crossref","first-page":"S4","DOI":"10.1186\/1471-2105-12-S1-S4","article-title":"On the pathgroups approach to rapid small phylogeny","volume":"12","author":"Zheng","year":"2011","journal-title":"BMC Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/18\/i382\/48884063\/bioinformatics_28_18_i382.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/18\/i382\/48884063\/bioinformatics_28_18_i382.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T18:53:06Z","timestamp":1674672786000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/18\/i382\/244519"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,3]]},"references-count":26,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2012,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts374","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,9,15]]},"published":{"date-parts":[[2012,9,3]]}}}