Samo: a protein structure alignment tool based on multiple objective optimization

• Version 0.4.1
• Last updated: February 10, 2009

References#

• Luonan Chen, Ling-Yun Wu, Ruiqi Wang, Yong Wang, Shuihua Zhang and Xiang-Sun Zhang. Comparison of protein structures by multi-objective optimization. Genome Informatics, Vol. 16, No. 2, pp. 114-124, 2005.
• Luonan Chen, Ling-Yun Wu, Yong Wang, Shi-Hua Zhang and Xiang-Sun Zhang. Revealing divergent evolution, identifying circular permutations and detecting active-sites by protein structure comparison. BMC Structural Biology, Vol. 6, 18, 2006. (PubMed: 16948858)

Method#

Protein structure alignment is one of the important computational problems in molecular biology and plays a key role in protein structure prediction, fold family classification, motif finding, phylogenetic tree reconstruction and protein docking.

We propose a novel method for solving the structure alignment problem in an accurate manner at the amino acid level, based on a decomposition technique.

We define the structure alignment as a multi-objective optimization problem with both integer and continuous variables, i.e., maximizing the matching number of proteins and minimizing their root mean square distance.

By exploiting the special structure of the protein alignment, the original problem is decomposed into two subproblems: one linear programming subproblem (LPS) for the protein matching and one weighted least square subproblem (LSS) for coordinate transformation.

A very efficient algorithm is developed for optimizing LPS and LSS. By controling a single distance-related parameter, theoretically we can obtain a variety of optimal alignments corresponding to different optimal matching patterns, i.e., from a global alignment with a large matching portion to a local alignment with a small matching portion.

Software#

This version of the program is in very preliminary stage and provided just for testing purpose. The program is still under development.

• Samo-0.4.1.zip

Data#

• Data.zip