{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T08:50:46Z","timestamp":1772614246334,"version":"3.50.1"},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T00:00:00Z","timestamp":1752537600000},"content-version":"vor","delay-in-days":14,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000054","name":"National Cancer Institute","doi-asserted-by":"publisher","award":["U24CA248453"],"award-info":[{"award-number":["U24CA248453"]}],"id":[{"id":"10.13039\/100000054","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000054","name":"National Cancer Institute","doi-asserted-by":"publisher","award":["U24CA264027"],"award-info":[{"award-number":["U24CA264027"]}],"id":[{"id":"10.13039\/100000054","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2046488"],"award-info":[{"award-number":["CCF-2046488"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Reconstructing the evolutionary history of tumors from bulk DNA sequencing of multiple tissue samples remains a challenging computational problem, requiring simultaneous deconvolution of the tumor tissue and inference of its evolutionary history. Recently, phylogenetic reconstruction methods have made significant progress by breaking the reconstruction problem into two parts: a regression problem over a fixed topology and a search over tree space. While effective techniques have been developed for the latter search problem, the regression problem remains a bottleneck in both method design and implementation due to the lack of fast, specialized algorithms.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>Here, we introduce fastppm, a fast tool to solve the perfect phylogeny regression problem via tree-structured dual dynamic programming. fastppm supports arbitrary, separable convex loss functions including the \u21132, piecewise linear, binomial and beta-binomial loss and provides asymptotic improvements for the \u21132 and piecewise linear loss over existing algorithms. We find that fastppm empirically outperforms both specialized and general purpose regression algorithms, obtaining 50\u2013450\u00d7 speedups while providing as accurate solutions as existing approaches. Incorporating fastppm into several phylogeny inference algorithms immediately yields up to 400\u00d7 speedups, requiring only a small change to the program code of existing software. Finally, fastppm enables analysis of low-coverage bulk DNA sequencing data on both simulated data and in a patient-derived mouse model of colorectal cancer, outperforming state-of-the-art phylogeny inference algorithms in terms of both accuracy and runtime.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>fastppm is implemented in C++ and available as both a command-line interface and Python library at github.com\/elkebir-group\/fastppm.git under an MIT license.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaf235","type":"journal-article","created":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T13:02:09Z","timestamp":1752584529000},"page":"i170-i179","source":"Crossref","is-referenced-by-count":1,"title":["Fast tumor phylogeny regression via tree-structured dual dynamic programming"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0132-3472","authenticated-orcid":false,"given":"Henri","family":"Schmidt","sequence":"first","affiliation":[{"name":"Department of Computer Science, Princeton University , Princeton, NJ 08542,","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9871-7415","authenticated-orcid":false,"given":"Yuanyuan","family":"Qi","sequence":"additional","affiliation":[{"name":"Siebel School of Computing and Data Science, University of Illinois Urbana-Champaign , Urbana, IL 61801,","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1274-048X","authenticated-orcid":false,"given":"Benjamin J","family":"Raphael","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Princeton University , Princeton, NJ 08542,","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1468-2407","authenticated-orcid":false,"given":"Mohammed","family":"El-Kebir","sequence":"additional","affiliation":[{"name":"Siebel School of Computing and Data Science, University of Illinois Urbana-Champaign , Urbana, IL 61801,","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2025,7,15]]},"reference":[{"key":"2025071509020042900_btaf235-B1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/24-AOP1694","article-title":"Random trees have height O(n)","volume":"52","author":"Addario-Berry","year":"2024","journal-title":"Ann Probab"},{"key":"2025071509020042900_btaf235-B2","author":"Andersen MS, Dahl J, Vandenberghe L.","year":"2013"},{"key":"2025071509020042900_btaf235-B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000016","article-title":"Distributed optimization and statistical learning via the alternating direction method of multipliers","volume":"3","author":"Boyd","year":"2010","journal-title":"FNT Mach Learn"},{"key":"2025071509020042900_btaf235-B4","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1017\/CBO9780511804441.006","volume-title":"Convex Optimization","author":"Boyd","year":"2004"},{"key":"2025071509020042900_btaf235-B5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00265991","article-title":"Branching processes in the analysis of the heights of trees","volume":"24","author":"Devroye","year":"1987","journal-title":"Acta Inf"},{"key":"2025071509020042900_btaf235-B6","first-page":"3071","year":"2013"},{"key":"2025071509020042900_btaf235-B7","doi-asserted-by":"crossref","first-page":"i671","DOI":"10.1093\/bioinformatics\/bty589","article-title":"SPhyR: tumor phylogeny estimation from single-cell sequencing data under loss and error","volume":"34","author":"El-Kebir","year":"2018","journal-title":"Bioinformatics"},{"key":"2025071509020042900_btaf235-B8","doi-asserted-by":"crossref","first-page":"i62","DOI":"10.1093\/bioinformatics\/btv261","article-title":"Reconstruction of clonal trees and tumor composition from multi-sample sequencing data","volume":"31","author":"El-Kebir","year":"2015","journal-title":"Bioinformatics"},{"key":"2025071509020042900_btaf235-B9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.cels.2016.07.004","article-title":"Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures","volume":"3","author":"El-Kebir","year":"2016","journal-title":"Cell Syst"},{"key":"2025071509020042900_btaf235-B10","doi-asserted-by":"crossref","first-page":"1334","DOI":"10.1038\/s43018-024-00787-0","article-title":"Tumor evolution metrics predict recurrence beyond 10 years in locally advanced prostate cancer","volume":"5","author":"Fernandez-Mateos","year":"2024","journal-title":"Nat Cancer"},{"key":"2025071509020042900_btaf235-B11","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1038\/s41586-022-05249-0","article-title":"Single-cell genomic variation induced by mutational processes in cancer","volume":"612","author":"Funnell","year":"2022","journal-title":"Nature"},{"key":"2025071509020042900_btaf235-B12","first-page":"287","year":"2011"},{"key":"2025071509020042900_btaf235-B13","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1038\/s41586-019-1907-7","article-title":"The evolutionary history of 2,658 cancers","volume":"578","author":"Gerstung","year":"2020","journal-title":"Nature"},{"key":"2025071509020042900_btaf235-B14","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1186\/s12859-020-03919-2","article-title":"PyClone-VI: scalable inference of clonal population structures using whole genome data","volume":"21","author":"Gillis","year":"2020","journal-title":"BMC Bioinformatics"},{"key":"2025071509020042900_btaf235-B15","author":"Goulart"},{"key":"2025071509020042900_btaf235-B16","first-page":"63","author":"Govek","year":"2018"},{"key":"2025071509020042900_btaf235-B17","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","author":"Guang","year":"2023","journal-title":"Bioinformatics"},{"key":"2025071509020042900_btaf235-B18","doi-asserted-by":"crossref","first-page":"992","DOI":"10.3390\/math7100992","article-title":"Universal function approximation by deep neural nets with bounded width and relu activations","volume":"7","author":"Hanin","year":"2019","journal-title":"Mathematics"},{"key":"2025071509020042900_btaf235-B19","first-page":"2109","volume":"376"},{"key":"2025071509020042900_btaf235-B20","first-page":"1","volume":"31"},{"key":"2025071509020042900_btaf235-B21","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1186\/s13059-022-02794-9","article-title":"MEDICC2: whole-genome doubling aware copy-number phylogenies for cancer evolution","volume":"23","author":"Kaufmann","year":"2022","journal-title":"Genome Biol"},{"key":"2025071509020042900_btaf235-B22","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1093\/genetics\/61.4.893","article-title":"The number of heterozygous nucleotide sites maintained in a finite population due to steady flux of mutations","volume":"61","author":"Kimura","year":"1969","journal-title":"Genetics"},{"key":"2025071509020042900_btaf235-B23","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1186\/s13059-021-02583-w","article-title":"CellPhy: accurate and fast probabilistic inference of single-cell phylogenies from scDNA-seq data","volume":"23","author":"Kozlov","year":"2022","journal-title":"Genome Biol"},{"key":"2025071509020042900_btaf235-B24","doi-asserted-by":"crossref","first-page":"e1012653","DOI":"10.1371\/journal.pcbi.1012653","article-title":"Orchard: building large cancer phylogenies using stochastic combinatorial search","volume":"20","author":"Kulman","year":"2024","journal-title":"PLoS Comput Biol"},{"key":"2025071509020042900_btaf235-B25","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1016\/j.cell.2019.10.026","article-title":"Clonal decomposition and DNA replication states defined by scaled single-cell genome sequencing","volume":"179","author":"Laks","year":"2019","journal-title":"Cell"},{"key":"2025071509020042900_btaf235-B26","first-page":"1089","article-title":"Single-cell methylation sequencing data reveal succinct metastatic migration histories and tumor progression models","volume":"33","author":"Liu","year":"2023","journal-title":"Genome Res"},{"key":"2025071509020042900_btaf235-B27","doi-asserted-by":"crossref","first-page":"1349","DOI":"10.1093\/bioinformatics\/btv003","article-title":"Clonality inference in multiple tumor samples using phylogeny","volume":"31","author":"Malikic","year":"2015","journal-title":"Bioinformatics"},{"key":"2025071509020042900_btaf235-B28","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1038\/s41586-021-03357-x","article-title":"Breast tumours maintain a reservoir of subclonal diversity during expansion","volume":"592","author":"Minussi","year":"2021","journal-title":"Nature"},{"key":"2025071509020042900_btaf235-B29","author":"MOSEK ApS","year":"2024"},{"key":"2025071509020042900_btaf235-B30","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.cels.2019.05.010","article-title":"CALDER: inferring phylogenetic trees from longitudinal tumor samples","volume":"8","author":"Myers","year":"2019","journal-title":"Cell Syst"},{"key":"2025071509020042900_btaf235-B31","doi-asserted-by":"crossref","first-page":"ii49","DOI":"10.1093\/bioinformatics\/btac467","article-title":"Discovering significant evolutionary trajectories in cancer phylogenies","volume":"38","author":"Pellegrina","year":"2022","journal-title":"Bioinformatics"},{"key":"2025071509020042900_btaf235-B32","first-page":"1","author":"Qi","year":"2024"},{"key":"2025071509020042900_btaf235-B33","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1186\/s13015-019-0155-6","article-title":"Implications of non-uniqueness in phylogenetic deconvolution of bulk DNA samples of tumors","volume":"14","journal-title":"Algorithm Mol Biol"},{"key":"2025071509020042900_btaf235-B34","doi-asserted-by":"crossref","first-page":"eabc1944","DOI":"10.1126\/science.abc1944","article-title":"Single-cell lineages reveal the rates, routes, and drivers of metastasis in cancer xenografts","volume":"371","author":"Quinn","year":"2021","journal-title":"Science"},{"key":"2025071509020042900_btaf235-B35"},{"key":"2025071509020042900_btaf235-B36","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/j.cell.2020.11.018","article-title":"Colorectal cancer cells enter a diapause-like DTP state to survive chemotherapy","volume":"184","author":"Rehman","year":"2021","journal-title":"Cell"},{"key":"2025071509020042900_btaf235-B37","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/s10957-021-01971-3","article-title":"Efficient semidefinite programming with approximate ADMM","volume":"192","author":"Rontsis","year":"2022","journal-title":"J Optim Theory Appl"},{"key":"2025071509020042900_btaf235-B38","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/BF01681346","article-title":"Locating the vertices of a Steiner tree in an arbitrary metric space","volume":"9","author":"Sankoff","year":"1975","journal-title":"Math Programm"},{"key":"2025071509020042900_btaf235-B39","doi-asserted-by":"crossref","first-page":"i152","DOI":"10.1093\/bioinformatics\/btx270","article-title":"Tumor phylogeny inference using tree-constrained importance sampling","volume":"33","author":"Satas","year":"2017","journal-title":"Bioinformatics"},{"key":"2025071509020042900_btaf235-B40","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1016\/j.cels.2021.07.006","article-title":"DeCiFering the elusive cancer cell fraction in tumor heterogeneity and evolution","volume":"12","author":"Satas","year":"2021","journal-title":"Cell Syst"},{"key":"2025071509020042900_btaf235-B41","doi-asserted-by":"crossref","first-page":"e1012631","DOI":"10.1371\/journal.pcbi.1012631","article-title":"A regression based approach to phylogenetic reconstruction from multi-sample bulk DNA sequencing of tumors","volume":"20","author":"Schmidt","year":"2024","journal-title":"PLoS Comput Biol"},{"key":"2025071509020042900_btaf235-B42","doi-asserted-by":"crossref","first-page":"e1011590","DOI":"10.1371\/journal.pcbi.1011590","article-title":"A zero-agnostic model for copy number evolution in cancer","volume":"19","author":"Schmidt","year":"2023","journal-title":"PLoS Comput Biol"},{"key":"2025071509020042900_btaf235-B43","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1006\/jagm.1996.0045","article-title":"On computing the nested sums and infimal convolutions of convex piecewise-linear functions","volume":"21","author":"Tseng","year":"1996","journal-title":"J Algorithms"},{"key":"2025071509020042900_btaf235-B44","doi-asserted-by":"crossref","first-page":"e1011544","DOI":"10.1371\/journal.pcbi.1011544","article-title":"Phertilizer: growing a clonal tree from ultra-low coverage single-cell DNA sequencing of tumors","volume":"19","author":"Weber","year":"2023","journal-title":"PLoS Comput Biol"},{"key":"2025071509020042900_btaf235-B45","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1158\/2643-3230.BCD-21-0092","article-title":"Reconstructing complex cancer evolutionary histories from multiple bulk DNA samples using Pairtree","volume":"3","author":"Wintersinger","year":"2022","journal-title":"Blood Cancer Discov"},{"key":"2025071509020042900_btaf235-B46","doi-asserted-by":"crossref","first-page":"1905","DOI":"10.1016\/j.cell.2022.04.015","article-title":"Lineage tracing reveals the phylodynamics, plasticity, and paths of tumor evolution","volume":"185","author":"Yang","year":"2022","journal-title":"Cell"},{"key":"2025071509020042900_btaf235-B47","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1186\/s13059-019-1922-x","article-title":"DENDRO: genetic heterogeneity profiling and subclone detection by single-cell RNA sequencing","volume":"21","author":"Zhou","year":"2020","journal-title":"Genome Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/Supplement_1\/i170\/63745508\/btaf235.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/Supplement_1\/i170\/63745508\/btaf235.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T13:02:17Z","timestamp":1752584537000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/41\/Supplement_1\/i170\/8199380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,1]]},"references-count":47,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2025,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaf235","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,7]]},"published":{"date-parts":[[2025,7,1]]}}}