Finding similar regions in many sequences
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 73-96 |
| Journal / Publication | Journal of Computer and System Sciences |
| Volume | 65 |
| Issue number | 1 |
| Publication status | Published - 2003 |
Link(s)
Abstract
Algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems. Assume that we are given n DNA sequences s 1,...,s n. The Consensus Patterns problem, which has been widely studied in bioinformatics research, in its simplest form, asks for a region of length L in each s i, and a median string s of length L so that the total Hamming distance from s to these regions is minimized. We show that the problem is NP-hard and give a polynomial time approximation scheme (PTAS) for it. We then present an efficient approximation algorithm for the consensus pattern problem under the original relative entropy measure. As an interesting application of our analysis, we further obtain a PTAS for a restricted (but still NP-hard) version of the important consensus alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence. © 2002 Elsevier Science (USA) All rights reserved.
Research Area(s)
- Approximation algorithms, Computational biology, Consensus alignment, Consensus patterns
Citation Format(s)
Finding similar regions in many sequences. / Li, Ming; Ma, Bin; Wang, Lusheng.
In: Journal of Computer and System Sciences, Vol. 65, No. 1, 2003, p. 73-96.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
