* Faculty       * Staff       * Students & Alumni       * Committees       * Contact       * Institute Directory
* Undergraduate Program       * Graduate Program       * Courses       * Institute Catalog      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Colloquia       * Seminars       * News       * Events       * Institute Events      
* Overview       * Lab Manual       * Institute Computing      
No Menu Selected

* Research

Ph.D. Theses

Protein Structural Similarity

By Saeed Salem
Advisor: Mohammed J. Zaki
July 9, 2009

Proteins are macromolecular organic compounds. They are involved either directly or indirectly in all the biological processes in living organisms. Structural similarity between proteins provides us with insights into their evolutionary relationships especially where sequence similarity is not strong enough to indicate functional relationship. Moreover, non-sequential alignments highlight the relationship between proteins that are related through circular permutation, or proteins that evolved from different ancestors owing to convergent evolution.

Most of the algorithms for structural alignment are inherently limited to sequential alignments and therefore cannot capture non-sequential alignments. Another limitation of the existing methods is that they only report rigid alignments and thus cannot capture flexible alignments.

This thesis presents two new approaches which tackle these limitations. The SNAP algorithm is an iterative superposition-based algorithm that reports both sequential and non-sequential alignments, from an initial superposition. The second algorithm, FlexSnap, assembles the alignment from small well-aligned fragments (AFPs) and introduces hinges when there is a significant gain in the alignment score. Through extensive experiments, both SNAP and FlexSnap show competitive results to the state-of-the art alignment methods (CE, DALI, SARF, FlexProt, FATCAT). Moreover, FlexSnap is the only alignment algorithm which reports flexible non-sequential alignments.

* Return to main PhD Theses page