{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"institution":[{"name":"bioRxiv"}],"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T20:03:35Z","timestamp":1772481815559,"version":"3.50.1"},"posted":{"date-parts":[[2026,2,27]]},"group-title":"Cancer Biology","reference-count":73,"publisher":"openRxiv","license":[{"start":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T00:00:00Z","timestamp":1772150400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2026,2,27]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                <jats:p>Understanding and comparing tumor evolutionary histories is fundamental to cancer genomics. Clonal trees, used to model tumor progression, are rooted, unordered trees in which each node represents a subclone labeled by a set of distinct mutations.<\/jats:p>\n                <jats:p>\n                  To compare two clonal trees, we introduce\n                  <jats:monospace>omlta<\/jats:monospace>\n                  , the\n                  <jats:underline>o<\/jats:underline>\n                  ptimal\n                  <jats:underline>m<\/jats:underline>\n                  ulti-label tree\n                  <jats:underline>a<\/jats:underline>\n                  lignment, which removes the minimum number of mutation labels from the trees, so that the remaining trees are isomorphic. Computing\n                  <jats:monospace>omlta<\/jats:monospace>\n                  is NP-hard. Here, we present an algorithm to compute the\n                  <jats:monospace>omlta<\/jats:monospace>\n                  , with a running time of\n                  <jats:inline-formula>\n                    <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"708046v1_inline1.gif\"\/>\n                  <\/jats:inline-formula>\n                  where\n                  <jats:italic>L<\/jats:italic>\n                  \u2265 1 is the total number of mutation labels occurring in the input trees and\n                  <jats:italic>k<\/jats:italic>\n                  is the minimum possible number of mutation labels that need to be removed for the alignment.\n                <\/jats:p>\n                <jats:p>\n                  Our implementation (\n                  <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/algo-cancer\/omlta\">https:\/\/github.com\/algo-cancer\/omlta<\/jats:ext-link>\n                  ) is the first computational tool for determining the\n                  <jats:italic>optimal<\/jats:italic>\n                  alignment between clonal trees. We applied\n                  <jats:monospace>omlta<\/jats:monospace>\n                  to 126 cases from the TRACERx study on non-small cell lung cancers and some melanoma single-cell data.\n                <\/jats:p>","DOI":"10.64898\/2026.02.25.708046","type":"posted-content","created":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T21:00:24Z","timestamp":1772226024000},"source":"Crossref","is-referenced-by-count":0,"title":["Identifying Robust Subclonal Structures through Tumor Progression Tree Alignment"],"prefix":"10.64898","author":[{"given":"Jacob","family":"Gilbert","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chih Hao","family":"Wu","sequence":"additional","affiliation":[{"name":"Cancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marina","family":"Knittel","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, UC San Diego, San Diego, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro A.","family":"Sch\u00e4ffer","sequence":"additional","affiliation":[{"name":"Cancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salem","family":"Maliki\u0107","sequence":"additional","affiliation":[{"name":"Cancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Cenk","family":"Sahinalp","sequence":"additional","affiliation":[{"name":"Cancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"54368","reference":[{"key":"2026030211102350000_2026.02.25.708046v1.1","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions and reversals","volume":"10","year":"1966","journal-title":"Sov. Phys. Dokl"},{"key":"2026030211102350000_2026.02.25.708046v1.2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"2026030211102350000_2026.02.25.708046v1.3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"2026030211102350000_2026.02.25.708046v1.4","doi-asserted-by":"publisher","DOI":"10.1038\/s41588-021-01005-8"},{"key":"2026030211102350000_2026.02.25.708046v1.5","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1016\/j.tcs.2010.10.002","article-title":"Exact algorithms for computing the tree edit distance between unordered trees","volume":"412","year":"2011","journal-title":"Theor. Comp. Sci"},{"key":"2026030211102350000_2026.02.25.708046v1.6","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-023-05729-x"},{"key":"2026030211102350000_2026.02.25.708046v1.7","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1038\/s41596-023-00913-9","article-title":"CONIPHER: a computational framework for scalable phylogenetic reconstruction with error correction","volume":"19","year":"2024","journal-title":"Nature Prot"},{"key":"2026030211102350000_2026.02.25.708046v1.8","doi-asserted-by":"publisher","DOI":"10.1158\/2643-3230.bcd-21-0092"},{"key":"2026030211102350000_2026.02.25.708046v1.9","doi-asserted-by":"publisher","DOI":"10.1038\/s41591-020-0818-3"},{"key":"2026030211102350000_2026.02.25.708046v1.10","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1109\/TCBB.2020.3029689","article-title":"Graphyc: Using consensus to infer tumor evolution","volume":"19","year":"2022","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"2026030211102350000_2026.02.25.708046v1.11","doi-asserted-by":"crossref","first-page":"i204","DOI":"10.1093\/bioinformatics\/btad230","article-title":"A weighted distance-based approach for deriving consensus tumor evolutionary trees","volume":"39","year":"2023","journal-title":"Bioinformatics"},{"key":"2026030211102350000_2026.02.25.708046v1.12","doi-asserted-by":"crossref","unstructured":"Fu, X. & Schwartz, R. Contreedp: A consensus method of tumor trees based on maximum directed partition support problem. In 2021 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 125\u2013130 (2021).","DOI":"10.1109\/BIBM52615.2021.9669279"},{"key":"2026030211102350000_2026.02.25.708046v1.13","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz312"},{"key":"2026030211102350000_2026.02.25.708046v1.14","doi-asserted-by":"crossref","unstructured":"Mehrabadi, F. R. et al. Profiles of expressed mutations in single cells reveal subclonal expansion patterns and therapeutic impact of intratumor heterogeneity. bioRxiv 2021\u201303 (2021).","DOI":"10.1101\/2021.03.26.437185"},{"key":"2026030211102350000_2026.02.25.708046v1.15","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaa801"},{"key":"2026030211102350000_2026.02.25.708046v1.16","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-019-0152-9"},{"key":"2026030211102350000_2026.02.25.708046v1.17","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv003"},{"key":"2026030211102350000_2026.02.25.708046v1.18","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv261"},{"key":"2026030211102350000_2026.02.25.708046v1.19","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-016-0936-x"},{"key":"2026030211102350000_2026.02.25.708046v1.20","doi-asserted-by":"publisher","DOI":"10.1101\/gr.234435.118"},{"key":"2026030211102350000_2026.02.25.708046v1.21","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(81)90043-2"},{"key":"2026030211102350000_2026.02.25.708046v1.22","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz869"},{"key":"2026030211102350000_2026.02.25.708046v1.23","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-021-00188-3"},{"key":"2026030211102350000_2026.02.25.708046v1.24","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaa676"},{"key":"2026030211102350000_2026.02.25.708046v1.25","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/0020-0190(77)90064-3","article-title":"The tree-to-tree editing problem","volume":"6","year":"1977","journal-title":"Inf. Proc. Lett"},{"key":"2026030211102350000_2026.02.25.708046v1.26","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/322139.322143","article-title":"The tree-to-tree correction problem","volume":"26","year":"1979","journal-title":"J. ACM"},{"key":"2026030211102350000_2026.02.25.708046v1.27","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"},{"key":"2026030211102350000_2026.02.25.708046v1.28","first-page":"91","volume-title":"6th Annual European Symposium on Algorithms, ESA 1998","volume":"1461","year":"1998"},{"key":"2026030211102350000_2026.02.25.708046v1.29","first-page":"2","article-title":"An optimal decomposition algorithm for tree edit distance","volume":"6","year":"2009","journal-title":"ACM Trans. Algorithms"},{"key":"2026030211102350000_2026.02.25.708046v1.30","doi-asserted-by":"crossref","unstructured":"Mao, X. Breaking the cubic barrier for (unweighted) tree edit distance. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, 792\u2013803 (IEEE, 2021).","DOI":"10.1109\/FOCS52979.2021.00082"},{"key":"2026030211102350000_2026.02.25.708046v1.31","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(92)90136-J","article-title":"On the editing distance between unordered labeled trees","volume":"42","year":"1992","journal-title":"Inf. Proc. Lett"},{"key":"2026030211102350000_2026.02.25.708046v1.32","doi-asserted-by":"crossref","unstructured":"Akutsu, T. , Tamura, T. , Fukagawa, D. & Takasu, A. Efficient exponential time algorithms for edit distance between unordered trees. In K\u00e4rkk\u00e4inen, J. & Stoye, J. (eds.) Combinatorial Pattern Matching, 360\u2013372 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2012).","DOI":"10.1007\/978-3-642-31265-6_29"},{"key":"2026030211102350000_2026.02.25.708046v1.33","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.tcs.2012.11.017","article-title":"Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees","volume":"470","year":"2013","journal-title":"Theor. Comp. Sci"},{"issue":"1","key":"2026030211102350000_2026.02.25.708046v1.34","first-page":"S13","article-title":"A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures","volume":"12","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2026030211102350000_2026.02.25.708046v1.35","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2012.0133"},{"key":"2026030211102350000_2026.02.25.708046v1.36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794269461"},{"key":"2026030211102350000_2026.02.25.708046v1.37","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796313477"},{"key":"2026030211102350000_2026.02.25.708046v1.38","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","article-title":"On the agreement of many trees","volume":"55","year":"1995","journal-title":"Inf. Proc. Lett"},{"key":"2026030211102350000_2026.02.25.708046v1.39","first-page":"7","volume-title":"24th International Workshop on Algorithms in Bioinformatics (WABI 2024)","volume":"312","year":"2024"},{"key":"2026030211102350000_2026.02.25.708046v1.40","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1038\/nmeth.2883","article-title":"Pyclone: statistical inference of clonal population structure in cancer","volume":"11","year":"2014","journal-title":"Nature Meth"},{"key":"2026030211102350000_2026.02.25.708046v1.41","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-015-0647-8"},{"key":"2026030211102350000_2026.02.25.708046v1.42","doi-asserted-by":"crossref","unstructured":"Fischer, M. , Herbst, L. , Kersting, S. , K\u00fchn, A. L. & Wicke, K. Tree balance indices: A comprehensive survey (Springer Nature, Cham, Switzerland, 2023).","DOI":"10.1007\/978-3-031-39800-1"},{"key":"2026030211102350000_2026.02.25.708046v1.43","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/j.trecan.2016.04.002","article-title":"Re-evaluating clonal dominance in cancer evolution","volume":"2","year":"2016","journal-title":"Trends Cancer"},{"key":"2026030211102350000_2026.02.25.708046v1.44","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.2009.04880.x"},{"key":"2026030211102350000_2026.02.25.708046v1.45","doi-asserted-by":"crossref","unstructured":"Cross, W. C. H. , Graham, T. A. & Wright, N. A. New paradigms in clonal evolution: punctuated equilibrium in cancer. J. Pathol. 126\u2013136 (2016).","DOI":"10.1002\/path.4757"},{"key":"2026030211102350000_2026.02.25.708046v1.46","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-023-05783-5"},{"key":"2026030211102350000_2026.02.25.708046v1.47","doi-asserted-by":"publisher","DOI":"10.1158\/0008-5472.CAN-15-1889"},{"key":"2026030211102350000_2026.02.25.708046v1.48","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkad986"},{"key":"2026030211102350000_2026.02.25.708046v1.49","doi-asserted-by":"publisher","DOI":"10.1158\/2159-8290.CD-23-0467"},{"key":"2026030211102350000_2026.02.25.708046v1.50","first-page":"1","article-title":"OncoKB: a precision oncology knowledge base","volume":"1","year":"2017","journal-title":"JCO Precis. Oncol"},{"key":"2026030211102350000_2026.02.25.708046v1.51","doi-asserted-by":"publisher","DOI":"10.1126\/scitranslmed.aaa1408"},{"key":"2026030211102350000_2026.02.25.708046v1.52","doi-asserted-by":"crossref","first-page":"e2013201","DOI":"10.1001\/jamanetworkopen.2020.13201","article-title":"Association of itmuc16 mutation with response to immune checkpoint inhibitors in solid tumors","volume":"3","year":"2020","journal-title":"JAMA Netw. Open"},{"key":"2026030211102350000_2026.02.25.708046v1.53","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.3389\/fimmu.2019.01113","article-title":"Association of lrp1b mutation with tumor mutation burden and outcomes in melanoma and non-small cell lung cancer patients treated with immune check-point blockades","volume":"10","year":"2019","journal-title":"Front. Immunol"},{"key":"2026030211102350000_2026.02.25.708046v1.54","doi-asserted-by":"publisher","DOI":"10.1136\/jitc-2020-001792"},{"key":"2026030211102350000_2026.02.25.708046v1.55","doi-asserted-by":"crossref","first-page":"101493","DOI":"10.1016\/j.tranon.2022.101493","article-title":"Potential predictive value of comutant lrp1b and fat for immune response in non-small cell lung cancer: Lrp1b and fat comutation enhance immune response","volume":"24","year":"2022","journal-title":"Transl. Oncol"},{"key":"2026030211102350000_2026.02.25.708046v1.56","doi-asserted-by":"publisher","DOI":"10.1097\/MD.0000000000035481"},{"key":"2026030211102350000_2026.02.25.708046v1.57","first-page":"3075","article-title":"Mutator phenotype may be required for multistage carcinogenesis","volume":"51","year":"1991","journal-title":"Cancer Res"},{"key":"2026030211102350000_2026.02.25.708046v1.58","doi-asserted-by":"publisher","DOI":"10.1016\/S0962-8924(99)01661-X"},{"key":"2026030211102350000_2026.02.25.708046v1.59","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.97.3.1236"},{"key":"2026030211102350000_2026.02.25.708046v1.60","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz676"},{"key":"2026030211102350000_2026.02.25.708046v1.61","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1038\/nprot.2014.006","article-title":"Full-length RNA-seq from single cells using Smart-seq2","volume":"9","year":"2014","journal-title":"Nat. Prot"},{"key":"2026030211102350000_2026.02.25.708046v1.62","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1038\/nmeth.4179","article-title":"Seq-well: portable, low-cost rna sequencing of single cells at high throughput","volume":"14","year":"2017","journal-title":"Nat. Meth"},{"key":"2026030211102350000_2026.02.25.708046v1.63","first-page":"159","article-title":"Multiple sequence alignment: Algorithms and applications","volume":"11","year":"1999","journal-title":"Adv. Biophys"},{"key":"2026030211102350000_2026.02.25.708046v1.64","doi-asserted-by":"publisher","DOI":"10.1016\/j.sbi.2006.04.004"},{"key":"2026030211102350000_2026.02.25.708046v1.65","doi-asserted-by":"crossref","first-page":"bbbac069","DOI":"10.1093\/bib\/bbac069","article-title":"A survey on the algorithm and development of multiple sequence alignment","volume":"23","year":"2022","journal-title":"Brief. Bioinformatics"},{"key":"2026030211102350000_2026.02.25.708046v1.66","unstructured":"Cormen, T. H. , Leiserson, C. E. , Rivest, R. L. & Stein, C. Introduction to Algorithms, 3rd Edition (MIT Press, 2009). URL http:\/\/mitpress.mit.edu\/books\/introduction-algorithms."},{"key":"2026030211102350000_2026.02.25.708046v1.67","unstructured":"Garey, M. R. & Johnson, D. S. Computers and Intractability; A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York, USA, 1990)."},{"key":"2026030211102350000_2026.02.25.708046v1.68","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-020-14976-9"},{"key":"2026030211102350000_2026.02.25.708046v1.69","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-023-02933-w"},{"key":"2026030211102350000_2026.02.25.708046v1.70","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-3"},{"key":"2026030211102350000_2026.02.25.708046v1.71","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2021.0342"},{"key":"2026030211102350000_2026.02.25.708046v1.72","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-015-0647-8"},{"key":"2026030211102350000_2026.02.25.708046v1.73","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-019-10737-5"}],"container-title":[],"original-title":[],"link":[{"URL":"https:\/\/syndication.highwire.org\/content\/doi\/10.64898\/2026.02.25.708046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T19:10:32Z","timestamp":1772478632000},"score":1,"resource":{"primary":{"URL":"http:\/\/biorxiv.org\/lookup\/doi\/10.64898\/2026.02.25.708046"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,27]]},"references-count":73,"URL":"https:\/\/doi.org\/10.64898\/2026.02.25.708046","relation":{},"subject":[],"published":{"date-parts":[[2026,2,27]]},"subtype":"preprint"}}