{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:09:10Z","timestamp":1783530550914,"version":"3.55.0"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Subtree prune and regraft (SPR) is one kind of tree rearrangements that has seen applications in solving several computational biology problems. The minimum number of rooted SPR (rSPR) operations needed to transform one rooted binary tree to another is called the rSPR distance between the two trees. Computing the rSPR distance has been actively studied in recent years. Currently, there is a lack of practical software tools for computing the rSPR distance for relatively large trees with large rSPR distance.<\/jats:p><jats:p>Results: In this article, we present a simple and practical method that computes the exact rSPR distance with integer linear programming. By applying this new method on several simulated and real biological datasets, we show that our new method outperforms existing software tools in term of accuracy and ef.ciency. Our experimental results indicate that our method can compute the exact rSPR distance for many large trees with large rSPR distance.<\/jats:p><jats:p>Availability: A software tool, SPRDist, is available for download from the web page: http:\/\/www.engr.uconn.edu\/~ywu.<\/jats:p><jats:p>Contact: \u00a0ywu@engr.uconn.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn606","type":"journal-article","created":{"date-parts":[[2008,11,20]],"date-time":"2008-11-20T01:14:11Z","timestamp":1227143651000},"page":"190-196","source":"Crossref","is-referenced-by-count":42,"title":["A practical method for exact computation of subtree prune and regraft distance"],"prefix":"10.1093","volume":"25","author":[{"given":"Yufeng","family":"Wu","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2008,11,19]]},"reference":[{"key":"2023013110002141700_B1","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s00285-005-0315-9","article-title":"Bounding the number of hybridisation events for a consistent evolutionary history","volume":"51","author":"Baroni","year":"2005","journal-title":"J. Math. Biol"},{"key":"2023013110002141700_B2","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1186\/1471-2148-6-15","article-title":"Phylogenetic identification of lateral genetic transfer events","volume":"6","author":"Beiko","year":"2006","journal-title":"BMC Evol. Biol"},{"key":"2023013110002141700_B3","doi-asserted-by":"crossref","first-page":"1419","DOI":"10.1089\/cmb.2006.13.1419","article-title":"Approximating subtree distances between phylogenies","volume":"13","author":"Bonet","year":"2006","journal-title":"J. Comp. Bio"},{"key":"2023013110002141700_B4","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s00026-004-0229-z","article-title":"On the computational complexity of the rooted subtree prune and regraft distance","volume":"8","author":"Bordewich","year":"2004","journal-title":"Ann. Combinatorics"},{"key":"2023013110002141700_B5","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1177\/117693430700300017","article-title":"A reduction algorithm for computing the hybridization number of two trees","volume":"3","author":"Bordewich","year":"2007","journal-title":"Evol. Bioinform"},{"key":"2023013110002141700_B6","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1016\/j.jda.2007.10.002","article-title":"A 3-approximation algorithm for the subtree distance between phylogenies","volume":"6","author":"Bordewich","year":"2008","journal-title":"J. Discrete Algorithm"},{"key":"2023013110002141700_B7","volume-title":"Inferring Phylogenies.","author":"Felsenstein","year":"2004"},{"key":"2023013110002141700_B8","doi-asserted-by":"crossref","first-page":"373","DOI":"10.2307\/3298585","article-title":"Phylogeny and subfamilial classification of the grasses (poaceae)","volume":"88","author":"Grass Phylogeny Working Group","year":"2001","journal-title":"Ann. Mo. Bot. Gard"},{"key":"2023013110002141700_B9","first-page":"144","article-title":"Haplotype inference by pure parsimony","volume-title":"14th Annual Symposium on Combinatorial Pattern Matching (CPM'03), LNCS, vol. 2676","author":"Gusfield","year":"2003"},{"key":"2023013110002141700_B10","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/369133.369188","article-title":"Efficient algorithms for lateral gene transfer problems","volume-title":"Proceedings of fifth annual conference on Research in Computational Molecular Biology","author":"Hallett","year":"2001"},{"key":"2023013110002141700_B11","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0025-5564(90)90123-G","article-title":"Reconstructing evolution of sequences subject to recombination using parsimony","volume":"98","author":"Hein","year":"1990","journal-title":"Math. Biosci"},{"key":"2023013110002141700_B12","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/BF00182187","article-title":"A heuristic method to reconstruct the history of sequences subject to recombination","volume":"36","author":"Hein","year":"1993","journal-title":"J. Mol. Evol"},{"key":"2023013110002141700_B13","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0166-218X(96)00062-5","article-title":"On the complexity of comparing evolutionary trees","volume":"71","author":"Hein","year":"1996","journal-title":"Discrete Appl. Math"},{"key":"2023013110002141700_B14","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1186\/1471-2148-5-27","article-title":"Deduction of probable events of lateral gene transfer through comparison of phylogenetic trees by recursive consolidation and rearrangement","volume":"5","author":"MacLeod","year":"2005","journal-title":"BMC Evol. Biol"},{"key":"2023013110002141700_B15","first-page":"159","article-title":"Some approximation results for the maximum agreement forest problem","volume-title":"LNCS 2129.","author":"Rodrigues","year":"2001"},{"key":"2023013110002141700_B16","article-title":"Phylogenetic trees from large datasets","author":"Schmidt","year":"2003"},{"key":"2023013110002141700_B17","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1093\/oso\/9780199208227.003.0010","article-title":"Hybridization networks","volume-title":"Reconstructing Evolution: New Mathematical and Computational Advances.","author":"Semple","year":"2007"},{"key":"2023013110002141700_B18","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics.","author":"Semple","year":"2003"},{"key":"2023013110002141700_B19","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1089\/cmb.2005.12.147","article-title":"Constructing minimal ancestral recombination graphs","volume":"12","author":"Song","year":"2005","journal-title":"J. Comp. Bio"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/2\/190\/48982724\/bioinformatics_25_2_190.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/2\/190\/48982724\/bioinformatics_25_2_190.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T18:31:26Z","timestamp":1709404286000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/2\/190\/219359"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11,19]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn606","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,1,15]]},"published":{"date-parts":[[2008,11,19]]}}}