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!
cited_by cdi_FETCH-LOGICAL-c456t-f86d5168cfdad13070fe1078ba3433d6bba334a6287fd845bfb115a94602b7fd3
cites cdi_FETCH-LOGICAL-c456t-f86d5168cfdad13070fe1078ba3433d6bba334a6287fd845bfb115a94602b7fd3
container_end_page i176
container_issue Supplement_1
container_start_page i169
container_title Bioinformatics (Oxford, England)
container_volume 36
creator 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
description 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
doi_str_mv 10.1093/bioinformatics/btaa464
format article
fullrecord <record><control><sourceid>proquest_TOX</sourceid><recordid>TN_cdi_pubmedcentral_primary_oai_pubmedcentral_nih_gov_7355310</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><oup_id>10.1093/bioinformatics/btaa464</oup_id><sourcerecordid>2423537190</sourcerecordid><originalsourceid>FETCH-LOGICAL-c456t-f86d5168cfdad13070fe1078ba3433d6bba334a6287fd845bfb115a94602b7fd3</originalsourceid><addsrcrecordid>eNqNUU1v1DAQtRCIfsBfqHzkEmrHH8lyQKIroJUqgVQ4W2PH3hgldrCdSvvvcbXLit64zIxm3rw3mofQFSXvKdmwa-2jDy6mGYo3-VoXAC75C3ROmewa3lP68lQTdoYucv5FCBFEyNfojLVSdEz052j4Pt49bB-am3DzAQN2kAvWCYIZMYQB67jWCNMuJl_GGVdFXEaLF5ucNQWXda6dZdxPcWfDHidrYsglrab4GPCSop7s_Aa9cjBl-_aYL9HPL59_bG-b-29f77af7hvDhSyN6-UgqOyNG2CgjHTEWUq6XgPjjA1S14JxkG3fuaHnQjtNqYANl6TVtcUu0ccD77Lq2Q7GhpJgUkvyM6S9iuDV80nwo9rFR1V_IRglleDdkSDF36vNRc0-GztNEGxcs2p5ywTr6OYJKg9Qk2LOybqTDCXqySL13CJ1tKguXv175GntrycVQA-AuC7_S_oHloOnHg</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2423537190</pqid></control><display><type>article</type><title>PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem</title><source>Oxford University Press Open Access</source><creator>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</creator><creatorcontrib>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</creatorcontrib><description>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 &lt;4 h. The resulting phylogeny agrees with and extends the published results by providing a more detailed picture on the clonal evolution of the tumor. Availability and implementation https://github.com/algo-cancer/PhISCS-BnB. Supplementary information Supplementary data are available at Bioinformatics online.</description><identifier>ISSN: 1367-4803</identifier><identifier>EISSN: 1367-4811</identifier><identifier>DOI: 10.1093/bioinformatics/btaa464</identifier><identifier>PMID: 32657358</identifier><language>eng</language><publisher>England: Oxford University Press</publisher><subject>Algorithms ; Genomic Variation Analysis ; Humans ; Markov Chains ; Neoplasms - genetics ; Phylogeny ; Sequence Analysis ; Software</subject><ispartof>Bioinformatics (Oxford, England), 2020-07, Vol.36 (Supplement_1), p.i169-i176</ispartof><rights>Published by Oxford University Press 2020. 2020</rights><rights>Published by Oxford University Press 2020.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c456t-f86d5168cfdad13070fe1078ba3433d6bba334a6287fd845bfb115a94602b7fd3</citedby><cites>FETCH-LOGICAL-c456t-f86d5168cfdad13070fe1078ba3433d6bba334a6287fd845bfb115a94602b7fd3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.ncbi.nlm.nih.gov/pmc/articles/PMC7355310/pdf/$$EPDF$$P50$$Gpubmedcentral$$H</linktopdf><linktohtml>$$Uhttps://www.ncbi.nlm.nih.gov/pmc/articles/PMC7355310/$$EHTML$$P50$$Gpubmedcentral$$H</linktohtml><link.rule.ids>230,314,727,780,784,885,1604,27924,27925,53791,53793</link.rule.ids><linktorsrc>$$Uhttps://dx.doi.org/10.1093/bioinformatics/btaa464$$EView_record_in_Oxford_University_Press$$FView_record_in_$$GOxford_University_Press</linktorsrc><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/32657358$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink></links><search><creatorcontrib>Sadeqi Azer, Erfan</creatorcontrib><creatorcontrib>Rashidi Mehrabadi, Farid</creatorcontrib><creatorcontrib>Malikić, Salem</creatorcontrib><creatorcontrib>Li, Xuan Cindy</creatorcontrib><creatorcontrib>Bartok, Osnat</creatorcontrib><creatorcontrib>Litchfield, Kevin</creatorcontrib><creatorcontrib>Levy, Ronen</creatorcontrib><creatorcontrib>Samuels, Yardena</creatorcontrib><creatorcontrib>Schäffer, Alejandro A</creatorcontrib><creatorcontrib>Gertz, E Michael</creatorcontrib><creatorcontrib>Day, Chi-Ping</creatorcontrib><creatorcontrib>Pérez-Guijarro, Eva</creatorcontrib><creatorcontrib>Marie, Kerrie</creatorcontrib><creatorcontrib>Lee, Maxwell P</creatorcontrib><creatorcontrib>Merlino, Glenn</creatorcontrib><creatorcontrib>Ergun, Funda</creatorcontrib><creatorcontrib>Sahinalp, S Cenk</creatorcontrib><title>PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem</title><title>Bioinformatics (Oxford, England)</title><addtitle>Bioinformatics</addtitle><description>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 &lt;4 h. The resulting phylogeny agrees with and extends the published results by providing a more detailed picture on the clonal evolution of the tumor. Availability and implementation https://github.com/algo-cancer/PhISCS-BnB. Supplementary information Supplementary data are available at Bioinformatics online.</description><subject>Algorithms</subject><subject>Genomic Variation Analysis</subject><subject>Humans</subject><subject>Markov Chains</subject><subject>Neoplasms - genetics</subject><subject>Phylogeny</subject><subject>Sequence Analysis</subject><subject>Software</subject><issn>1367-4803</issn><issn>1367-4811</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><recordid>eNqNUU1v1DAQtRCIfsBfqHzkEmrHH8lyQKIroJUqgVQ4W2PH3hgldrCdSvvvcbXLit64zIxm3rw3mofQFSXvKdmwa-2jDy6mGYo3-VoXAC75C3ROmewa3lP68lQTdoYucv5FCBFEyNfojLVSdEz052j4Pt49bB-am3DzAQN2kAvWCYIZMYQB67jWCNMuJl_GGVdFXEaLF5ucNQWXda6dZdxPcWfDHidrYsglrab4GPCSop7s_Aa9cjBl-_aYL9HPL59_bG-b-29f77af7hvDhSyN6-UgqOyNG2CgjHTEWUq6XgPjjA1S14JxkG3fuaHnQjtNqYANl6TVtcUu0ccD77Lq2Q7GhpJgUkvyM6S9iuDV80nwo9rFR1V_IRglleDdkSDF36vNRc0-GztNEGxcs2p5ywTr6OYJKg9Qk2LOybqTDCXqySL13CJ1tKguXv175GntrycVQA-AuC7_S_oHloOnHg</recordid><startdate>20200701</startdate><enddate>20200701</enddate><creator>Sadeqi Azer, Erfan</creator><creator>Rashidi Mehrabadi, Farid</creator><creator>Malikić, Salem</creator><creator>Li, Xuan Cindy</creator><creator>Bartok, Osnat</creator><creator>Litchfield, Kevin</creator><creator>Levy, Ronen</creator><creator>Samuels, Yardena</creator><creator>Schäffer, Alejandro A</creator><creator>Gertz, E Michael</creator><creator>Day, Chi-Ping</creator><creator>Pérez-Guijarro, Eva</creator><creator>Marie, Kerrie</creator><creator>Lee, Maxwell P</creator><creator>Merlino, Glenn</creator><creator>Ergun, Funda</creator><creator>Sahinalp, S Cenk</creator><general>Oxford University Press</general><scope>CGR</scope><scope>CUY</scope><scope>CVF</scope><scope>ECM</scope><scope>EIF</scope><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7X8</scope><scope>5PM</scope></search><sort><creationdate>20200701</creationdate><title>PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem</title><author>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</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c456t-f86d5168cfdad13070fe1078ba3433d6bba334a6287fd845bfb115a94602b7fd3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Algorithms</topic><topic>Genomic Variation Analysis</topic><topic>Humans</topic><topic>Markov Chains</topic><topic>Neoplasms - genetics</topic><topic>Phylogeny</topic><topic>Sequence Analysis</topic><topic>Software</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Sadeqi Azer, Erfan</creatorcontrib><creatorcontrib>Rashidi Mehrabadi, Farid</creatorcontrib><creatorcontrib>Malikić, Salem</creatorcontrib><creatorcontrib>Li, Xuan Cindy</creatorcontrib><creatorcontrib>Bartok, Osnat</creatorcontrib><creatorcontrib>Litchfield, Kevin</creatorcontrib><creatorcontrib>Levy, Ronen</creatorcontrib><creatorcontrib>Samuels, Yardena</creatorcontrib><creatorcontrib>Schäffer, Alejandro A</creatorcontrib><creatorcontrib>Gertz, E Michael</creatorcontrib><creatorcontrib>Day, Chi-Ping</creatorcontrib><creatorcontrib>Pérez-Guijarro, Eva</creatorcontrib><creatorcontrib>Marie, Kerrie</creatorcontrib><creatorcontrib>Lee, Maxwell P</creatorcontrib><creatorcontrib>Merlino, Glenn</creatorcontrib><creatorcontrib>Ergun, Funda</creatorcontrib><creatorcontrib>Sahinalp, S Cenk</creatorcontrib><collection>Medline</collection><collection>MEDLINE</collection><collection>MEDLINE (Ovid)</collection><collection>MEDLINE</collection><collection>MEDLINE</collection><collection>PubMed</collection><collection>CrossRef</collection><collection>MEDLINE - Academic</collection><collection>PubMed Central (Full Participant titles)</collection><jtitle>Bioinformatics (Oxford, England)</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Sadeqi Azer, Erfan</au><au>Rashidi Mehrabadi, Farid</au><au>Malikić, Salem</au><au>Li, Xuan Cindy</au><au>Bartok, Osnat</au><au>Litchfield, Kevin</au><au>Levy, Ronen</au><au>Samuels, Yardena</au><au>Schäffer, Alejandro A</au><au>Gertz, E Michael</au><au>Day, Chi-Ping</au><au>Pérez-Guijarro, Eva</au><au>Marie, Kerrie</au><au>Lee, Maxwell P</au><au>Merlino, Glenn</au><au>Ergun, Funda</au><au>Sahinalp, S Cenk</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem</atitle><jtitle>Bioinformatics (Oxford, England)</jtitle><addtitle>Bioinformatics</addtitle><date>2020-07-01</date><risdate>2020</risdate><volume>36</volume><issue>Supplement_1</issue><spage>i169</spage><epage>i176</epage><pages>i169-i176</pages><issn>1367-4803</issn><eissn>1367-4811</eissn><abstract>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 &lt;4 h. The resulting phylogeny agrees with and extends the published results by providing a more detailed picture on the clonal evolution of the tumor. Availability and implementation https://github.com/algo-cancer/PhISCS-BnB. Supplementary information Supplementary data are available at Bioinformatics online.</abstract><cop>England</cop><pub>Oxford University Press</pub><pmid>32657358</pmid><doi>10.1093/bioinformatics/btaa464</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 1367-4803
ispartof Bioinformatics (Oxford, England), 2020-07, Vol.36 (Supplement_1), p.i169-i176
issn 1367-4803
1367-4811
language eng
recordid cdi_pubmedcentral_primary_oai_pubmedcentral_nih_gov_7355310
source Oxford University Press Open Access
subjects Algorithms
Genomic Variation Analysis
Humans
Markov Chains
Neoplasms - genetics
Phylogeny
Sequence Analysis
Software
title PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T13%3A58%3A21IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_TOX&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=PhISCS-BnB:%20a%20fast%20branch%20and%20bound%20algorithm%20for%20the%20perfect%20tumor%20phylogeny%20reconstruction%20problem&rft.jtitle=Bioinformatics%20(Oxford,%20England)&rft.au=Sadeqi%20Azer,%20Erfan&rft.date=2020-07-01&rft.volume=36&rft.issue=Supplement_1&rft.spage=i169&rft.epage=i176&rft.pages=i169-i176&rft.issn=1367-4803&rft.eissn=1367-4811&rft_id=info:doi/10.1093/bioinformatics/btaa464&rft_dat=%3Cproquest_TOX%3E2423537190%3C/proquest_TOX%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c456t-f86d5168cfdad13070fe1078ba3433d6bba334a6287fd845bfb115a94602b7fd3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2423537190&rft_id=info:pmid/32657358&rft_oup_id=10.1093/bioinformatics/btaa464&rfr_iscdi=true