Bipartite graph algorithm with reference frame representation for protein tertiary structure matching

Loading...
Thumbnail Image
Date
2010
Authors
Othman, Fazilah
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Proteins with structural resemblances tend to share similarities in biological functions. This shows the importance of protein structure matching in function determination. Matching between a new structure and a list of target structures with known functions can discover the best target with highest similarity score to indicate the function of the new structure. Previous works have shown that structural matching is computationally intensive and consumes large amount of memory. The problem of space complexity is solved with the implementations of two algorithms: Geometric Hashing Algorithm with Reference Frame (GHARF) and Weighted Bipartite Graph Matching with Reference Frame (WBGMRF). In GHARF, new structural representation for protein Ca backbone is designed using 3 D reference frame which was originally introduced in computer vision for object representation. The experiments have shown the suitability of reference frame for protein structures. Yet, high space complexity due to hash table utilisation in GHARF is unfeasible for larger datasets. Besides, this tec1mique is only effective for matching small proteins. Hence, in WBGMRF, the reference frame is combined with bipartite graph matching technique. A correlation test shows that WBGMRF has a statistically and biologically significant correlation with the benchmark program from the European Bioinformatics Institute. The space complexity for WBGMRF is reduced to O(N2+N) compared to O(N3) in GHARF. The application of reference frames in WBGMRF reduces the space complexity and improves the algorithm for matching larger protein dataset in reasonable time and space.
Description
Keywords
Citation