In the thesis, we focus on developing frameworks to comparing and aligning multiple geometric shape data. In particular, the research covers two main subjects: (1) Analysis of protein folding trajectories via aligning multiple folding trajectories modeled as multiple high dimensional curves. We develop a novel method, called the EPO algorithm, that can help to mine folding convergent rules dynamically by exploring vital sub-structures and tracking their folding orders. Our EPO algorithm is very effective at identifying structural similarities even when the degree of similarity is low. Hence it can potentially discover critical folding events that cannot yet be discovered by conventional curve alignment algorithms. (2) Multiple protein structure alignment framework: the framework called Spatial Motifs based Protein Multiple Structural Alignment (Smolign) is a complete package including both alignment and superimposition tools. We first introduce a contact-window based motif library of three-dimensional molecular structures. The retrieved motifs are potentially conserved to specific spatial folds and are non-sequentially related. Later on, the structurally similar seeds are selected and extended with a complex heuristic algorithm from this library. Next, we develop an optimal global alignment and superimposition algorithm according to the seeds selected from the first step. due to the similarities between status of protein folding trajectories and protein structures on the contact map representations and based on the successful application of the above techniques in the domain of protein trajectory analysis, we are further extending the EPO to the domain of protein structure alignment. Slightly modified from EPO, our Smolign has the ability to detect multiple correspondences simultaneously, to catch alignments globally, to be able to collect sub-set alignments and to support flexible alignments. Our method yields better alignment results compared to other popular MSTA methods on several protein structure datasets that span various structural folds and represent different protein similarity levels. Of particular interest is that Smolign can discover similarities among protein structures even under very low similarity conditions.
Our research exhibits significantly high efficiency with reasonably high accuracy and will benefit the study of high-throughput protein structure-function evolutionary relationships. A web-based alignment tool as well as a set of downloadable, executable, and detailed alignment results for the datasets used in this thesis are available at http://bio.cse.ohio-state.edu/Smolign and http://sacan.biomed.drexel.edu/Smolign