新科学想法 › 学术文库 › 学术文献 › 浏览文献

A Modified Multiple Alignment Fast Fourier Transform with Higher Efficiency

leiyuanwu 添加于 2016-4-1 09:56 | 1514 次阅读 | 0 个评论

作者
Zheng W, Li K, Li K, So HC
摘要
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, to improve MAFFT in efficiency, we modify the correlation computation scheme of MAFFT in three aspects. First, novel complex number based amino acid and nucleotide expressions are utilized in the modified correlation scheme. 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 efficiently linear convolution. The FFT algorithm is based on conjugate pair split-radix FFT and does not require the permutation of order. The FFT is a novel algorithm on real data, in which only the real parts of the final outputs are required. Simulation results show that the speed of the modified scheme is 107.58% to 365.74% faster than that of the original MAFFT for one execution of the function Falign() of MAFFT, which is highly efficient.
详细资料
- 文献种类: Journal Article
- 期刊名称: IEEE/ACM Transactions on Computational Biology and Bioinformatics / IEEE, ACM
- 期刊缩写: IEEE/ACM Trans Comput Biol Bioinform
- 期卷页: 2016年
- ISBN: 1545-5963
学科领域信息系统 » 计算机科学
相关链接 DOI URL