DNA杂交测序算法研究进展

DNA杂交测序是计算生物学的核心问题之一,其研究目标是在杂交实验的基础上重构DNA序列,已证明带有错误的杂交测序属于强NP-难问题。随着组合优化的研究,精确算法和启发式搜索算法,尤其是后者,被用于求解此类问题。目前,许多文献已提出了重构算法,但现有算法在解决实际问题时仍存在缺陷。综述了国内外已提出的重构算法,在此基础上进行了比较,分析了存在的主要问题,指出了当前新的研究热点,对未来的研究与发展趋势进行了展望。

Research Progress of Algorithms for DNA Sequencing by Hybridization

Sequencing by hybridization is one of the most challenging problems in computational biology.Its research aim is to reconstruct DNA sequence based on hybridization experiments.And it has been proved that the sequencing by hybridization with errors belongs to strongly NP-hard.With the study of combinatorial optimization,exact algorithm and heuristic search algorithm,especially the latter,have been used to solve this kind of problems.Currently,many literatures have puts forward the reconfiguration algorithm,but there still are various defects in existing algorithms in solving the actual problems.This paper reviews the reconfiguration algorithms presented in China and foreign countries,and based on this,makes comparison of these algorithms,analyze some existing problems,point out some current research highlights,and looks forward to the future research and development trends.