PSNetAl (Protein Structure Network Aligner): a New Algorithm for Multiple Protein Structural Alignment Based on Graph Matching

The increasing rate of depositing new protein sequences and structures to biological databases such as Protein Data Bank (PDB) indicates the importance of structural comparison to explore the evolutionary relationship among different protein families, prediction of function in annotated proteins and classification of protein structure and folds. Due to the high computational cost, protein multiple structural alignment programs in comparison with the conventional multiple sequence alignment programs are slower and represent approximate answers. Therefore, designing new algorithms is an open problem. In this paper, a novel algorithm named PSNetAl for multiple structural alignments of proteins based on graph matching is introduced. PSNetAl inputs are protein structural files in PDB format. Undirected, distance-based graphs are constructed from pdb input files and multiple alignments of graphs are performed by a progressive algorithm. The largest common subgraph as the output of multiple alignment includes the common nodes among all networks. If there is any structural or evolutionary similarity among networks, it will be expected after multiple alignments structural motifs to be present in the largest common subgraph. To evaluate the functionality of PSNetAl, a dataset containing 76 protein families with 50-90% sequence identity and at least 3 members were extracted from HOMSTRAD database. The obtained results show in 67 out of 76 families more than 90% of structural motifs are observed in the largest common subgraph of the multiple alignment.