Protein sequence alignment: Theory, algorithms, and optimal score function.

The growth in protein sequence data has placed a premium on ways to infer structure and function of the newly sequenced proteins. One of the most effective ways is to identify a homologous relationship with a protein about which more is known. This methodology, also known as sequence comparison, is addressed in this thesis. Using a novel optimization-iteration procedure, we obtain a new score function to improve the detection of distant homologs with sequence comparison. In addition, we assess the performance of a recently developed alignment algorithm for sequence comparison and examine the null statistics of the scores obtained with this algorithm. The analysis begins by introducing the current techniques for sequence alignment and the interpretation of the scores obtained with such procedures. All of these methods rely on some score function to measure sequence similarity. We describe a new method of determining a score function, optimizing the ability to discriminate between homologs and non-homologs. We find that this new score function (OPTIMA) performs better than standard score functions for the identification of distant homologies. A detailed analysis of the performance of hybrid, a new sequence alignment algorithm developed by Yu and co-workers that combines Smith Waterman local dynamic programming with a local version of the maximum-likelihood approach, was made in order to access the applicability of this algorithm to the detection of distant homologs by sequence comparison. We analyzed the statistics of hybrid with a set of non-homologous protein sequences from the SCOP database and found that the statistics of the scores from hybrid algorithm follows an Extreme Value Distribution with lambda ∼1, as previously demonstrated by Yu et al. for the case of artificially generated sequences. The ability of dynamic programming to discriminate between homologs and non-homologs in the two sets of distantly related sequences is slightly better than that of hybrid algorithm. The advantage of producing accurate score statistics with only a few simulations may overcome the small differences in performance and make this new algorithm suitable for detection of homologs in conjunction with a wide range of score functions and gap penalties.Ph.D.BiochemistryBiological SciencesMolecular biologyPure SciencesUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/127833/2/3029357.pd