Paper

PhISCS-BnB: A Fast Branch and Bound Algorithm for the Perfect Tumor Phylogeny Reconstruction Problem

Lee, Maxwell P, Farid Rashidi Mehrabadi, Schaffer, Alejandro A, Merlino, Glenn, Sahinalp, S Cenk, Salem Malikic, Gertz, E Michael, Perez-Guijarro, Eva, Day, Chi-Ping, Marie, Kerrie, Erfan Sadeqi Azer, Ergun, Funda, Xuan Cindy Li

2020

Overview

Motivation: Recent advances in single cell sequencing (SCS) offer an unprecedented insight into tumor emergence and evolution. Principled approaches to tumor phylogeny reconstruction via SCS data are typically based on general computational methods for solving an integer linear program (ILP), or a constraint satisfaction program (CSP), which, although guaranteeing convergence to the most likely solution, are very slow. Others based on Monte Carlo Markov Chain (MCMC) or alternative heuristics not only offer no such guarantee, but also are not faster in practice. As a result, novel methods that can scale up to handle the size and noise characteristics of emerging SCS data are highly desirable to fully utilize this technology. Results: We introduce PhISCS-BnB, a Branch and Bound algorithm to compute the most likely perfect phylogeny (PP) on an input genotype matrix extracted from a SCS data set. PhISCS-BnB not only offers an optimality guarantee, but is also 10 to 100 times faster than the best available methods on simulated tumor SCS data. We also applied PhISCS-BnB on a large melanoma data set derived from the sub-lineages of a cell line involving 24 clones with 3574 mutations, which returned the optimal tumor phylogeny in less than 2 hours. The resulting phylogeny also agrees with bulk exome sequencing data obtained from in vivo tumors growing out from the same cell line. Availability: https://github.com/algo-cancer/PhISCS-BnB Footnotes * We have removed the list of the mutations at edges of the tree (it was at the end of the previous document) and added them to our Github repository linked in the manuscript (Figure 1 caption).

• Publisher: Cold Spring Harbor Laboratory Press,Cold Spring Harbor Laboratory
• Subject: Algorithms / Bioinformatics / Computer applications / Genotypes / Markov chains / Melanoma / Mutation / Phylogeny / Problem solving / Tumors