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

Simple item page
dc.contributor.authorOthman, Fazilah
dc.date.accessioned2015-05-06T07:51:31Z
dc.date.available2015-05-06T07:51:31Z
dc.date.issued2010
dc.description.abstractProteins 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.en_US
dc.identifier.urihttp://hdl.handle.net/123456789/617
dc.language.isoenen_US
dc.titleBipartite graph algorithm with reference frame representation for protein tertiary structure matchingen_US
dc.typeThesisen_US
Files
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Pusat Pengajian Sains Komputer - Tesis