Open AccessStudying the History of Tumor Evolution from Single-Cell Sequencing Data by Exploring the Space of Binary Matrices
Author(s) -
Salem Malikić,
Farid Rashidi Mehrabadi,
Erfan Sadeqi Azer,
Mohammad Haghir Ebrahimabadi,
S. Cenk Şahinalp
Publication year - 2021
Publication title -
journal of computational biology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.585
H-Index - 95
eISSN - 1557-8666
pISSN - 1066-5277
DOI - 10.1089/cmb.2020.0595
Subject(s) - optimal binary search tree , tree (set theory) , computer science , binary number , space (punctuation) , binary tree , tree rearrangement , maximum likelihood , data mining , algorithm , theoretical computer science , mathematics , phylogenetic tree , interval tree , tree structure , biology , statistics , combinatorics , biochemistry , arithmetic , gene , operating system
Single-cell sequencing (SCS) data have great potential in reconstructing the evolutionary history of tumors. Rapid advances in SCS technology in the past decade were followed by the design of various computational methods for inferring trees of tumor evolution. Some of the earliest methods were based on the direct search in the space of trees with the goal of finding the maximum likelihood tree. However, it can be shown that instead of searching directly in the tree space, we can perform a search in the space of binary matrices and obtain maximum likelihood tree directly from the maximum likelihood matrix. The potential of the latter tree search strategy has recently been recognized by different research groups and several related methods were published in the past 2 years. Here we provide a review of the theoretical background of these methods and a detailed discussion, which are largely missing in the available publications, of the correlation between the two tree search strategies. We also discuss each of the existing methods based on the search in the space of binary matrices and summarize the best-known single-cell DNA sequencing data sets, which can be used in the future for assessing performance on real data of newly developed methods.