Streletc V B, Shindyalov I N, Kolchanov N A, Milanesi L
Institute of Cytology and Genetics, Siberian Department of Russian Academy of Sciences, Novosibirsk.
Comput Appl Biosci. 1992 Dec;8(6):529-34. doi: 10.1093/bioinformatics/8.6.529.
We present a new pairwise alignment algorithm that uses iterative statistical analysis of homologous subsequences. Apart from the classical conversion of the DOT-matrix characteristic of the Needleman-Wunsch algorithm (NW), we used only those matrix elements that corresponded to the most non-random subsequence homologies. The most reliable elements of the DOT-matrix are written to the compact competition matrices. The algorithm then searches for alignment on the base of only these matrix elements. Our algorithm has low storage and memory requirements, but provides a reliable alignment for the sequences of weak homology (or, at least for the homology regions). In such cases classical NW algorithms often produce unreliable results on the level of statistical noise due to accumulation of random matchings throughout the aligned sequences.
我们提出了一种新的成对序列比对算法，该算法使用同源子序列的迭代统计分析。除了对Needleman-Wunsch算法（NW）的点阵矩阵特征进行经典转换外，我们只使用了那些对应于最非随机子序列同源性的矩阵元素。点阵矩阵中最可靠的元素被写入紧凑竞争矩阵。然后，该算法仅基于这些矩阵元素搜索比对。我们的算法具有较低的存储和内存要求，但能为弱同源性序列（或者至少为同源区域）提供可靠的比对。在这种情况下，由于整个比对序列中随机匹配的积累，经典的NW算法在统计噪声水平上常常产生不可靠的结果。
