Cluster-Distribute-Align-Merge: A General Algorithm to Speed Up Multiple Sequence Alignment on Multi-Core Computers

摘要

We present a general algorithm to speed up multiple sequence alignment on modern multi-core computers. This algorithm is implemented in a software called CDAM. By clustering, CDAM partitions a large-scale alignment problem into smaller and more tractable sub-problems, which can be solved by existing alignment algorithms in parallel. The aligned clusters are then merged to form a solution to the original alignment problem. By performance evaluation on an 8-core computer using the classical benchmarks, BAliBASE, PREFAB, IRMBASE, and OXBench, and twenty-eight artificially generated datasets, it is shown that CDAM provides significant performance improvement with reasonable loss of accuracy. In some cases, a gain in accuracy is observed. The CDAM program, source code, and test data are freely available for academic users at http://aca.hnu.cn/CDAM/.