Zhang Ji-Hong, Wu Ling-Yun, Zhang Xiang-Sun
Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing 100080, China.
Bioinformatics. 2003 Jan;19(1):14-21. doi: 10.1093/bioinformatics/19.1.14.
It is widely recognized that the hybridization process is prone to errors and that the future of DNA sequencing by hybridization is predicated on the ability to successfully cope with such errors. However, the occurrence of hybridization errors results in the computational difficulty of the reconstruction of DNA sequencing by hybridization. The reconstruction problem of DNA sequencing by hybridization with errors is a strongly NP-hard problem. So far the problem has not been solved well.
In this paper, a new approach is presented to solve the reconstruction problem of DNA sequencing by hybridization, which realizes the computational part of the SBH experiment. The proposed algorithm accepts both the negative and positive errors. The computational experiments show that the algorithm behaves satisfactorily, especially for the case with k-tuple repetitions and positive errors.
人们普遍认识到杂交过程容易出错，并且基于杂交的DNA测序的未来取决于成功应对此类错误的能力。然而，杂交错误的出现导致了基于杂交的DNA测序重建的计算困难。带错误的基于杂交的DNA测序重建问题是一个强NP难问题。到目前为止，这个问题还没有得到很好的解决。
本文提出了一种新的方法来解决基于杂交的DNA测序重建问题，该方法实现了SBH实验的计算部分。所提出的算法同时接受负误差和正误差。计算实验表明，该算法表现令人满意，特别是对于具有k元组重复和正误差的情况。
