# 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

## Author(s)

## Detail(s)

Original language | English |
---|---|

Title of host publication | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

Publisher | Publ by ACM |

Pages | 760-769 |

ISBN (Print) | 897916638 |

Publication status | Published - 1994 |

Externally published | Yes |

### Publication series

Name | |
---|---|

ISSN (Electronic) | 0734-9025 |

### Conference

Title | Proceedings of the 26th Annual ACM Symposium on the Theory of Computing |
---|---|

City | Montreal, Que, Can |

Period | 23 - 25 May 1994 |

## Link(s)

## 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.

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