TY - GEN
T1 - Phyolin
T2 - 20th International Workshop on Algorithms in Bioinformatics, WABI 2020
AU - Weber, Leah L.
AU - El-Kebir, Mohammed
N1 - Funding Information:
Funding Mohammed El-Kebir: This work was supported by the National Science Foundation under award number CCF 1850502.
Publisher Copyright:
© Leah L. Weber and Mohammed El-Kebir; licensed under Creative Commons License CC-BY
PY - 2020/8/1
Y1 - 2020/8/1
N2 - Cancer arises from an evolutionary process where somatic mutations occur and eventually give rise to clonal expansions. Modeling this evolutionary process as a phylogeny is useful for treatment decision-making as well as understanding evolutionary patterns across patients and cancer types. However, cancer phylogeny inference from single-cell DNA sequencing data of tumors is challenging due to limitations with sequencing technology and the complexity of the resulting problem. Therefore, as a first step some value might be obtained from correctly classifying the evolutionary process as either linear or branched. The biological implications of these two high-level patterns are different and understanding what cancer types and which patients have each of these trajectories could provide useful insight for both clinicians and researchers. Here, we introduce the Linear Perfect Phylogeny Flipping Problem as a means of testing a null model that the tree topology is linear and show that it is NP-hard. We develop Phyolin and, through both in silico experiments and real data application, show that it is an accurate, easy to use and a reasonably fast method for classifying an evolutionary trajectory as linear or branched.
AB - Cancer arises from an evolutionary process where somatic mutations occur and eventually give rise to clonal expansions. Modeling this evolutionary process as a phylogeny is useful for treatment decision-making as well as understanding evolutionary patterns across patients and cancer types. However, cancer phylogeny inference from single-cell DNA sequencing data of tumors is challenging due to limitations with sequencing technology and the complexity of the resulting problem. Therefore, as a first step some value might be obtained from correctly classifying the evolutionary process as either linear or branched. The biological implications of these two high-level patterns are different and understanding what cancer types and which patients have each of these trajectories could provide useful insight for both clinicians and researchers. Here, we introduce the Linear Perfect Phylogeny Flipping Problem as a means of testing a null model that the tree topology is linear and show that it is NP-hard. We develop Phyolin and, through both in silico experiments and real data application, show that it is an accurate, easy to use and a reasonably fast method for classifying an evolutionary trajectory as linear or branched.
KW - Combinatorial optimization
KW - Constraint programming
KW - Intra-tumor heterogeneity
UR - http://www.scopus.com/inward/record.url?scp=85092788472&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85092788472&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.WABI.2020.5
DO - 10.4230/LIPIcs.WABI.2020.5
M3 - Conference contribution
AN - SCOPUS:85092788472
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 20th International Workshop on Algorithms in Bioinformatics, WABI 2020
A2 - Kingsford, Carl
A2 - Pisanti, Nadia
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 7 September 2020 through 9 September 2020
ER -