Abstract Motivation: A formulation of a new problem of the restriction map construction based on a simplified digestion experiment and a development of an algorithm for solving both ideal and noisy data cases of the introduced problem. Results: A simplified partial digest problem and a branch and cut algorithm for finding the solution of the problem. Contact: [email protected] * To whom correspondence should be addressed. † Fellowship holder of the Foundation for Polish Sciences.

MOTIVATION: Reconstruction of the original DNA sequence in the sequencing by the hybridization approach (SBH) requires computational support due to a large number of possible combinations. One can notice a lack of algorithms admitting false-negative data and giving in addition all possible solutions. RESULTS: In this paper, a new method of sequencing has been proposed. An algorithm based on its idea (for the general case, when some data are missing, like in the real experiment) has been implemented and tested. Authentic DNA sequences have been used for testing. A parallel version of the algorithm has also been implemented and tested. The quality of the reconstruction is satisfactory for the library of oligonucleotides of length between 8 and 12, and 100, 200 and 300 bp long sequences. A way to a further decrease in the computation time is also suggested.