Bipartite graph algorithm with reference frame representation for protein tertiary structure matching
Loading...
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.