Chadi Kallab

Heuristics & Phylogenies: Generic Implementation + Encoding for Genetic Sequences Comparison Chadi Kallab

This research focuses on the NP-Hard problem of finding an optimal tree topology where leaves represent biological sequences. The problem tries to minimize the number of changes between sequences. As there number increases, the search space size grows exponentially, requesting the use of optimization methods, to come up with an acceptable optimal topology. Despite the efforts to relate large number of species and gene families to each other, the computation intensive load of many popular methods for evaluating trees (ex: parsimony and maximum likelihood) establish the quasi-inexistence of an exact solution for more than about 20 sequences. Different algorithm types (based on dynamic programming, linear programming, heuristics ?) are used in sequence alignment. For large count of sequences, heuristics may give a result similar to the exact solution offered by dynamic prog or linear prog, but in much shorter time. The author aims to suggest a general way to encode the problem for different heuristic algorithm types; in addition to suggesting heuristics generic optimal implementations, trying to get a compromise between speedup, flexibility and detailed tracing/chronology of each run.