PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem

Abstract 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, or a...

Full description

Saved in:
Bibliographic Details
Published in:Bioinformatics (Oxford, England) England), 2020-07, Vol.36 (Supplement_1), p.i169-i176
Main Authors: Sadeqi Azer, Erfan, Rashidi Mehrabadi, Farid, Malikić, Salem, Li, Xuan Cindy, Bartok, Osnat, Litchfield, Kevin, Levy, Ronen, Samuels, Yardena, Schäffer, Alejandro A, Gertz, E Michael, Day, Chi-Ping, Pérez-Guijarro, Eva, Marie, Kerrie, Lee, Maxwell P, Merlino, Glenn, Ergun, Funda, Sahinalp, S Cenk
Format: Article
Language:English
Subjects:
Algorithms
Genomic Variation Analysis
Humans
Markov Chains
Neoplasms - genetics
Phylogeny
Sequence Analysis
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Abstract 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, or a constraint satisfaction program, which, although guaranteeing convergence to the most likely solution, are very slow. Others based on Monte Carlo Markov Chain 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 (phylogeny inference using SCS via branch and bound), a branch and bound algorithm to compute the most likely perfect phylogeny on an input genotype matrix extracted from an SCS dataset. PhISCS-BnB not only offers an optimality guarantee, but is also 10–100 times faster than the best available methods on simulated tumor SCS data. We also applied PhISCS-BnB on a recently published large melanoma dataset derived from the sublineages of a cell line involving 20 clones with 2367 mutations, which returned the optimal tumor phylogeny in
ISSN:1367-4803
1367-4811
DOI:10.1093/bioinformatics/btaa464