Algorithms for DNA Sequencing by Hybridization: A Review

One of the most challenging problems in computational biology is the reconstruction of DNA sequences from DNA fragments. This paper describes the problems of sequencing by hybridization with standard, isothermic and multistage oligonucleotide libraries. However, the problems are NP-hard in the strong sense in case of errors. With the study of combinatorial optimization, it has become common for the researchers to apply the exact and heuristic algorithms, especially the latter, to solve these problems. Though there have been various available methods in the literature, researchers still have difficulties in choosing the best method that could solve these problems well. This paper aims to review the existing algorithms, compare them, point out the flaws of these works and indicate the emerging trend.