{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T06:32:53Z","timestamp":1789972373842,"version":"4.0.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,27]],"date-time":"2019-07-27T00:00:00Z","timestamp":1564185600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2019,7,27]],"date-time":"2019-07-27T00:00:00Z","timestamp":1564185600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1619081"],"award-info":[{"award-number":["CCF-1619081"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1525024"],"award-info":[{"award-number":["CCF-1525024"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1633215"],"award-info":[{"award-number":["IIS-1633215"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["GM108348"],"award-info":[{"award-number":["GM108348"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Vanier CGS"],"award-info":[{"award-number":["Vanier CGS"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1186\/s13015-019-0152-9","type":"journal-article","created":{"date-parts":[[2019,7,27]],"date-time":"2019-07-27T12:02:34Z","timestamp":1564228954000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["A multi-labeled tree dissimilarity measure for comparing \u201cclonal trees\u201d of tumor progression"],"prefix":"10.1186","volume":"14","author":[{"given":"Nikolai","family":"Karpov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4962-3925","authenticated-orcid":false,"given":"Salem","family":"Malikic","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Md. Khaledur","family":"Rahman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Cenk","family":"Sahinalp","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,7,27]]},"reference":[{"issue":"4260","key":"152_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1126\/science.959840","volume":"194","author":"PC Nowell","year":"1976","unstructured":"Nowell PC. The clonal evolution of tumor cell populations. Science. 1976;194(4260):23\u20138.","journal-title":"Science"},{"issue":"2","key":"152_CR2","first-page":"127","volume":"1867","author":"J Kuipers","year":"2017","unstructured":"Kuipers J, et al. Advances in understanding tumour evolution through single-cell sequencing. Biochim Biophys Acta. 2017;1867(2):127\u201338.","journal-title":"Biochim Biophys Acta"},{"issue":"1","key":"152_CR3","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1186\/s13059-017-1311-2","volume":"18","author":"H Zafar","year":"2017","unstructured":"Zafar H, et al. Sifit: inferring tumor trees from single-cell sequencing data under finite-sites models. Genome Biol. 2017;18(1):178.","journal-title":"Genome Biol"},{"issue":"1","key":"152_CR4","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1186\/1471-2105-15-27","volume":"15","author":"KI Kim","year":"2014","unstructured":"Kim KI, Simon R. Using single cell sequencing data to model the evolutionary history of a tumor. BMC Bioinform. 2014;15(1):27.","journal-title":"BMC Bioinform"},{"issue":"1","key":"152_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1186\/s13059-016-0936-x","volume":"17","author":"K Jahn","year":"2016","unstructured":"Jahn K, et al. Tree inference for single-cell data. Genome Biol. 2016;17(1):86.","journal-title":"Genome Biol"},{"issue":"17","key":"152_CR6","doi-asserted-by":"publisher","first-page":"165165","DOI":"10.1093\/nar\/gkt641","volume":"41","author":"F Strino","year":"2013","unstructured":"Strino F, et al. Trap: a tree approach for fingerprinting subclonal tumor composition. Nucleic Acids Res. 2013;41(17):165165.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"152_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1186\/1471-2105-15-35","volume":"15","author":"W Jiao","year":"2014","unstructured":"Jiao W, et al. Inferring clonal evolution of tumors from single nucleotide somatic mutations. BMC Bioinform. 2014;15(1):35.","journal-title":"BMC Bioinform"},{"issue":"12","key":"152_CR8","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1093\/bioinformatics\/btu284","volume":"30","author":"I Hajirasouliha","year":"2014","unstructured":"Hajirasouliha I, et al. A combinatorial approach for analyzing intra-tumor heterogeneity from high-throughput sequencing data. Bioinformatics. 2014;30(12):78\u201386.","journal-title":"Bioinformatics"},{"issue":"1","key":"152_CR9","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1186\/s13059-015-0602-8","volume":"16","author":"AG Deshwar","year":"2015","unstructured":"Deshwar AG, et al. Phylowgs: reconstructing subclonal composition and evolution from whole-genome sequencing of tumors. Genome Biol. 2015;16(1):35.","journal-title":"Genome Biol"},{"issue":"12","key":"152_CR10","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1093\/bioinformatics\/btv261","volume":"31","author":"M El-Kebir","year":"2015","unstructured":"El-Kebir M, et al. Reconstruction of clonal trees and tumor composition from multi-sample sequencing data. Bioinformatics. 2015;31(12):62\u201370.","journal-title":"Bioinformatics"},{"issue":"1","key":"152_CR11","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1186\/s13059-015-0647-8","volume":"16","author":"V Popic","year":"2015","unstructured":"Popic V, et al. Fast and scalable inference of multi-sample cancer lineages. Genome Biol. 2015;16(1):91.","journal-title":"Genome Biol"},{"issue":"9","key":"152_CR12","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1093\/bioinformatics\/btv003","volume":"31","author":"S Malikic","year":"2015","unstructured":"Malikic S, et al. Clonality inference in multiple tumor samples using phylogeny. Bioinformatics. 2015;31(9):1349\u201356.","journal-title":"Bioinformatics"},{"issue":"1","key":"152_CR13","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1186\/s13059-016-0929-9","volume":"17","author":"EM Ross","year":"2016","unstructured":"Ross EM, Markowetz F. Onconem: inferring tumor evolution from single-cell sequencing data. Genome Biol. 2016;17(1):69.","journal-title":"Genome Biol"},{"issue":"1","key":"152_CR14","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.cels.2016.07.004","volume":"3","author":"M El-Kebir","year":"2016","unstructured":"El-Kebir M, et al. Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures. Cell Syst. 2016;3(1):43\u201353.","journal-title":"Cell Syst"},{"issue":"6","key":"152_CR15","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1089\/cmb.2016.0148","volume":"24","author":"N Donmez","year":"2017","unstructured":"Donmez N, et al. Clonality inference from single tumor samples using low-coverage sequence data. J Comput Biol. 2017;24(6):515\u201323. \n                              https:\/\/doi.org\/10.1089\/cmb.2016.0148\n                              \n                           .","journal-title":"J Comput Biol"},{"issue":"1","key":"152_CR16","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner RA, Fischer MJ. The string-to-string correction problem. J ACM. 1974;21(1):168\u201373. \n                              https:\/\/doi.org\/10.1145\/321796.321811\n                              \n                           .","journal-title":"J ACM"},{"key":"152_CR17","doi-asserted-by":"publisher","unstructured":"Backurs A, Indyk P. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In: Proceedings of STOC. 2015. pp. 51\u20138. \n                              https:\/\/doi.org\/10.1145\/2746539.2746612\n                              \n                           .","DOI":"10.1145\/2746539.2746612"},{"issue":"1","key":"152_CR18","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2003.05.005","volume":"321","author":"S Muthukrishnan","year":"2004","unstructured":"Muthukrishnan S, Sahinalp SC. An efficient algorithm for sequence comparison with block reversals. Theor Comput Sci. 2004;321(1):95\u2013101. \n                              https:\/\/doi.org\/10.1016\/j.tcs.2003.05.005\n                              \n                           .","journal-title":"Theor Comput Sci"},{"issue":"1","key":"152_CR19","doi-asserted-by":"publisher","first-page":"40","DOI":"10.3390\/a4010040","volume":"4","author":"D Shapira","year":"2011","unstructured":"Shapira D, Storer JA. Edit distance with block deletions. Algorithms. 2011;4(1):40\u201360. \n                              https:\/\/doi.org\/10.3390\/a4010040\n                              \n                           .","journal-title":"Algorithms"},{"issue":"6","key":"152_CR20","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K Zhang","year":"1989","unstructured":"Zhang K, Shasha DE. Simple fast algorithms for the editing distance between trees and related problems. SIAM J Comput. 1989;18(6):1245\u201362. \n                              https:\/\/doi.org\/10.1137\/0218082\n                              \n                           .","journal-title":"SIAM J Comput"},{"issue":"1","key":"152_CR21","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","volume":"143","author":"T Jiang","year":"1995","unstructured":"Jiang T, et al. Alignment of trees\u2014an alternative to tree edit. Theor Comput Sci. 1995;143(1):137\u201348. \n                              https:\/\/doi.org\/10.1016\/0304-3975(95)80029-9\n                              \n                           .","journal-title":"Theor Comput Sci"},{"issue":"3","key":"152_CR22","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/322139.322143","volume":"26","author":"T Kuo-Chung","year":"1979","unstructured":"Kuo-Chung T. The tree-to-tree correction problem. J ACM. 1979;26(3):422\u201333. \n                              https:\/\/doi.org\/10.1145\/322139.322143\n                              \n                           .","journal-title":"J ACM"},{"key":"152_CR23","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-68530-8_8","volume-title":"Algorithms \u2014 ESA\u2019 98","author":"Philip N. Klein","year":"1998","unstructured":"Klein PN. Computing the edit-distance between unrooted ordered trees. In: Algorithms\u2014ESA \u201998, 6th annual European symposium, Venice, Italy, August 24\u201326, 1998, Proceedings. pp. 91\u2013102. \n                              https:\/\/doi.org\/10.1007\/3-540-68530-8_8\n                              \n                           ."},{"issue":"2","key":"152_CR24","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1006\/jagm.2001.1170","volume":"40","author":"W Chen","year":"2001","unstructured":"Chen W. New algorithm for ordered tree-to-tree correction problem. J Algorithms. 2001;40(2):135\u201358. \n                              https:\/\/doi.org\/10.1006\/jagm.2001.1170\n                              \n                           .","journal-title":"J Algorithms"},{"issue":"3","key":"152_CR25","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/0031-3203(94)00109-Y","volume":"28","author":"K Zhang","year":"1995","unstructured":"Zhang K. Algorithms for the constrained editing distance between ordered labeled trees and related problems. Pattern Recogn. 1995;28(3):463\u201374. \n                              https:\/\/doi.org\/10.1016\/0031-3203(94)00109-Y\n                              \n                           .","journal-title":"Pattern Recogn"},{"issue":"4","key":"152_CR26","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1016\/0196-6774(90)90011-3","volume":"11","author":"D Shasha","year":"1990","unstructured":"Shasha D, Zhang K. Fast algorithms for the unit cost editing distance between trees. J Algorithms. 1990;11(4):581\u2013621. \n                              https:\/\/doi.org\/10.1016\/0196-6774(90)90011-3\n                              \n                           .","journal-title":"J Algorithms"},{"issue":"6","key":"152_CR27","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/0020-0190(77)90064-3","volume":"6","author":"SM Selkow","year":"1977","unstructured":"Selkow SM. The tree-to-tree editing problem. Inf Process Lett. 1977;6(6):184\u20136. \n                              https:\/\/doi.org\/10.1016\/0020-0190(77)90064-3\n                              \n                           .","journal-title":"Inf Process Lett"},{"issue":"1\u20132","key":"152_CR28","first-page":"105","volume":"56","author":"J Jansson","year":"2003","unstructured":"Jansson J, Lingas A. A fast algorithm for optimal alignment between similar ordered trees. Fundam Inform. 2003;56(1\u20132):105\u201320.","journal-title":"Fundam Inform"},{"issue":"2","key":"152_CR29","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1006\/jagm.1997.0899","volume":"26","author":"W Chen","year":"1998","unstructured":"Chen W. More efficient algorithm for ordered tree inclusion. J Algorithms. 1998;26(2):370\u201385. \n                              https:\/\/doi.org\/10.1006\/jagm.1997.0899\n                              \n                           .","journal-title":"J Algorithms"},{"issue":"2","key":"152_CR30","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539791218202","volume":"24","author":"P Kilpel\u00e4inen","year":"1995","unstructured":"Kilpel\u00e4inen P, Mannila H. Ordered and unordered tree inclusion. SIAM J Comput. 1995;24(2):340\u201356. \n                              https:\/\/doi.org\/10.1137\/S0097539791218202\n                              \n                           .","journal-title":"SIAM J Comput"},{"issue":"1\u20133","key":"152_CR31","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek J, Thomas R. On the complexity of finding iso- and other morphisms for partial k-trees. Discret Math. 1992;108(1\u20133):343\u201364. \n                              https:\/\/doi.org\/10.1016\/0012-365X(92)90687-B\n                              \n                           .","journal-title":"Discret Math"},{"issue":"5","key":"152_CR32","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(94)90062-0","volume":"49","author":"K Zhang","year":"1994","unstructured":"Zhang K, Jiang T. Some MAX SNP-hard results concerning unordered labeled trees. Inf Process Lett. 1994;49(5):249\u201354. \n                              https:\/\/doi.org\/10.1016\/0020-0190(94)90062-0\n                              \n                           .","journal-title":"Inf Process Lett"},{"issue":"1\u20133","key":"152_CR33","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P Bille","year":"2005","unstructured":"Bille P. A survey on tree edit distance and related problems. Theor Comput Sci. 2005;337(1\u20133):217\u201339. \n                              https:\/\/doi.org\/10.1016\/j.tcs.2004.12.030\n                              \n                           .","journal-title":"Theor Comput Sci"},{"issue":"3","key":"152_CR34","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman ML, Tarjan RE. Fibonacci heaps and their uses in improved network optimization algorithms. J ACM. 1987;34(3):596\u2013615. \n                              https:\/\/doi.org\/10.1145\/28869.28874\n                              \n                           .","journal-title":"J ACM"},{"key":"152_CR35","doi-asserted-by":"crossref","unstructured":"Malikic S, et al. Integrative inference of subclonal tumour evolution from single-cell and bulk sequencing data. In: Proceedings of RECOMB. 2018.","DOI":"10.1101\/234914"},{"key":"152_CR36","doi-asserted-by":"publisher","unstructured":"Malikic S, et\u00a0al. Phiscs\u2014a combinatorial approach for sub-perfect tumor phylogeny reconstruction via integrative use of single cell and bulk sequencing data. 2018. \n                              bioRxiv:10.1101\/376996\n                              \n                           . \n                              https:\/\/doi.org\/10.1101\/376996\n                              \n                           . \n                              https:\/\/www.biorxiv.org\/content\/early\/2018\/07\/25\/376996.full.pdf\n                              \n                           .","DOI":"10.1101\/376996"},{"issue":"7513","key":"152_CR37","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1038\/nature13600","volume":"512","author":"Y Wang","year":"2014","unstructured":"Wang Y, et al. Clonal evolution in breast cancer revealed by single nucleus genome sequencing. Nature. 2014;512(7513):155.","journal-title":"Nature"},{"issue":"50","key":"152_CR38","doi-asserted-by":"publisher","first-page":"17947","DOI":"10.1073\/pnas.1420822111","volume":"111","author":"C Gawad","year":"2014","unstructured":"Gawad C, et al. Dissecting the clonal origins of childhood acute lymphoblastic leukemia by single-cell genomics. Proc Natl Acad Sci. 2014;111(50):17947\u201352.","journal-title":"Proc Natl Acad Sci"},{"key":"152_CR39","doi-asserted-by":"crossref","unstructured":"Ramazzotti D, et al. Learning mutational graphs of individual tumor evolution from multi-sample sequencing data. 2017. arXiv preprint \n                              arXiv:1709.01076\n                              \n                           .","DOI":"10.1101\/132183"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0152-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-019-0152-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0152-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T23:07:53Z","timestamp":1595718473000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-019-0152-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,27]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["152"],"URL":"https:\/\/doi.org\/10.1186\/s13015-019-0152-9","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,27]]},"assertion":[{"value":"31 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"17"}}