The Taub Faculty of Computer Science Events and Talks

In many practical situations heuristic algorithms reliably give satisfactory solutions to real-life instances of optimization problems, despite evidence from computational complexity theory that the problems are intractable in general.Our long-term goal is to contribute to an understanding of this seeming contradiction, and to put the construction of heuristic algorithms on a firmer footing.

As a step in this direction we describe the evolution of a succesful heuristic algorithm By Erick Moreno Centeno and the speaker for the following Global Genome Alignment problem: given the genomes of several species, an anchor pair is a pair of substrings from two different genomes which appear to be descended from a common ancestral sequence. Given a collection of anchor pairs, construct a multiple alignment maximizing the number of anchor pairs that are aligned against each other. Such an alignment exhibits the common evolutionary ancestry of the set of species.

We then use the Global Genome Alignment problem to illustrate a general approach for tuning the parameters and design choices within a given heuristic algorithmic strategy, assuming the availability of a training set of typical problem instances. This approach leads to a decision-theoretic problem related to the Multi-Armed Bandit Problem.