Cargando…
Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine
Tumors contain multiple subpopulations of genetically distinct cancer cells. Reconstructing their evolutionary history can improve our understanding of how cancers develop and respond to treatment. Subclonal reconstruction methods cluster mutations into groups that co-occur within the same subpopula...
Autores principales: | , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Public Library of Science
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7845980/ https://www.ncbi.nlm.nih.gov/pubmed/33465079 http://dx.doi.org/10.1371/journal.pcbi.1008400 |
_version_ | 1783644655476277248 |
---|---|
author | Sundermann, Linda K. Wintersinger, Jeff Rätsch, Gunnar Stoye, Jens Morris, Quaid |
author_facet | Sundermann, Linda K. Wintersinger, Jeff Rätsch, Gunnar Stoye, Jens Morris, Quaid |
author_sort | Sundermann, Linda K. |
collection | PubMed |
description | Tumors contain multiple subpopulations of genetically distinct cancer cells. Reconstructing their evolutionary history can improve our understanding of how cancers develop and respond to treatment. Subclonal reconstruction methods cluster mutations into groups that co-occur within the same subpopulations, estimate the frequency of cells belonging to each subpopulation, and infer the ancestral relationships among the subpopulations by constructing a clone tree. However, often multiple clone trees are consistent with the data and current methods do not efficiently capture this uncertainty; nor can these methods scale to clone trees with a large number of subclonal populations. Here, we formalize the notion of a partially-defined clone tree (partial clone tree for short) that defines a subset of the pairwise ancestral relationships in a clone tree, thereby implicitly representing the set of all clone trees that have these defined pairwise relationships. Also, we introduce a special partial clone tree, the Maximally-Constrained Ancestral Reconstruction (MAR), which summarizes all clone trees fitting the input data equally well. Finally, we extend commonly used clone tree validity conditions to apply to partial clone trees and describe SubMARine, a polynomial-time algorithm producing the subMAR, which approximates the MAR and guarantees that its defined relationships are a subset of those present in the MAR. We also extend SubMARine to work with subclonal copy number aberrations and define equivalence constraints for this purpose. Further, we extend SubMARine to permit noise in the estimates of the subclonal frequencies while retaining its validity conditions and guarantees. In contrast to other clone tree reconstruction methods, SubMARine runs in time and space that scale polynomially in the number of subclones. We show through extensive noise-free simulation, a large lung cancer dataset and a prostate cancer dataset that the subMAR equals the MAR in all cases where only a single clone tree exists and that it is a perfect match to the MAR in most of the other cases. Notably, SubMARine runs in less than 70 seconds on a single thread with less than one Gb of memory on all datasets presented in this paper, including ones with 50 nodes in a clone tree. On the real-world data, SubMARine almost perfectly recovers the previously reported trees and identifies minor errors made in the expert-driven reconstructions of those trees. The freely-available open-source code implementing SubMARine can be downloaded at https://github.com/morrislab/submarine. |
format | Online Article Text |
id | pubmed-7845980 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | Public Library of Science |
record_format | MEDLINE/PubMed |
spelling | pubmed-78459802021-02-04 Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine Sundermann, Linda K. Wintersinger, Jeff Rätsch, Gunnar Stoye, Jens Morris, Quaid PLoS Comput Biol Research Article Tumors contain multiple subpopulations of genetically distinct cancer cells. Reconstructing their evolutionary history can improve our understanding of how cancers develop and respond to treatment. Subclonal reconstruction methods cluster mutations into groups that co-occur within the same subpopulations, estimate the frequency of cells belonging to each subpopulation, and infer the ancestral relationships among the subpopulations by constructing a clone tree. However, often multiple clone trees are consistent with the data and current methods do not efficiently capture this uncertainty; nor can these methods scale to clone trees with a large number of subclonal populations. Here, we formalize the notion of a partially-defined clone tree (partial clone tree for short) that defines a subset of the pairwise ancestral relationships in a clone tree, thereby implicitly representing the set of all clone trees that have these defined pairwise relationships. Also, we introduce a special partial clone tree, the Maximally-Constrained Ancestral Reconstruction (MAR), which summarizes all clone trees fitting the input data equally well. Finally, we extend commonly used clone tree validity conditions to apply to partial clone trees and describe SubMARine, a polynomial-time algorithm producing the subMAR, which approximates the MAR and guarantees that its defined relationships are a subset of those present in the MAR. We also extend SubMARine to work with subclonal copy number aberrations and define equivalence constraints for this purpose. Further, we extend SubMARine to permit noise in the estimates of the subclonal frequencies while retaining its validity conditions and guarantees. In contrast to other clone tree reconstruction methods, SubMARine runs in time and space that scale polynomially in the number of subclones. We show through extensive noise-free simulation, a large lung cancer dataset and a prostate cancer dataset that the subMAR equals the MAR in all cases where only a single clone tree exists and that it is a perfect match to the MAR in most of the other cases. Notably, SubMARine runs in less than 70 seconds on a single thread with less than one Gb of memory on all datasets presented in this paper, including ones with 50 nodes in a clone tree. On the real-world data, SubMARine almost perfectly recovers the previously reported trees and identifies minor errors made in the expert-driven reconstructions of those trees. The freely-available open-source code implementing SubMARine can be downloaded at https://github.com/morrislab/submarine. Public Library of Science 2021-01-19 /pmc/articles/PMC7845980/ /pubmed/33465079 http://dx.doi.org/10.1371/journal.pcbi.1008400 Text en © 2021 Sundermann et al http://creativecommons.org/licenses/by/4.0/ This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. |
spellingShingle | Research Article Sundermann, Linda K. Wintersinger, Jeff Rätsch, Gunnar Stoye, Jens Morris, Quaid Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine |
title | Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine |
title_full | Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine |
title_fullStr | Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine |
title_full_unstemmed | Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine |
title_short | Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine |
title_sort | reconstructing tumor evolutionary histories and clone trees in polynomial-time with submarine |
topic | Research Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7845980/ https://www.ncbi.nlm.nih.gov/pubmed/33465079 http://dx.doi.org/10.1371/journal.pcbi.1008400 |
work_keys_str_mv | AT sundermannlindak reconstructingtumorevolutionaryhistoriesandclonetreesinpolynomialtimewithsubmarine AT wintersingerjeff reconstructingtumorevolutionaryhistoriesandclonetreesinpolynomialtimewithsubmarine AT ratschgunnar reconstructingtumorevolutionaryhistoriesandclonetreesinpolynomialtimewithsubmarine AT stoyejens reconstructingtumorevolutionaryhistoriesandclonetreesinpolynomialtimewithsubmarine AT morrisquaid reconstructingtumorevolutionaryhistoriesandclonetreesinpolynomialtimewithsubmarine |