LNA: Fast Protein Classification Using A Laplacian Characterization of Tertiary Structure

Nicolas Bonnel (1) , Pierre-François Marteau (1)

1 SEASIDE - SEarch, Analyze, Synthesize and Interact with Data Ecosystems

In the last two decades, a lot of protein 3D shapes have been discovered, characterized and made available thanks to the Protein Data Bank (PDB), that is nevertheless growing very quickly. New scalable methods are thus urgently required to search through the PDB efficiently. We present in this paper an approach entitled LNA (Laplacian Norm Alignment) that performs structural comparison of two proteins with dynamic programming algorithms. This is achieved by characterizing each residue in the protein with scalar features. The feature values are calculated using a Laplacian operator applied on the graph corresponding to the adjacency matrix of the residues. The weighted Laplacian operator we use estimates at various scales local deformations of the topology where each residue is located. On some benchmarks widely shared by the community we obtain qualitatively similar results compared to other competing approaches, but with an algorithm one or two order of magnitudes faster. 180,000 protein comparisons can be done within 1 seconds with a single recent GPU, which makes our algorithm very scalable and suitable for real-time database querying across the Web.

Mots clés: PDB; Laplacian; protein; tertiary structure; GPU; Accuracy; Dynamic programming; Graphics processing unit; Heuristic algorithms; Laplace equations; Three dimensional displays

Domaines: Bio-informatique [q-bio.QM]; Bio-Informatique, Biologie Systémique [q-bio.QM]

Nicolas Bonnel, Pierre-François Marteau. LNA: Fast Protein Classification Using A Laplacian Characterization of Tertiary Structure. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012, 9 Issue: 5, pp.1451 - 1458. ⟨10.1109/TCBB.2012.64⟩. ⟨hal-00639663⟩