{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:04Z","timestamp":1759638904091},"reference-count":31,"publisher":"Oxford University Press (OUP)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Ancestral gene order reconstruction problems, including the median problem, quartet construction, small phylogeny, guided genome halving and genome aliquoting, are NP hard. Available heuristics dedicated to each of these problems are computationally costly for even small instances.<\/jats:p>\n               <jats:p>Results: We present a data structure enabling rapid heuristic solution to all these ancestral genome reconstruction problems. A generic greedy algorithm with look-ahead based on an automatically generated priority system suffices for all the problems using this data structure. The efficiency of the algorithm is due to fast updating of the structure during run time and to the simplicity of the priority scheme. We illustrate with the first rapid algorithm for quartet construction and apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny.<\/jats:p>\n               <jats:p>Availability: \u00a0http:\/\/albuquerque.bioinformatics.uottawa.ca\/pathgroup\/Quartet.html<\/jats:p>\n               <jats:p>Contact: \u00a0chunfang313@gmail.com<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq255","type":"journal-article","created":{"date-parts":[[2010,5,19]],"date-time":"2010-05-19T00:47:01Z","timestamp":1274230021000},"page":"1587-1594","source":"Crossref","is-referenced-by-count":13,"title":["Pathgroups, a dynamic data structure for genome reconstruction problems"],"prefix":"10.1093","volume":"26","author":[{"given":"Chunfang","family":"Zheng","sequence":"first","affiliation":[{"name":"D\u00e9partement d'informatique et de recherche op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, Canada"}]}],"member":"286","published-online":{"date-parts":[[2010,5,18]]},"reference":[{"key":"2023012507562484000_B1","first-page":"69","article-title":"The ABCs of MGR with DCJ","volume":"4","author":"Adam","year":"2003","journal-title":"Evol. Bioinformatics"},{"key":"2023012507562484000_B2","first-page":"163","article-title":"A unifying view of genome rearrangements","volume-title":"Algorithms in Bioinformatics. Proceedings of WABI 2006","author":"Bergeron","year":"2006"},{"key":"2023012507562484000_B3","first-page":"26","article-title":"Genome-scale evolution: Reconstructing gene orders in the ancestral species","volume":"12","author":"Bourque","year":"2002","journal-title":"Genome Res."},{"key":"2023012507562484000_B4","doi-asserted-by":"crossref","first-page":"1456","DOI":"10.1101\/gr.3672305","article-title":"The Yeast Gene Order Browser: combining curated homology and syntenic context reveals gene fate in polyploid species","volume":"15","author":"Byrne","year":"2005","journal-title":"Genome Res."},{"key":"2023012507562484000_B5","first-page":"238","article-title":"On the practical solution of the reversal median problem","volume-title":"Algorithms in Bioinformatics. Proceedings of WABI 2001","author":"Caprara","year":"2001"},{"key":"2023012507562484000_B6","first-page":"277","article-title":"Algorithms for the extraction of synteny blocks from comparative maps","volume-title":"Algorithms in Bioinformatics. Proceedings of WABI 2007","author":"Choi","year":"2007"},{"key":"2023012507562484000_B7","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1137\/S0097539700377177","article-title":"The reconstruction of doubled genomes","volume":"32","author":"El-Mabrouk","year":"2003","journal-title":"SIAM J. Comput."},{"key":"2023012507562484000_B8","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/9780262062824.001.0001","volume-title":"Combinatorics of Genome Rearrangements.","author":"Fertin","year":"2009"},{"key":"2023012507562484000_B9","article-title":"Genome rearrangements analysis under parsimony other phylogenetic algorithms","year":"2004"},{"key":"2023012507562484000_B10","doi-asserted-by":"crossref","first-page":"e1000485","DOI":"10.1371\/journal.pgen.1000485","article-title":"Additions, losses, and rearrangements on the evolutionary route from a reconstructed ancestor to the modern Saccharomyces cerevisiae genome","volume":"5","author":"Gordon","year":"2009","journal-title":"PLoS Genet."},{"key":"2023012507562484000_B11","first-page":"304","article-title":"To cut \u2026 or not to cut: applications of comparative physical maps in molecular evolution","volume-title":"Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96)","author":"Hannenhalli","year":"1996"},{"key":"2023012507562484000_B12","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1080\/10635150600697358","article-title":"Resolution of phylogenetic conflict in large data sets by increased taxon sampling","volume":"55","author":"Hedtke","year":"2006","journal-title":"Syst. Biol."},{"key":"2023012507562484000_B13","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/11533719_9","article-title":"Quartet methods for phylogeny reconstruction from gene orders","volume-title":"Computing and Combinatorics (COCOON). Eleventh Annual Conference","author":"Liu","year":"2005"},{"key":"2023012507562484000_B14","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/978-3-642-01551-9_17","article-title":"Rearrangement phylogeny of genomes in contig form","volume-title":"Bioinformatics Research and Applications, 5th International Symposium (ISBRA)","author":"Mu\u00f1oz","year":"2009"},{"key":"2023012507562484000_B15","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1126\/science.1111387","article-title":"Dynamics of mammalian chromosome evolution inferred from multispecies comparative maps","volume":"309","author":"Murphy","year":"2005","journal-title":"Science"},{"key":"2023012507562484000_B16","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BFb0045092","article-title":"The median problem for breakpoints in comparative genomics","volume-title":"Computing and Combinatorics (COCOON). Third Annual Conference","author":"Sankoff","year":"1997"},{"key":"2023012507562484000_B17","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1089\/cmb.1998.5.555","article-title":"Multiple genome rearrangement and breakpoint phylogeny","volume":"5","author":"Sankoff","year":"1998","journal-title":"J. Comput. Biol."},{"key":"2023012507562484000_B18","first-page":"131","article-title":"Reversals of fortune","volume-title":"Comparative Genomics (RECOMB CG). Third Annual Workshop","author":"Sankoff","year":"2005"},{"key":"2023012507562484000_B19","doi-asserted-by":"crossref","first-page":"i433","DOI":"10.1093\/bioinformatics\/btm169","article-title":"Polyploids, genome halving and phylogeny","volume":"23","author":"Sankoff","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012507562484000_B20","first-page":"252","article-title":"Internal validation of ancestral gene order reconstruction in angiosperm phylogeny","volume-title":"Comparative Genomics (RECOMB CG). Sixth Annual Workshop","author":"Sankoff","year":"2008"},{"key":"2023012507562484000_B21","article-title":"Exact algorithms for the reversal median problem","volume-title":"Master's Thesis","author":"Siepel","year":"2001"},{"key":"2023012507562484000_B22","doi-asserted-by":"crossref","first-page":"336","DOI":"10.3732\/ajb.0800079","article-title":"Polyploidy and angiosperm diversification","volume":"96","author":"Soltis","year":"2009","journal-title":"Am. J. Bot."},{"key":"2023012507562484000_B23","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-540-45078-8_4","article-title":"Phylogenetic reconstruction from gene rearrangement data with unequal gene contents","volume-title":"Proceedings of the 8th Workshop on Algorithms and Data Structures (WADS)","author":"Tang","year":"2003"},{"key":"2023012507562484000_B24","first-page":"1","article-title":"Yeast ancestral genome reconstructions: the possibilities of computational methods","volume-title":"Comparative Genomics (RECOMB CG). Seventh Annual Workshop","author":"Tannier","year":"2009"},{"key":"2023012507562484000_B25","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1186\/1471-2105-10-120","article-title":"Multichromosomal median and halving problems under different genomic distances","volume":"10","author":"Tannier","year":"2009","journal-title":"BMC Bioinformatics"},{"issue":"Suppl. 1","key":"2023012507562484000_B26","first-page":"1","article-title":"Genome aliquoting with double cut and join","volume":"10","author":"Warren","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023012507562484000_B27","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","article-title":"Efficient sorting of genomic permutations by translocation, inversion, and block interchange","volume":"21","author":"Yancopoulos","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012507562484000_B28","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s10878-006-7120-2","article-title":"Genome rearrangements with partially ordered chromosomes","volume":"11","author":"Zheng","year":"2006","journal-title":"J. Comb. Optim."},{"key":"2023012507562484000_B29","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1177\/117693430600200028","article-title":"Genome halving with an outgroup","volume":"2","author":"Zheng","year":"2006","journal-title":"Evol. Bioinformatics"},{"key":"2023012507562484000_B30","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1109\/TCBB.2007.1075","article-title":"Removing noise and ambiguities from comparative maps in rearrangement analysis","volume":"4","author":"Zheng","year":"2007","journal-title":"Trans. Comput. Biol. Bioinf."},{"key":"2023012507562484000_B31","doi-asserted-by":"crossref","first-page":"i96","DOI":"10.1093\/bioinformatics\/btn146","article-title":"Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes","volume":"24","author":"Zheng","year":"2008","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/13\/1587\/48852764\/bioinformatics_26_13_1587.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/13\/1587\/48852764\/bioinformatics_26_13_1587.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T07:56:56Z","timestamp":1674633416000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/13\/1587\/201709"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,18]]},"references-count":31,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2010,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq255","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,7,1]]},"published":{"date-parts":[[2010,5,18]]}}}