LAB IN BIOINFORMATICS

Algorithms and Experiments for Finding Weighted Treewidth

under the guidance of  Dan Geiger

by Nickolay Dovgolevsky

Purpose

Experimenting with real data using new and known algorithms to produce a practical state-of-the-art vertex elimination algorithm for usage in various applications including Bayesian networks, genetic linkage analysis, and combinatorial problems.

Results

1. Using reduction rules as preprocessing. Main conclusion is a set of good reductions that are worthy to apply in almost every problem.

2. Comparison of stochastic greedy algorithms. Main conclusion is that a stochastic weighted fill-in algorithm due to Dan Geiger is the best so far.

3. Experiments on eight known benchmarks. Main conclusion is that the weighted fill-in algorithm is comparative to simulated annealing in reaching close to optimal cost but is much faster.

Background


The problem of finding treewidth has been the subject of research for many years.