Non-sequential Protein Structure Alignment Based On AFPs

With the successful completion of the human genome project,known as the Human Science Monthly Program,Life Sciences has entered a new era-the post-genome era.The acquisition of gene sequences provides the basis for understanding the mysteries of organisms,but at the same time it is also found that the biological function can't be systematically described from the perspective of gene sequences.Protein not is the main component of the composition for life,but also the main performer of life activities.It has important guiding significance for us to understand the inherent function of the organismFinding the similarity between protein structures is helpful for people to understand the similarity between functions,to discover remote homology relationships,and even to discover the evolutionary mechanisms of protein structures.The protein structure is developed to find the protein similarity,and is has become an indispensable tool for bioinformatics.More and more protein structure alignment methods have been proposed,such as FATCAT,CE and so on.However,many of the protein structure alignment methods are based on sequence limitations and do not detect non-sequential similarity between the protein structures which are related through circular permutation,or proteins that evolved from different ancestors owing to convergent evolution.Based on the above background,this paper briefly introduces the current 7 non-sequential protein structure alignment methods,in this work,a new non-sequential protein structure alignment method based on Aligned Fragment Pairs(AFPs)and the maximal clique is proposed.Different from other AFP-based protein structure alignment methods,our method is based on variable length AFPs which can better represent the local structure similarities and can also speed up the computation.In addition,we use AFP's spatial information to filter the noisy AFP,and obtain high-quality AFP.Then,a graph is built to represent the relationship between all the “good” AFPs.If two AFPs can be aligned at the same time,an edge is added to the graph.A high quality maximal clique of the graph is found to produce the initial alignment.Finally,in order to avoid the limitations of dynamic programming algorithms in non-sequential structural comparisons,we use a greedy algorithm to optimize the initial alignment to obtain the final alignment results.The experiments show that,compared with seven non-sequential methods,except DEDAL which is a non-rigid body method,and MICAN which uses secondary structure information,the proposed method usually produces more correctly aligned residue pairs than the other non-sequential alignment methods.In addition,compared with the structure alignment methods based on constant length AFP,implementation efficiency of our method has been greatly improved by using the variable length AFPs.