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

Erfan Sadeqi Azer; Farid Rashidi Mehrabadi; Salem Malikić; Xuan Cindy Li; Osnat Bartok; Kevin Litchfield; Ronen Levy; Yardena Samuels; Alejandro A. Schäffer; Michael E Gertz; Chi-Ping Day; Eva Pérez-Guijarro; Kerrie Marie; Maxwell P. Lee; Glenn Merlino; Funda Ergun; S. Cenk Sahinalp

doi:10.1093/bioinformatics/btaa464

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

Erfan Sadeqi Azer, Farid Rashidi Mehrabadi, Salem Malikić, Xuan Cindy Li, Osnat Bartok, Kevin Litchfield, Ronen Levy, Yardena Samuels, Alejandro A. Schäffer, Michael E Gertz, Chi-Ping Day, Eva Pérez-Guijarro, Kerrie Marie, Maxwell P. Lee, Glenn Merlino, Funda Ergun, S. Cenk Sahinalp

Division of Molecular & Cellular Function (L5)

Research output: Contribution to journal › Article › peer-review

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

Original language	English
Pages (from-to)	i169–i176
Number of pages	8
Journal	Bioinformatics
Volume	36
Issue number	1
DOIs	https://doi.org/10.1093/bioinformatics/btaa464
Publication status	Published - 13 Jul 2020

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1093/bioinformatics/btaa464

Cite this

Azer, E. S., Mehrabadi, F. R., Malikić, S., Li, X. C., Bartok, O., Litchfield, K., Levy, R., Samuels, Y., Schäffer, A. A., Gertz, M. E., Day, C.-P., Pérez-Guijarro, E., Marie, K., Lee, M. P., Merlino, G., Ergun, F., & Sahinalp, S. C. (2020). PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem. Bioinformatics, 36(1), i169–i176. https://doi.org/10.1093/bioinformatics/btaa464

@article{62e8e13d38734a97b58fff830b1902bb,

title = "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 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 ",

author = "Azer, {Erfan Sadeqi} and Mehrabadi, {Farid Rashidi} and Salem Maliki{\'c} and Li, {Xuan Cindy} and Osnat Bartok and Kevin Litchfield and Ronen Levy and Yardena Samuels and Sch{\"a}ffer, {Alejandro A.} and Gertz, {Michael E} and Chi-Ping Day and Eva P{\'e}rez-Guijarro and Kerrie Marie and Lee, {Maxwell P.} and Glenn Merlino and Funda Ergun and Sahinalp, {S. Cenk}",

year = "2020",

month = jul,

day = "13",

doi = "10.1093/bioinformatics/btaa464",

language = "English",

volume = "36",

pages = "i169–i176",

journal = "Bioinformatics",

issn = "1367-4803",

publisher = "Oxford University Press",

number = "1",

}

Azer, ES, Mehrabadi, FR, Malikić, S, Li, XC, Bartok, O, Litchfield, K, Levy, R, Samuels, Y, Schäffer, AA, Gertz, ME, Day, C-P, Pérez-Guijarro, E, Marie, K, Lee, MP, Merlino, G, Ergun, F & Sahinalp, SC 2020, 'PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem', Bioinformatics, vol. 36, no. 1, pp. i169–i176. https://doi.org/10.1093/bioinformatics/btaa464

TY - JOUR

T1 - PhISCS-BnB

T2 - a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem

AU - Azer, Erfan Sadeqi

AU - Mehrabadi, Farid Rashidi

AU - Malikić, Salem

AU - Li, Xuan Cindy

AU - Bartok, Osnat

AU - Litchfield, Kevin

AU - Levy, Ronen

AU - Samuels, Yardena

AU - Schäffer, Alejandro A.

AU - Gertz, Michael E

AU - Day, Chi-Ping

AU - Pérez-Guijarro, Eva

AU - Marie, Kerrie

AU - Lee, Maxwell P.

AU - Merlino, Glenn

AU - Ergun, Funda

AU - Sahinalp, S. Cenk

PY - 2020/7/13

Y1 - 2020/7/13

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

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

UR - http://dx.doi.org/10.1093/bioinformatics/btaa464

U2 - 10.1093/bioinformatics/btaa464

DO - 10.1093/bioinformatics/btaa464

M3 - Article

SN - 1367-4803

VL - 36

SP - i169–i176

JO - Bioinformatics

JF - Bioinformatics

IS - 1

ER -

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

Abstract

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this