Ttle: "Fixed-Parameter Tractable Algorithms for Microarray Data Analysis"
Speaker: Dr. Michael Langston, Department of Computer Science University of Tennessee, Knoxville, TN
Place: Mechanical Engineering (ME) 161; Tuesday, November 8, 2005 4:30pm

Abstract

This talk addresses algorithmic methods based on the theory of fixed-parameter tractability. When combined with high performance computational platforms, these methods can be used as a basis for launching systematic attacks on difficult combinatorial problems. Efficient sequential techniques for problem reduction and highly parallel algorithms for exhaustive search will be discussed. The importance of maintaining a balanced decomposition of the search space turns out to be critical to achieving scalability. Applications to high-throughput computational biology will be stressed, with the analysis of microarray data serving as a prime example. Using mRNA samples obtained from a variety of inbred Mus musculus strains, we solve immense instances of the clique problem to derive sets of putatively co-regulated genes. The depth of quantitative genetic analysis we can perform is vastly enhanced by combining these results with knowledge of cis-regulatory elements, ontological classifications, and causal structures that may be imposed with quantitative trait locus mapping. Techniques for dealing with noisy data are important concerns. A long-term goal is gene regulatory network discovery.


Click here for a full schedule of BIOINFORMATICS SEMINARS, past and present.