A Tool for Structure Alignment of Molecules

Authors: Pei-Ken Chang, Chien-Cheng Chen and Ming Ouhyoung
Department of Computer Science and Information Engineering, National Taiwan University

Proc. of IEEE Sixth International Symposium on Multimedia Software Engineering (IEEE-MSE2004) Special Session on Bioinformatics, pp. 354-361, Miami, USA, Dec. 2004. (ISBN 0-7695-2217-3)
ABSTRACT

A novel tool is proposed to align two molecules (not just proteins) based on their 3D structural data, and the user can observe the result of alignment visually via the tool. Most existing tools are designed only for alignment of proteins. Here, a new tool is developed to address shared structural features between protein structures and tRNA structures, that is, molecular mimicry, although they are two very different types of molecules.

In order to align two molecules A and B, Geometric Hashing is applied to globally find initial matching of approximately overlapped atoms, thus parts of molecule A can be matched to parts of molecule B. Next, a fine tuning process is introduced, which is based on local optimization of overlapped parts, and the Iterative Closest Point (ICP) is used until the number of overlapped atoms within a given distance threshold can not be increased any more. The results show that our method is useful to structurally align two molecules, not restricted to align two proteins only. Besides, our tool outperforms in terms of RMSD and number of matched atom pairs in comparison to other tools.
Algorithms

The alignment problem between two molecules A and B is solved in two steps: Geometric Hashing and a fine tuning process.
  • Geometric Hashing globally finds initial matching of approximately overlapped atoms.
  • Secondly, the fine tuning process is based on local optimization of overlapped parts, and the Iterative Closest Point (ICP) algorithm is used until the number of overlapped atoms within a given distance threshold can not be increased any more.

Experimental Results

  1. The Molecular Alignment Problem
  2. Comparison with Other Alignment Tools

Conclusion

A novel tool is developed to align two molecules based on 3D structural data. In contrast to other algorithms, it takes more computation time to align two molecules by our tool. However, other tools might be restricted to align two proteins. The experiments are conducted based on the data from the PDB and demonstrate that the proposed tool is useful and versatile.

The first experiment is the molecular alignment problem. Given two molecules, our tool will generate the rotation matrix and translation vector so that the above two molecules are optimally aligned. In our experiments, the results are the same, no matter where we randomly place the molecules in a different location with different orientation.

In the second experiment, several protein pairs are used to compare the results with four popular alignment tools, namely Yale, Dali, CE and Lund methods. Our tool performs the best in terms of RMSD and number of matched atom pairs.
Tools/Downloads

The proposed tool
* version 1.00 05/07/2004 350KB The first released version
* version 2.00 10/15/2004 357KB
Platform: Windows 2000/XP
ReadMe.ppt
The paper

Last Update: Nov 28 2004