School of Computer Science and Technology, Xidian University, Xi'an, Shaanxi 710071, China.
Yangtze Delta Region Institute (Quzhou), University of Electronic Science and Technology of China, Quzhou, Zhejiang 324003, China.
Bioinformatics. 2022 Nov 15;38(22):5019-5025. doi: 10.1093/bioinformatics/btac658.
Multiple sequence alignment (MSA) is a fundamental problem in bioinformatics. The quality of alignment will affect downstream analysis. MAFFT has adopted the Fast Fourier Transform method for searching the homologous segments and using them as anchors to divide the sequences, then making alignment only on segments, which can save time and memory without overly reducing the sequence alignment quality. MAFFT becomes slow when the dataset is large.
We made a software, WMSA, which uses the divide-and-conquer method to split the sequences into clusters, aligns those clusters into profiles with the center star strategy and then makes a progressive profile-profile alignment. The alignment is conducted by the compiled algorithms of MAFFT, K-Band with multithread parallelism. Our method can balance time, space and quality and performs better than MAFFT in test experiments on highly conserved datasets.
Source code is freely available at https://github.com/malabz/WMSA/, which is implemented in C/C++ and supported on Linux, and datasets are available at https://github.com/malabz/WMSA-dataset.
Supplementary data are available at Bioinformatics online.
多序列比对（MSA）是生物信息学中的一个基本问题。比对的质量会影响下游分析。MAFFT 采用快速傅里叶变换方法搜索同源片段，并将其用作锚点将序列分割，然后仅在片段上进行比对，这可以节省时间和内存，而不会过度降低序列比对的质量。当数据集较大时，MAFFT 会变得很慢。
我们开发了一个软件 WMSA，它使用分治方法将序列分割成簇，使用中心星策略将这些簇对齐成轮廓，然后进行渐进的轮廓-轮廓比对。对齐是通过 MAFFT 的编译算法、K-Band 和多线程并行完成的。我们的方法可以在时间、空间和质量之间取得平衡，并且在高度保守数据集的测试实验中表现优于 MAFFT。
源代码可在 https://github.com/malabz/WMSA/ 上免费获得，它是用 C/C++ 实现的，并支持 Linux 系统，数据集可在 https://github.com/malabz/WMSA-dataset 上获得。
补充数据可在 Bioinformatics 在线获得。
