Mathematical Culture and Thought

Mathematical Culture and Thought

Approximate Algorithms for Genealogical Tree Reconstruction: Applications of Theoretical Computer Science in Biology and Bioinformatics

Document Type : Review

Author
M. H. Foroughmand
Department of Mathematical Sciences, Sharif University of Technology, Iran
10.30504/mct.2022.320
Abstract
The reconstruction of genealogical trees is a longstanding problem in biology, which aims to illustrate the similarities among organisms. Existing algorithms for this task are generally heuristic, relying on the understanding and intuition of their creators. Consequently, there is no guarantee of their optimality or the extent of their effectiveness. On the other hand, approximate algorithms, while not necessarily yielding the optimal solution (likely an impossibility), can provide a range indicating the distance between their solution and the optimal one. In this article, we explore an approximate algorithm for reconstructing tumor genealogical trees. This algorithm is derived from modifications [1] to the previously proposed Steiner tree problem algorithm. Additionally, we examine one of the applications of theoretical computer science in designing algorithms for bioinformatics problems.
Keywords
genealogical tree reconstruction
classification problem
application of computer science in bioinformatics
Subjects
[1] Alon, N., Chor, B., Pardi, F., Rapoport, A., Approximate maximum parsimony and ancestral
maximum likelihood, IEEE/ACM Transactions on Computational Biology and Bioinformatics,
7 (2008), 183–187.
[2] Berman, P., Ramaiyer, V., Improved approximations for the Steiner tree problem, Journal
of Algorithms, 17 (1994), 381–408.
[3] A. Borchers, Du, D.-Z., Thek-Steiner ratio in graphs, SIAM J. Comput., 26 (1997), 857–
869.
[4] Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L., An improved LP-based approximation for
steiner tree, in Proceedings of the Forty-Second ACM Symposium on Theory of Computing
(Massachusetts, 2010), Association for Computing Machinery, New York, 2010, 583–592.
[5] Chlebík, M., Chlebíková, J., The Steiner tree problem on graphs: Inapproximability results,
Theoretical Computer Science, 406 (2008), 207–214.
[6] Karp, R. M., Reducibility among combinatorial problems, in Complexity of Computer
Computations, R. E. Miller, J. W. Thatcher, J. D. Bohlinger, eds., Springer, New York,
1972, 85–103.
[7] Robins, G., Zelikovsky, A., Tighter bounds for graph Steiner tree approximation, SIAM J.
Discrete Math., 19 (2005), 122–134.
[8] Zelikovsky, A., An 11/6-approximation algorithm for the Steiner problem on graphs, in
Annals of Discrete Mathematics, volume 51, Elsevier, 1992, 351–354.

  • Receive Date 05 August 2019
  • Revise Date 21 July 2020
  • Accept Date 22 July 2020
  • Publish Date 20 February 2022