Heuristic algorithms in computational molecular biology

In this paper we develop a framework for designing and validating heuristic algorithms for NP-hard problems arising in computational biology and other application areas. We introduce two areas of current research in which we are applying the framework: implicit hitting set problems and analysis of protein–protein interaction networks, with emphasis on a specific problem in each area: multi-genome alignment and colorful connected graph detection.