OPTIMAL SEQUENCE ALIGNMENT ALLOWING FOR LONG GAPS

A new algorithm for optimal sequence alignment allowing for long insertions and deletions is developed. The algorithm requires O((L+C)MN) computational steps, O(LN) primary memory and O(MN) secondary memory storage, where M and N(M≥N) are sequence lengths, L (typically L≤3) is the number of segment specifying the gap weighting function, and C is a constant. We have also modified our earlier traceback algorithm so that it finds all and only the optimal alignments in a compact form of a directed graph. The current versions accept a set of aligned sequences as input, which facilitates multiple sequence alignment by some iterative procedures. © 1990 Society for Mathematical Biology.