摘要： 传统双序列比对算法使用动态规划进行序列比对的速度慢，且准确性不高。为解决该问题，提出一种基于布尔逻辑的双序列搜索比对算法。根据一条序列中定长的碱基片段搜索2条序列的相似区，对相似区进行比对，包括相似区中碱基的比对以及子序列与另一条序列的比对，并通过并行执行机制实现加速比对。仿真实验结果表明，该算法具有较高的准确性和较好的实时性。

关键词: 双序列, 布尔逻辑, 搜索比对, 相似区域, 现场可编程门阵列

Abstract: Traditional pairwise sequences alignment algorithms are mostly based on dynamic programming, there are some problems when using dynamic programming to align for its slow speed and low accuracy. Pairwise sequences search and alignment algorithm based on Boolean logic is proposed in this paper. The algorithm searches homologous regions in the pairwise sequence using a fixed-length base fragment in one sequence, and performs the alignment between the homologous regions at once, including the alignment of the bases in the homologous regions and the alignment between the subsequence and the other sequence. It also makes use of concurrent execution mechanism to realize the parallel speed up. Simulation experimental results show that the algorithm has higer real-time and accuracy.

Key words: pairwise sequences, Boolean logic, search and alignment, similar area, Field Programmable Gate Array(FPGA)

中图分类号: 

• TP391.4