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 greater than or equal to N) are sequence lengths, L(typically L less than or greater than 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 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.
Gotoh
O
O
Department of Biochemistry, Saitama Cancer Research Institute, Japan.
D000465:Algorithms; D001483:Base Sequence; D002872:Chromosome Deletion; D004251:DNA Transposable Elements; D008433:Mathematics; D008957:Models, Genetic; D012335:RNA, Ribosomal / Q000235:genetics*
D004251:DNA Transposable Elements; D012335:RNA, Ribosomal