Name
Abstract | ||
|---|---|---|
Motivation: Recently, the concept of the constrained sequence alignment was proposed to incorporate the knowledge of biologists about structures/functionalities/consensuses of their datasets into sequence alignment such that the user-specified residues/nucleotides are aligned together in the computed alignment. The currently developed programs use the so-called progressive approach to efficiently obtain a constrained alignment of several sequences. However, the kernels of these programs, the dynamic programming algorithms for computing an optimal constrained alignment between two sequences, run in O(γn2) memory, where γ is the number of the constraints and n is the maximum of the lengths of sequences. As a result, such a high memory requirement limits the overall programs to align short sequences~only. Results: We adopt the divide-and-conquer approach to design a memory-efficient algorithm for computing an optimal constrained alignment between two sequences, which greatly reduces the memory requirement of the dynamic programming approaches at the expense of a small constant factor in CPU time. This new algorithm consumes only O(αn) space, where α is the sum of the lengths of constraints and usually α n in practical applications. Based on this algorithm, we have developed a memory-efficient tool for multiple sequence alignment with constraints. Availability: http://genome.life.nctu.edu.tw/MUSICME Contact: cllu@mail.nctu.edu.tw |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1093/bioinformatics/bth468 | Bioinformatics |
Keywords | Field | DocType |
multiple sequence alignment | Sequence alignment,Dynamic programming,High memory,Computer science,CPU time,Algorithm,Needleman–Wunsch algorithm,Bioinformatics,Multiple sequence alignment | Journal |
Volume | Issue | ISSN |
21 | 1 | 1367-4803 |
Citations | PageRank | References |
13 | 0.62 | 20 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chin Lung Lu | 1 | 423 | 34.59 |
| Yen Pin Huang | 2 | 30 | 1.48 |