CS5238 Combinatorial methods in bioinformatics 2004/2005 Semester 1
Lecture 8: Finding structural similarities among proteins (II)
Lecturer: Prof Jean-Claude Latombe
Scribe: Cheng Chi Kan, Lee Pern Chern and Moritz Buck
1 Voting scheme with hash table
Many-to-many comparisons are evaluated when we align protein structures. In order to avoid repetition, a better
organization of computation is necessary. This could be achieved by pre-computing the indexes of proteins and
arranging them in a hash table. Then, queries are evaluated based on a voting scheme using the hash table. This
voting scheme replaces the seed generation process.
In this lecture, we look into the voting scheme used in 3dSEARCH [2]. The algorithm is based on the concept of
geometric hashing [1] developed in the eld of computer vision. The basic idea is to represent all secondary structure
elements (SSEs) from all target proteins with a large, highly redundant hash (or index) table. Once the table has been......
Join Now or Login to view the rest of this paper.
Approximate Word Count: 296
Approximate Pages: 2 (260 words per double-spaced page) |