Tagged-ICP: An Iterative Closest Point Algorithm with Metadata Knowledge for Improved Matching of 3D Protein Structures

Three-dimensional shapes are important in representing physical objects in digital form. This digital
representation is useful in applications in numerous fields including chemistry, biology, and engineering. The
benefits in analyzing and processing such 3D digital data have given rise to vast amounts of available 3D data
and related applications.
In recent times, techniques for determining the functional and structural relationships amongst proteins
consider the whole 3D structure (spatial coordinates), proceeding from earlier techniques that were based
on sequence information. However, techniques considering the 3D structure of all atomic positions of the
protein are too demanding for fast similarity searches especially when the protein is made up of very large
numbers of atoms.
Iterative Closest Point (ICP) is the standard algorithm for performing 3D shape matching tasks. ICP
has several issues that can affect the process of 3D shape matching. These include the need for an initial
transformation to ensure an optimal match, inability of algorithm to converge when rotations are large, and
computational cost and complexity of the distance calculation.
We propose an improvement of the ICP algorithm, Tagged-ICP for matching 3D protein structures that
takes into consideration known feature descriptions of the points. The search for correspondence in our
algorithm matches atoms based on their meta data (atom types), making this approach more meaningful.
Our algorithm also reduces the number of distance calculations by a factor depending on the partition. The
neighbourhood information also increases the partitions and reduces the size of the search space even further.
Our experimental results based on the publicly accessible Protein Data Bank show that matching becomes
inherently meaningful and the complexity of the distance calculation is reduced. Our results also demonstrate
improvements in speed, accuracy and convergence on larger rotations over the standard ICP algorithm