Zheng Weihua, Li Kenli, Li Keqin, So Hing Cheung
IEEE/ACM Trans Comput Biol Bioinform. 2017 May-Jun;14(3):634-645. doi: 10.1109/TCBB.2016.2530064. Epub 2016 Feb 15.
Multiple sequence alignment (MSA) is the most common task in bioinformatics. Multiple alignment fast Fourier transform (MAFFT) is the fastest MSA program among those the accuracy of the resulting alignments can be comparable with the most accurate MSA programs. In this paper, we modify the correlation computation scheme of the MAFFT for further efficiency improvement in three aspects. First, novel complex number based amino acid and nucleotide expressions are utilized in the modified correlation. Second, linear convolution with a limitation is proposed for computing the correlation of amino acid and nucleotide sequences. Third, we devise a fast Fourier transform (FFT) algorithm for computing linear convolution. The FFT algorithm is based on conjugate pair split-radix FFT and does not require the permutation of order, and it is new as only real parts of the final outputs are required. Simulation results show that the speed of the modified scheme is 107.58 to 365.74 percent faster than that of the original MAFFT for one execution of the function Falign() of MAFFT, indicating its faster realization.
多序列比对（MSA）是生物信息学中最常见的任务。多比对快速傅里叶变换（MAFFT）是众多多序列比对程序中速度最快的，其比对结果的准确性可与最精确的多序列比对程序相媲美。在本文中，我们从三个方面修改了MAFFT的相关性计算方案，以进一步提高效率。首先，在修改后的相关性计算中使用了基于新型复数的氨基酸和核苷酸表示法。其次，提出了一种带有限制的线性卷积来计算氨基酸和核苷酸序列的相关性。第三，我们设计了一种用于计算线性卷积的快速傅里叶变换（FFT）算法。该FFT算法基于共轭对分裂基FFT，不需要顺序排列，并且由于只需要最终输出的实部，所以是全新的。仿真结果表明，对于MAFFT的函数Falign()执行一次，修改后的方案速度比原始MAFFT快107.58%至365.74%，表明其实现速度更快。
