Abstract
In this paper, we propose a simple algorithm which can automatically assign secondary structures in a protein using a list of nitrogen (N), carbon (C) and oxygen (O) coordinates on its backbone, which can be modeled as sparse points in three dimensional space. Our algorithm has two stages. In the first stage, it determines hydrogen bonds based on pair-wise distances between N and O atoms of difference residues. Then a fragment of consecutive residues is considered as a candidate of α-helix/β-sheet if it follows a specific pattern on the linking of hydrogen bonds. Moreover, if there are at least four CO vectors that are parallel in this fragment, then this fragment is an α-helix; otherwise, it is considered as a β-sheet. A brute-force implementation of the above algorithm requires O(n 2) time, where n is the number of residues. With the help of multidimensional divide-and-conquer approach commonly used in computational geometry, we reduce the time complexity to O (n log2 n + m) , where m is the number of identified hydrogen bonds. Our experimental results show that our results are comparable with those obtained by the DSSP, which is currently the most widely used tool.