Dr. Arno Formella, Computer Science Department

Approximate point set match (2D and 3D)


Given a set of points as search space (for instance, a large protein) and a set of points as search pattern (for instance, a known active zone), the implemented programm finds all locations, including the necessary rigid motion transformations according to some distance measure such as rms, where the pattern can be aligned within the search space. Besides complete matches, the program can determine the largest partial match as well.
  • The images show the two locations where the 34 atoms of the active zone have been encountered in the protein 1IRU consisting of 47562 atoms.

    IRU zona global zoom

  • The image shows the location of the best partial match (for the example the same zone as above was taken, but 6 atoms have been moved slightly).



  • The image shows the five best locations where the five C-alpha atoms of the zone have been found in the protein.



Without going into details, the runtimes to obtain all the results shown above were in the range of seconds.

Publications:

A. Formella. Approximate Point Set Match for Partial Protein Structure Alignments. Proceedings of Bioinformatics: Knowledge Discovery in Biology (BKDB2005) , p. 53-57, Lisboa, June 2005.



© Arno Formella, last update: June 22, 2005

e-mail: formella@uvigo.es