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.