Grant: Discovery Grants Program - Individual

This proposal is in two areas: bioinformatics and Kolmogorov complexity. Part I: Building a comprehensive biological sequence annotation system. This system consists of homology search tools (PatternHunter), motif finding and protein family classification tool (COPIA), protein threading tool (RAPTOR), coding region detection tool (ExonHunter), and protein-protein interaction literature mining tool (PathwayFinder). In developing these tools, we have invented the optimal spaced seeds for homology search and linear programming formulation for protein threading. We plan to investigate new ways of studying the following problems: (a) Linear programming formulation for loop modeling, side-chain modeling, refinement, and folding transmembrane proteins. (b) New indexing structure for large scale DNA databases. (c) Theory of optimal spaced seeds. Our invention of optimal spaced seeds has started a new trend of research. We will study the theory of spaced seeds in depth. (d) Further development of the widely used PatternHunter software in order to better serve the bioinformatics research community and industry. Part II. Kolmogorov complexity. We will do research in two directions: (a) Incompressibility method and average case analysis of algorithms. Over the past 15 years, we have been developing the incompressibility method and used it to solve a number of open problems. For example, recently we have successfully applied the method to analyze the average case complexity of Shellsort, an open problem for 40 years. We plan to further develop this methodology and use this method to analyze more algorithms. (b) Information distance, introduced by us in 1991, is now an accepted concept for measuring information distance between two objects. Our normalized information distance (2001) has found applications in whole genome phylogeny, English document classification, plagiarism detection, google distance, and various time series classification. This research will further generalize such concepts and develop more applications. Our research has directly created a part of Canadian bioinformatics industry (BSI); our research results are, and will continue to be, used in proteomics reseaerch and pharmaceuticals to help speed up drug discovery.