Most of the evolutionary history reconstruction approaches are based on the infinite sites assumption, which states that mutations appear once in the evolutionary history. The Perfect Phylogeny model is the result of the infinite sites assumption and has been widely used to infer cancer evolution. Nonetheless, recent results show that recurrent and back mutations are present in the evolutionary history of tumors, hence the Perfect Phylogeny model might be too restrictive. We propose an approach that allows losing previously acquired mutations and multiple acquisitions of a character. Moreover, we provide an ILP formulation for the evolutionary tree reconstruction problem. Our formulation allows us to tackle both the Incomplete Directed Phylogeny problem and the Clonal Reconstruction problem when general evolutionary models are considered. The latter problem is fundamental in cancer genomics, the goal is to study the evolutionary history of a tumor considering as input data the fraction of cells having a certain mutation in a set of cancer samples. For the Clonal Reconstruction problem, an experimental analysis shows the advantage of allowing mutation losses. Namely, by analyzing real and simulated datasets, our ILP approach provides a better interpretation of the evolutionary history than a Perfect Phylogeny. The software is at https://github.com/AlgoLab/gppf.

Does relaxing the infinite sites assumption give better tumor phylogenies? An ILP-based comparative approach / P. Bonizzoni, S. Ciccolella, G.D. Vedova, M. Soto. - In: IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS. - ISSN 1545-5963. - 16:5(2019 Sep), pp. 1410-1423. [10.1109/TCBB.2018.2865729]

Does relaxing the infinite sites assumption give better tumor phylogenies? An ILP-based comparative approach

M. Soto
Ultimo
2019

Abstract

Most of the evolutionary history reconstruction approaches are based on the infinite sites assumption, which states that mutations appear once in the evolutionary history. The Perfect Phylogeny model is the result of the infinite sites assumption and has been widely used to infer cancer evolution. Nonetheless, recent results show that recurrent and back mutations are present in the evolutionary history of tumors, hence the Perfect Phylogeny model might be too restrictive. We propose an approach that allows losing previously acquired mutations and multiple acquisitions of a character. Moreover, we provide an ILP formulation for the evolutionary tree reconstruction problem. Our formulation allows us to tackle both the Incomplete Directed Phylogeny problem and the Clonal Reconstruction problem when general evolutionary models are considered. The latter problem is fundamental in cancer genomics, the goal is to study the evolutionary history of a tumor considering as input data the fraction of cells having a certain mutation in a set of cancer samples. For the Clonal Reconstruction problem, an experimental analysis shows the advantage of allowing mutation losses. Namely, by analyzing real and simulated datasets, our ILP approach provides a better interpretation of the evolutionary history than a Perfect Phylogeny. The software is at https://github.com/AlgoLab/gppf.
camin-sokal model; cancer genomics; dollo model; incomplete phylogeny problem; integer linear programming; perfect phylogeny; persistent phylogeny; tumoral phylogeny
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
   Automi e Linguaggi Formali: Aspetti Matematici e Applicativi
   MINISTERO DELL'ISTRUZIONE E DEL MERITO
   2010LYA9RH_005
set-2019
Article (author)
File in questo prodotto:
File Dimensione Formato  
Does_Relaxing_the_Infinite_Sites_Assumption_Give_Better_Tumor_Phylogenies_An_ILP-Based_Comparative_Approach.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 2.27 MB
Formato Adobe PDF
2.27 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/961449
Citazioni
  • ???jsp.display-item.citation.pmc??? 6
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 13
social impact