{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:49:26Z","timestamp":1772372966062,"version":"3.50.1"},"reference-count":17,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Algorithms for phylogenetic tree reconstruction based on gene order data typically repeatedly solve instances of the reversal median problem (RMP) which is to find for three given gene orders a fourth gene order (called median) with a minimal sum of reversal distances. All existing algorithms of this type consider only one median for each RMP instance even when a large number of medians exist. A careful selection of one of the medians might lead to better phylogenetic trees.<\/jats:p><jats:p>Results: We propose a heuristic algorithm amGRP for solving the multiple genome rearrangement problem (MGRP) by repeatedly solving instances of the RMP taking all medians into account. Algorithm amGRP uses a branch-and-bound method that branches over medians from a selected subset of all medians for each RMP instance. Different heuristics for selecting the subsets have been investigated. To show that the medians for RMP vary strongly with respect to different properties that are likely to be relevant for phylogenetic tree reconstruction, the set of all medians has been investigated for artificial datasets and mitochondrial DNA (mtDNA) gene orders. Phylogenetic trees have been computed for a large set of randomly generated gene orders and two sets of mtDNA gene order data for different animal taxa with amGRP and with two standard approaches for solving the MGRP (GRAPPA-DCM and MGR). The results show that amGRP outperforms both other methods with respect to solution quality and computation time on the test data.<\/jats:p><jats:p>Availability: The source code of amGRP, additional results and the test instances used in this paper are freely available from the authors.<\/jats:p><jats:p>Contact: \u00a0merkle@informatik.uni-leipzig.de<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl300","type":"journal-article","created":{"date-parts":[[2007,1,19]],"date-time":"2007-01-19T18:51:12Z","timestamp":1169232672000},"page":"e129-e135","source":"Crossref","is-referenced-by-count":14,"title":["Using median sets for inferring phylogenetic trees"],"prefix":"10.1093","volume":"23","author":[{"given":"Matthias","family":"Bernt","sequence":"first","affiliation":[{"name":"Parallel Computing and Complex Systems Group, Department of Computer Science, University of Leipzig \u00a0 Augustusplatz 10\/11, 04109 Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Merkle","sequence":"additional","affiliation":[{"name":"Parallel Computing and Complex Systems Group, Department of Computer Science, University of Leipzig \u00a0 Augustusplatz 10\/11, 04109 Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Middendorf","sequence":"additional","affiliation":[{"name":"Parallel Computing and Complex Systems Group, Department of Computer Science, University of Leipzig \u00a0 Augustusplatz 10\/11, 04109 Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2007,1,15]]},"reference":[{"key":"2023041107140374100_","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1089\/106652701753216503","article-title":"A linear-time algorithm for computing inversion distances between signed permutations with an experimental study","volume":"8","author":"Bader","year":"2001","journal-title":"J. Comput. Biol."},{"key":"2023041107140374100_","article-title":"Genome rearrangement based on reversals that preserve conserved intervals","author":"Bernt","year":"2005","journal-title":"IEEE\/ACM Trans. on Comp. Biol. and Bioinformatics"},{"key":"2023041107140374100_","first-page":"68","article-title":"On the similarity of sets of permutations and its applications to genome comparison","author":"Bergeron","year":"2003"},{"key":"2023041107140374100_","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/PL00006542","article-title":"Gene order breakpoint evidence in animal mitochondrial phylogeny","volume":"49","author":"Blanchette","year":"1999","journal-title":"J. Mol. Evol."},{"key":"2023041107140374100_","article-title":"Mitochondrial database","author":"Boore","year":"2005"},{"key":"2023041107140374100_","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":"2023041107140374100_","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1287\/ijoc.15.1.93.15155","article-title":"The reversal median problem","volume":"15","author":"Caprara","year":"2003","journal-title":"INFORMS J. Comput."},{"key":"2023041107140374100_","article-title":"Inferring Phylogenies","author":"Felsenstein","year":"2004"},{"key":"2023041107140374100_","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1016\/j.jtbi.2005.10.010","article-title":"Alignments of mitochondrial genome arrangements: applications to metazoan phylogeny","volume":"240","author":"Fritzsch","year":"2005","journal-title":"J. Theor. Biol."},{"key":"2023041107140374100_","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1089\/106652799318337","article-title":"Disk-covering, a fast converging method for phylogenetic tree reconstruction","volume":"6","author":"Huson","year":"1999","journal-title":"J. Comput. Biol."},{"key":"2023041107140374100_","first-page":"321","article-title":"Reconstructing phylogenies from gene-content and gene-order data","volume-title":"Math. Evol. Phylog.","author":"Moret","year":"2004"},{"key":"2023041107140374100_","first-page":"189","article-title":"Finding an optimal inversion median: experimental results","author":"Moret","year":"2001"},{"key":"2023041107140374100_","first-page":"165","article-title":"New approaches for reconstructing phylogenies from gene order data","volume-title":"Proc. Int. Conf. Intell. Syst. Mol. Biol. (ISMB-2001)","author":"Moret","year":"2001"},{"key":"2023041107140374100_","first-page":"121","article-title":"Edit distance for genome comparison based on non-local operations","author":"Sankoff","year":"1992"},{"key":"2023041107140374100_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0129054196000026","article-title":"Steiner points in the space of genome rearrangements","volume":"8","author":"Sankoff","year":"1996","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2023041107140374100_","doi-asserted-by":"crossref","first-page":"858","DOI":"10.1093\/oxfordjournals.molbev.a003867","article-title":"Numerous Gene Rearrangements in the Mitochondrial Genome of the Wallaby Louse, Heterodoxus macropus (Phthiraptera)","volume":"18","author":"Shao","year":"2001","journal-title":"Mol. Biol. Evol."},{"key":"2023041107140374100_","first-page":"305","article-title":"Scaling up accurate phylogenetic reconstruction from gene-order data","volume":"19","author":"Tang","year":"2003","journal-title":"Proc. Int. Conf. Intell. Syst. Mol. Biol. (ISMB-2003)"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e129\/49820350\/bioinformatics_23_2_e129.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e129\/49820350\/bioinformatics_23_2_e129.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T13:03:58Z","timestamp":1683723838000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/2\/e129\/202015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,15]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl300","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,1,15]]},"published":{"date-parts":[[2007,1,15]]}}}