Aligning sequences via an evolutionary tree : Complexity and approximation

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

42 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
PublisherPubl by ACM
Pages760-769
ISBN (Print)897916638
Publication statusPublished - 1994
Externally publishedYes

Publication series

Name
ISSN (Electronic)0734-9025

Conference

TitleProceedings of the 26th Annual ACM Symposium on the Theory of Computing
CityMontreal, Que, Can
Period23 - 25 May 1994

Abstract

We study the following fundamental problem in computational molecular biology: Given a set of DNA sequences representing some species and a phylogenetic tree depicting the ancestral relationship among these species, compute an optimal alignment of the sequences by the means of constructing a minimum-cost evolutionary tree. The problem is an important variant of multiple sequence alignment, and is widely known as tree alignment. A more generalized version of the problem, called generalized tree alignment in this paper, is that we are given the DNA sequences only and still have to construct a minimum-cost evolutionary tree. The paper presents some hardness results as well as approximation algorithms. It is shown that tree alignment is NP-hard and generalized tree alignment is MAX SNP-hard. On the positive side, we design an efficient approximation algorithm with performance ratio 2 for tree alignment. The algorithm is then extended to a polynomial-time approximation scheme. The construction actually works for Steiner trees in any metric space, and thus implies a polynomial-time approximation scheme for planar Steiner trees under a given topology (with any constant degree). To our knowledge, this is the first polynomial-time approximation scheme in the fields of computational biology and Steiner trees. The contrast between the approximability of tree alignment and generalized tree alignment shows that a phylogenetic tree can indeed help in multiple alignment. The approximation algorithms may be useful in evolutionary genetics practice as they can provide a good initial alignment for the iterative method in [24].

Citation Format(s)

Aligning sequences via an evolutionary tree : Complexity and approximation. / Jiang, Tao; Lawler, Eugene L.; Wang, Lusheng.

Conference Proceedings of the Annual ACM Symposium on Theory of Computing. Publ by ACM, 1994. p. 760-769.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review