A TABU SEARCH ALGORITHM FOR POST-PROCESSING MULTIPLE SEQUENCE ALIGNMENT
| Autor: | Tariq Riaz, Kuo Bin Li, Wang Yi |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
Adaptive memory
Sequence Homology Best-first search Biochemistry Tabu search Computer Science Applications Local optimum Artificial Intelligence Search algorithm Beam search Guided Local Search Sequence Alignment Sequence Analysis Molecular Biology Hill climbing Algorithm Algorithms Conserved Sequence Mathematics |
| Zdroj: | Journal of Bioinformatics and Computational Biology. :145-156 |
| ISSN: | 1757-6334 0219-7200 |
| Popis: | Tabu search is a meta-heuristic approach that is proven to be useful in solving combinatorial optimization problems. We implement the adaptive memory features of tabu search to refine a multiple sequence alignment. Adaptive memory helps the search process to avoid local optima and explores the solution space economically and effectively without getting trapped into cycles. The algorithm is further enhanced by introducing extended tabu search features such as intensification and diversification. The neighborhoods of a solution are generated stochastically and a consistency-based objective function is employed to measure its quality. The algorithm is tested with the datasets from BAliBASE benchmarking database. We have observed through experiments that tabu search is able to improve the quality of multiple alignments generated by other software such as ClustalW and T-Coffee. The source code of our algorithm is available at http://www.bii.a-star.edu.sg/~tariq/tabu/. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|