Allison L
Department of Computer Science, Monash University, Australia.
J Theor Biol. 1993 Sep 21;164(2):261-9. doi: 10.1006/jtbi.1993.1153.
Ukkonen's (pair-wise) string alignment technique is extended to the problem of finding an optimal alignment for three strings. The resulting algorithm has worst-case time-complexity O(nd2) and space-complexity O(d3), where the string lengths are ñ and d is the three-way edit-distance based on tree-costs. In practice, the algorithm usually runs in O(n + d3) time. The algorithm is particularly fast when the strings are similar, in which case, d << n. Three-way alignment is an important special case in string alignment. Each internal node in an unrooted, binary evolutionary-tree has three neighbours. The algorithm presented can be used as an iterative step in a heuristic multiple-alignment program for more than three strings.
乌科宁（成对）字符串比对技术被扩展到为三个字符串寻找最优比对的问题。所得算法的最坏情况时间复杂度为O(nd²)，空间复杂度为O(d³)，其中字符串长度为n，d是基于树代价的三路编辑距离。在实际应用中，该算法通常在O(n + d³)时间内运行。当字符串相似时，该算法特别快，在这种情况下，d << n。三路比对是字符串比对中的一个重要特殊情况。无根二叉进化树中的每个内部节点都有三个邻居。所提出的算法可以用作启发式多序列比对程序中用于三个以上字符串的迭代步骤。
