DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2019.22

A Combinatorial Approach for Single-cell Variant Detection via Phylogenetic Inference

Authors: Mohammadamin Edrisi, Hamim Zafar, and Luay Nakhleh

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)

Abstract

Single-cell sequencing provides a powerful approach for elucidating intratumor heterogeneity by resolving cell-to-cell variability. However, it also poses additional challenges including elevated error rates, allelic dropout and non-uniform coverage. A recently introduced single-cell-specific mutation detection algorithm leverages the evolutionary relationship between cells for denoising the data. However, due to its probabilistic nature, this method does not scale well with the number of cells. Here, we develop a novel combinatorial approach for utilizing the genealogical relationship of cells in detecting mutations from noisy single-cell sequencing data. Our method, called scVILP, jointly detects mutations in individual cells and reconstructs a perfect phylogeny among these cells. We employ a novel Integer Linear Program algorithm for deterministically and efficiently solving the joint inference problem. We show that scVILP achieves similar or better accuracy but significantly better runtime over existing methods on simulated data. We also applied scVILP to an empirical human cancer dataset from a high grade serous ovarian cancer patient.

Cite as

Mohammadamin Edrisi, Hamim Zafar, and Luay Nakhleh. A Combinatorial Approach for Single-cell Variant Detection via Phylogenetic Inference. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{edrisi_et_al:LIPIcs.WABI.2019.22,
  author =	{Edrisi, Mohammadamin and Zafar, Hamim and Nakhleh, Luay},
  title =	{{A Combinatorial Approach for Single-cell Variant Detection via Phylogenetic Inference}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.22},
  URN =		{urn:nbn:de:0030-drops-110525},
  doi =		{10.4230/LIPIcs.WABI.2019.22},
  annote =	{Keywords: Mutation calling, Single-cell sequencing, Integer linear programming, Perfect phylogeny}
}

Search Results

Documents authored by Edrisi, Mohammadamin

A Combinatorial Approach for Single-cell Variant Detection via Phylogenetic Inference

Abstract

Cite as

Thanks for your feedback!

Could not send message