Parameterized Algorithms in Bioinformatics: An Overview

Bioinformatics regularly poses new challenges to algorithm engineers and theoretical computer scientists. This work surveys recent developments of parameterized algorithms and complexity for important NP-hard problems in bioinformatics. We cover sequence assembly and analysis, genome comparison and completion, and haplotyping and phylogenetics. Aside from reporting the state of the art, we give challenges and open problems for each topic.

Linear time probabilistic algorithms for the singular haplotype reconstruction problem from SNP fragments

In this paper, we develop a probabilistic model to approach two realistic scenarios regarding the singular haplotype reconstruction problem--the incompleteness and inconsistency that occurred in the DNA sequencing process to generate the input haplotype fragments, and the common practice used to generate synthetic data in experimental algorithm studies. We design three algorithms in the model that can reconstruct the two unknown haplotypes from the given matrix of haplotype fragments with provable high probability and in linear time in the size of the input matrix. We also present experimental results that conform with the theoretical efficient performance of those algorithms. The software of our algorithms is available for public access and for real-time on-line demonstration.

The haplotype assembly model with genotype information and iterative local-exhaustive search algorithm

The minimum error correction (MEC) model for haplotype reconstruction is efficient only when the error rate in SNP fragments is low. In order to improve reconstruction rate, additional genotype information is added into MEC model as an extension to MEC model. In this paper, we first establish a new mathematical model for haplotype assembly problem with genotype information. Several properties of the mathematical model are proved. Then an iterative local-exhaustive search algorithm is proposed based on the model and its properties. The main idea is to find the optimal pair among 2(l-1) (l denotes the number of heterozygous sites of a genotype) haplotype pairs by performing local exhaustive search for the promising haplotype pair step by step. By experiments and comparison, extensive numerical results on real data and simulated data indicate that our algorithm outperforms the other algorithms in terms of efficiency and robustness.