A Heuristic Algorithm for Multiple Sequence Alignment Based on Blocks

Peng Zhao () and Tao Jiang ()
Additional contact information
Peng Zhao: IBM Toronto Lab
Tao Jiang: University of California

Journal of Combinatorial Optimization, 2001, vol. 5, issue 1, No 7, 95-115

Abstract: Abstract Blocked multiple sequence alignment refers to the construction of multiple alignment by first aligning conserved regions into what we call “blocks” and then aligning the regions between successive blocks to form a final alignment. Instead of starting from low order pairwise alignments we propose a new way to form blocks by searching for closely related regions in all input sequences, allowing internal spaces in blocks as well as some degree of mismatch. We address the problem of semi-conserved patterns (patterns that do not appear in all input sequences) by introducing into the process two similarity thresholds that are adjusted dynamically according to the input. A method to control the number of blocks is also presented to deal with the situation when input sequences have so many similar regions that it becomes impractical to form blocks by trying every combination. BMA is an implementation of this approach, and our experimental results indicatethat this approach is efficient, particularly on large numbers of long sequences with well-conserved regions.

Keywords: multiple sequence alignment; conserved blocks; block chaining (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009841718561 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:5:y:2001:i:1:d:10.1023_a:1009841718561

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009841718561

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().