title: CAPRI: efficient inference of cancer progression models from cross-sectional data.
abstract: We devise a novel inference algorithm to effectively solve the cancer progression model reconstruction problem. Our empirical analysis of the accuracy and convergence rate of our algorithm, CAncer PRogression Inference (CAPRI), shows that it outperforms the state-of-the-art algorithms addressing similar problems.
  
  
  BACKGROUND
  Several cancer-related genomic data have become available (e.g. The Cancer Genome Atlas, TCGA) typically involving hundreds of patients. At present, most of these data are aggregated in a cross-sectional fashion providing all measurements at the time of diagnosis. Our goal is to infer cancer 'progression' models from such data. These models are represented as directed acyclic graphs (DAGs) of collections of 'selectivity' relations, where a mutation in a gene A 'selects' for a later mutation in a gene B. Gaining insight into the structure of such progressions has the potential to improve both the stratification of patients and personalized therapy choices.
  
  
  RESULTS
  The CAPRI algorithm relies on a scoring method based on a probabilistic theory developed by Suppes, coupled with bootstrap and maximum likelihood inference. The resulting algorithm is efficient, achieves high accuracy and has good complexity, also, in terms of convergence properties. CAPRI performs especially well in the presence of noise in the data, and with limited sample sizes. Moreover CAPRI, in contrast to other approaches, robustly reconstructs different types of confluent trajectories despite irregularities in the data. We also report on an ongoing investigation using CAPRI to study atypical Chronic Myeloid Leukemia, in which we uncovered non trivial selectivity relations and exclusivity patterns among key genomic events.
  
  
  METHODS
  CAPRI is part of the TRanslational ONCOlogy R package and is freely available on the web at: http://bimib.disco.unimib.it/index.php/Tronco
  
  
  BACKGROUND
  daniele.ramazzotti@disco.unimib.it
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Informatics, Systems and Communication, University of Milan-Bicocca, Milan, Italy, Center for Neurobehavioral Genetics, University of California Los Angeles, Los Angeles, CA, USA, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA and SYSBIO Centre of Systems Biology, Milano, Italy.
authors.forename: Daniele
authors.initials: D
authors.lastname: Ramazzotti
authors.affiliation: Department of Informatics, Systems and Communication, University of Milan-Bicocca, Milan, Italy, Center for Neurobehavioral Genetics, University of California Los Angeles, Los Angeles, CA, USA, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA and SYSBIO Centre of Systems Biology, Milano, Italy.
authors.forename: Giulio
authors.initials: G
authors.lastname: Caravagna
authors.affiliation: Department of Informatics, Systems and Communication, University of Milan-Bicocca, Milan, Italy, Center for Neurobehavioral Genetics, University of California Los Angeles, Los Angeles, CA, USA, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA and SYSBIO Centre of Systems Biology, Milano, Italy.
authors.forename: Loes
authors.initials: L
authors.lastname: Olde Loohuis
authors.affiliation: Department of Informatics, Systems and Communication, University of Milan-Bicocca, Milan, Italy, Center for Neurobehavioral Genetics, University of California Los Angeles, Los Angeles, CA, USA, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA and SYSBIO Centre of Systems Biology, Milano, Italy.
authors.forename: Alex
authors.initials: A
authors.lastname: Graudenzi
authors.affiliation: Department of Informatics, Systems and Communication, University of Milan-Bicocca, Milan, Italy, Center for Neurobehavioral Genetics, University of California Los Angeles, Los Angeles, CA, USA, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA and SYSBIO Centre of Systems Biology, Milano, Italy.
authors.forename: Ilya
authors.initials: I
authors.lastname: Korsunsky
authors.affiliation: Department of Informatics, Systems and Communication, University of Milan-Bicocca, Milan, Italy, Center for Neurobehavioral Genetics, University of California Los Angeles, Los Angeles, CA, USA, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA and SYSBIO Centre of Systems Biology, Milano, Italy Department of Informatics, Systems and Communication, University of Milan-Bicocca, Milan, Italy, Center for Neurobehavioral Genetics, University of California Los Angeles, Los Angeles, CA, USA, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA and SYSBIO Centre of Systems Biology, Milano, Italy.
authors.forename: Giancarlo
authors.initials: G
authors.lastname: Mauri
authors.affiliation: Department of Informatics, Systems and Communication, University of Milan-Bicocca, Milan, Italy, Center for Neurobehavioral Genetics, University of California Los Angeles, Los Angeles, CA, USA, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA and SYSBIO Centre of Systems Biology, Milano, Italy.
authors.forename: Marco
authors.initials: M
authors.lastname: Antoniotti
authors.affiliation: Department of Informatics, Systems and Communication, University of Milan-Bicocca, Milan, Italy, Center for Neurobehavioral Genetics, University of California Los Angeles, Los Angeles, CA, USA, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA and SYSBIO Centre of Systems Biology, Milano, Italy.
authors.forename: Bud
authors.initials: B
authors.lastname: Mishra
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003430:Cross-Sectional Studies; D030541:Databases, Genetic; D018450:Disease Progression; D006801:Humans; D015464:Leukemia, Myelogenous, Chronic, BCR-ABL Positive / Q000235:genetics* / Q000473:pathology*; D008962:Models, Theoretical; D009154:Mutation / Q000235:genetics; D011336:Probability; D015398:Signal Transduction