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...

Descripción completa

Detalles Bibliográficos
Autores principales: Sundermann, Linda K., Wintersinger, Jeff, Rätsch, Gunnar, Stoye, Jens, Morris, Quaid
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