MULTIPLE SEQUENCE ALIGNMENT USING AN EXHAUSTIVE AND GREEDY ALGORITHM
| Autor: | Yi Wang, Kuo Bin Li |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
Multiple sequence alignment
business.industry Computer science Sequence alignment Sequence Analysis DNA Machine learning computer.software_genre Biochemistry Pattern Recognition Automated Computer Science Applications Software Sequence Analysis Protein Benchmark (computing) Artificial intelligence business Greedy algorithm Sequence Alignment Molecular Biology computer Algorithm Algorithms Conserved Sequence Java Programming Language |
| Zdroj: | Journal of Bioinformatics and Computational Biology. :243-255 |
| ISSN: | 1757-6334 0219-7200 |
| Popis: | We describe an exhaustive and greedy algorithm for improving the accuracy of multiple sequence alignment. A simple progressive alignment approach is employed to provide initial alignments. The initial alignment is then iteratively optimized against an objective function. For any working alignment, the optimization involves three operations: insertions, deletions and shuffles of gaps. The optimization is exhaustive since the algorithm applies the above operations to all eligible positions of an alignment. It is also greedy since only the operation that gives the best improving objective score will be accepted. The algorithms have been implemented in the EGMA (Exhaustive and Greedy Multiple Alignment) package using Java programming language, and have been evaluated using the BAliBASE benchmark alignment database. Although EGMA is not guaranteed to produce globally optimized alignment, the tests indicate that EGMA is able to build alignments with high quality consistently, compared with other commonly used iterative and non-iterative alignment programs. It is also useful for refining multiple alignments obtained by other methods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|