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

  • Version 0.4.1
  • Last updated: February 10, 2009



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.


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


Category: Supplementary Software

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
zip 1,671.9 kB 1 14-May-2011 21:45 LingyunWu
zip 76.2 kB 1 14-May-2011 21:46 LingyunWu
zip 81.7 kB 1 14-May-2011 21:46 LingyunWu
zip 83.3 kB 1 14-May-2011 21:46 LingyunWu
zip 82.9 kB 1 14-May-2011 21:46 LingyunWu
zip 507.5 kB 1 14-May-2011 21:45 LingyunWu
pdbSelectCastp.tar.gz 34,330.5 kB 1 14-May-2011 21:46 LingyunWu
« This page (revision-5) was last changed on 20-Nov-2011 22:19 by LingyunWu