Tagged ICP: An Iterative Closest Point Algorithm with Metadata Knowledge for Improved Matching of 3D Protein Structures
Peter Ankomah, Peter Vangorp, Ardhendu Behera, Yonghuai Liu · Edge Hill University Research Information Repository (Edge Hill University) · 2020
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