Protein Structure Alignment Using Dynamic Programming and Iterative Improvement

this paper, we consider the protein structure alignment problem, which is a very important problem in molecular biology. Since an outline of protein structure is represented by a sequence of points in three-dimensional space, this problem is defined as the following geometric pattern matching problem: given two point sequences P and Q in three-dimensions and a real number ffi ? 0, find a maximum-cardinality set of point pairs such that the distance between each pair is at most ffi under the condition that any translation and rotation can be applied to P . Since it is very difficult to solve this problem exactly, we consider algorithms that solve it approximately. We propose three algorithms: BASICALIGN, RANDALIGN and FRAGALIGN whose worst case time complexities are O(