{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T15:18:52Z","timestamp":1742397532397},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>The NCBI taxonomy provides one of the most powerful ways to navigate sequence data bases but currently users are forced to formulate queries according to a single taxonomic classification. Given that there is not universal agreement on the classification of organisms, providing a single classification places constraints on the questions biologists can ask. However, maintaining multiple classifications is burdensome in the face of a constantly growing NCBI classification.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>In this paper, we present a solution to the problem of generating modifications of the NCBI taxonomy, based on the computation of an edit script that summarises the differences between two classification trees. Our algorithms find the shortest possible edit script based on the identification of all shared subtrees, and only take time quasi linear in the size of the trees because classification trees have unique node labels.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusion<\/jats:title>\n                <jats:p>These algorithms have been recently implemented, and the software is freely available for download from <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/darwin.zoology.gla.ac.uk\/~rpage\/forest\/\">http:\/\/darwin.zoology.gla.ac.uk\/~rpage\/forest\/<\/jats:ext-link>.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/1471-2105-6-208","type":"journal-article","created":{"date-parts":[[2005,8,26]],"date-time":"2005-08-26T06:17:05Z","timestamp":1125037025000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["An edit script for taxonomic classifications"],"prefix":"10.1186","volume":"6","author":[{"given":"Roderic DM","family":"Page","sequence":"first","affiliation":[]},{"given":"Gabriel","family":"Valiente","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,8,25]]},"reference":[{"key":"533_CR1","unstructured":"NCBI Taxonomy[http:\/\/www.ncbi.nlm.nih.gov\/Taxonomy\/taxonomyhome.html]"},{"issue":"6632","key":"533_CR2","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1038\/387489a0","volume":"387","author":"A Aguinaldo","year":"1997","unstructured":"Aguinaldo A, Turbeville J, Linford L, Rivera M, Garey J, Raff R, Lake J: Evidence for a clade of nematodes, arthropods and other moulting animals. Nature 1997, 387(6632):489\u201393. 10.1038\/387489a0","journal-title":"Nature"},{"key":"533_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1101\/gr.1347404","volume":"14","author":"Y Wolf","year":"2004","unstructured":"Wolf Y, Rogozin I, Koonin E: Coelomata and not Ecdysozoa: evidence from genome-wide phylogenetic analysis. Genome Res 2004, 14: 29\u201336. 10.1101\/gr.1347404","journal-title":"Genome Res"},{"key":"533_CR4","doi-asserted-by":"publisher","first-page":"1175","DOI":"10.1093\/molbev\/msi102","volume":"22","author":"GK Philip","year":"2005","unstructured":"Philip GK, Creevey CJ, Mclnerney JO: The Opisthokonta and the Ecdysozoa may not be Clades: stronger support for the grouping of plant and animal than for animal and fungi and stronger support for the Coelomata than Ecdysozoa. Mol Biol Evol 2005, 22: 1175\u20131184. 10.1093\/molbev\/msi102","journal-title":"Mol Biol Evol"},{"key":"533_CR5","doi-asserted-by":"publisher","first-page":"1246","DOI":"10.1093\/molbev\/msi111","volume":"22","author":"H Philippe","year":"2005","unstructured":"Philippe H, Lartillot N, Brinkmann H: Multigene analyses of bilaterian animals corroborate the monophyly of Ecdysozoa, Lophotrochozoa and Protostomia. Mol Biol Evol 2005, 22: 1246\u20131253. 10.1093\/molbev\/msi111","journal-title":"Mol Biol Evol"},{"key":"533_CR6","volume-title":"SQL for Smarties: Advanced SQL Programming","author":"J Celko","year":"1999","unstructured":"Celko J: SQL for Smarties: Advanced SQL Programming. San Francisco: Morgan Kaufmann; 1999."},{"key":"533_CR7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(92)90136-J","volume":"42","author":"K Zhang","year":"1992","unstructured":"Zhang K, Statman R, Shasha D: On the editing distance between unordered labeled trees. Inform Process Lett 1992, 42: 133\u2013139. 10.1016\/0020-0190(92)90136-J","journal-title":"Inform Process Lett"},{"key":"533_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-45028-9_2","volume-title":"Proc. 4 th IAPR Int. Workshop Graph Based Representations in Pattern Recognition","author":"P Dickinson","year":"2003","unstructured":"Dickinson P, Bunke H, Dadej A, Kraetzl M: On graphs with unique node labels. In Proc. 4 th IAPR Int. Workshop Graph Based Representations in Pattern Recognition. Springer-Verlag; 2003:13\u201323."},{"key":"533_CR9","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1016\/S0167-8655(97)00060-3","volume":"18","author":"H Bunke","year":"1997","unstructured":"Bunke H: On a relation between graph edit distance and maximum common subgraph. Pattern Recogn Lett 1997, 18: 689\u2013694. 10.1016\/S0167-8655(97)00060-3","journal-title":"Pattern Recogn Lett"},{"key":"533_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04921-1","volume-title":"Algorithms on Trees and Graphs","author":"G Valiente","year":"2002","unstructured":"Valiente G: Algorithms on Trees and Graphs. Berlin: Springer-Verlag; 2002."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-208.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T17:49:30Z","timestamp":1706809770000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8,25]]},"references-count":10,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["533"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-208","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8,25]]},"assertion":[{"value":"21 June 2005","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"208"}}