License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2018.22
URN: urn:nbn:de:0030-drops-93242
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9324/
Go to the corresponding LIPIcs Volume Portal

Karpov, Nikolai ; Malikic, Salem ; Rahman, Md. Khaledur ; Sahinalp, S. Cenk

A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression

pdf-format:
LIPIcs-WABI-2018-22.pdf (1.0 MB)

Abstract

We introduce a new edit distance measure between a pair of "clonal trees", each representing the progression and mutational heterogeneity of a tumor sample, constructed by the use of single cell or bulk high throughput sequencing data. In a clonal tree, each vertex represents a specific tumor clone, and is labeled with one or more mutations in a way that each mutation is assigned to the oldest clone that harbors it. Given two clonal trees, our multi-labeled tree edit distance (MLTED) measure is defined as the minimum number of mutation/label deletions, (empty) leaf deletions, and vertex (clonal) expansions, applied in any order, to convert each of the two trees to the maximal common tree. We show that the MLTED measure can be computed efficiently in polynomial time and it captures the similarity between trees of different clonal granularity well. We have implemented our algorithm to compute MLTED exactly and applied it to a variety of data sets successfully. The source code of our method can be found in: https://github.com/khaled-rahman/leafDelTED.

BibTeX - Entry

@InProceedings{karpov_et_al:LIPIcs:2018:9324,
  author =	{Nikolai Karpov and Salem Malikic and Md. Khaledur Rahman and S. Cenk Sahinalp},
  title =	{{A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression}},
  booktitle =	{18th International Workshop on Algorithms in  Bioinformatics (WABI 2018)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-082-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{113},
  editor =	{Laxmi Parida and Esko Ukkonen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9324},
  URN =		{urn:nbn:de:0030-drops-93242},
  doi =		{10.4230/LIPIcs.WABI.2018.22},
  annote =	{Keywords: Intra-tumor heterogeneity, tumor evolution, multi-labeled tree, tree edit distance, dynamic programming}
}

Keywords: Intra-tumor heterogeneity, tumor evolution, multi-labeled tree, tree edit distance, dynamic programming
Collection: 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)
Issue Date: 2018
Date of publication: 02.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI