back

APPROXIMATE 2D AND 3D POINT SET MATCH

Simulation, Optimization, and Approximation

Approximate point set match is the task to align a search pattern represented by a set of 2D or 3D points in a, usually large, search space consisting of 2D or 3D points as well. The challenge is not to find only perfect matches, but allowing certain types of flexibility of the search pattern when embedded in the search space. The match itself might be only approximative, in other words, some deviation between the pattern and its counterpart in the search space is allowed. The measurement of the deviation can be based on the root mean square (RMSD) distance, but other distance functions (like average distance or maximum distance) might be of interest as well.

One example application is the search for known substructures of protein molecules in a database of proteins. However, approximate point set match has many other possible applications.

 

  • We have implemented an application psm which finds substructures in proteins. Some results:
    • The images show two locations where the 34 atoms of the active zone have been encountered in the protein 1IRU consisting of 47562 atoms. One is the perfect match (where the zone was cut) and one is an approximate match close by. The last image shows the optimal alignment.
      IRU zona global zoom alignment
       
    • 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.
       
  • psm in its server version is part of the algorithm suite of the Superimposé Web server for structural searches in protein data accessible at http://bioinformatics.charite.de/superimpose at the Charité Berlin, Germany.


Publications


People Involved


Student Work


Press Articles


Resources


Partners

More about Engineering of Advanced Materials
Engineering of Advanced Materials
Ir a web
More about Charité-Universitätsmedizin
Charité-Universitätsmedizin
Ir a web
More about Laboratorio de Informática Aplicada
Laboratorio de Informática Aplicada
Ir a web