Fast Local Alignment of Protein Pockets (FLAPP): A System-Compiled Program for Large-Scale Binding Site Alignment

Protein function is a direct consequence of its sequence, structure, and the arrangement at the binding site. Bioinformatics using sequence analysis is typically used to gain a first insight into protein function. Protein structures, on the other hand, provide a higher resolution platform into understanding functions. As the protein structural information is increasingly becoming available through experimental structure determination and through advances in computational methods for structure prediction, the opportunity to utilize these data is also increasing. Structural analysis of small molecule ligand binding sites in particular provides a direct and more accurate window to infer protein function. However, it remains a poorly utilized resource due to the huge computational cost of existing methods that make large-scale structural comparisons of binding sites prohibitive. Here, we present an algorithm called FLAPP that produces very rapid atomic level alignments. By combining clique matching in graphs and the power of modern CPU architectures, FLAPP aligns a typical pair of binding sites at ∼12.5 ms using a single CPU core, ∼1 ms using 12 cores on a standard desktop machine, and performs a PDB-wide scan in 1-2 min. We perform rigorous validation of the algorithm at multiple levels of complexity and show that FLAPP provides accurate alignments. We also present a case study involving vitamin B12 binding sites to showcase the usefulness of FLAPP for performing an exhaustive alignment-based PDB-wide scan. We expect that this tool will be invaluable to the scientific community to quickly align millions of site pairs on a normal desktop machine to gain insights into protein function and drug discovery for drug target and off-target identification and polypharmacology.