Optimal sequence alignment allowing for long gaps |
| |
Authors: | Osamu Gotoh |
| |
Affiliation: | (1) Department of Biochemistry, Saitama Cancer Center Research Institute, 362 Ina-machi, Saitama, Japan |
| |
Abstract: | 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, whereM andN(M≥N) are sequence lengths,L (typicallyL≤3) is the number of segment specifying the gap weighting function, andC 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. Dedicated to Professor Akiyoshi Wada on the occasion of his 60th birthday. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|