Department of Computer Science, University of Waterloo, Waterloo, Ont N3L 3G1, Canada
In this talk, we will study how machine learning research is related to the mathematical study of the DNA sequencing process. In particular, we will discuss several models of learning a string from its substrings and the related algorithmic issues. These models include the basic pac-learning model, learning with queries, learning with oblivious queries, etc. The last learning model is intended to model sequencing by hybridization. We will investigate how one can fix all queries (according to a conditional universal distribution) beforehand and still efficiently learn a sequence in a group of homologous sequences.