What we actually do

The main areas of our research are: DNA sequencing and assembling (including design of algorithms for the NGS sequencers); protein structure analysis; RNA structure analysis and prediction (including automatic tertiary structure prediction tool); nanotechnology and DNA computing.

Simplified partial digest problem
In order to recognize linear structure of a long DNA fragment (i.e. its sequence of nucleotides), the DNA molecule is divided into smaller parts, sequenced and then combined together back into the whole. Restriction mapping is one of the approaches used for the purpose of dividing and subsequent joining smaller parts. Very short DNA fragments (patterns) of the molecule uniquely recognized by restriction enzymes provide information necessary to carry out this process. The patterns are called restriction sites.

During the process of restriction mapping of DNA, many copies (clones) of a DNA molecule are exposed to restriction enzymes, which cut them at particular patterns (sites). Depending on the time of this reaction (also on the enzyme used and on the length of DNA), the experiment returns clones of the original molecule cut at few or many sites (usually the shorter reaction time, the smaller the number of sites recognized by the enzyme). The cutting process leads to the loss of information about the location of the fragments and restriction sites in the original molecule, their order is next reconstructed on the base of the fragment lengths.

There are two classical variants of the experiment: double digestion, which employs two restriction enzymes, and partial digestion, which uses one enzyme but in a series of reactions differing by time. At the output of the error-free partial digestion one gets a multiset of all interpoint distances, where the points are the restriction sites and the ends of the molecule. The aim of the Partial Digest Problem (PDP) is to reconstruct the restriction map basing on the multiset of fragment lengths. This variant was not widely employed in biological laboratories because of the difficulty in obtaining fragments between every pair of sites. From the point of view of computational complexity theory, the status of error-free PDP (being a known problem also in computational geometry) is still an open question.

The simplified partial digestion was proposed as a new variant of the restriction mapping in [1]. It overcomes the drawback of the partial digestion outlined above. In this simplified method, one enzyme is used on two sets of clones of the DNA molecule. The corresponding experiment consists only of two parts. In the first part, the time of the chemical reaction is very short and chosen so that target cloned molecules from the first set are cut at (statistically) one restriction site at most. In the second part, the reaction time span is long enough to cut the cloned molecules from the second set at all restriction sites. This approach reduces the number of reactions and presents an easier adjustment of the reaction times. The aim of the Simplified Partial Digest Problem (SPDP) is the reconstruction of the map of restriction sites from two multisets resulting from the two reactions. The computational complexity of SPDP was solved in [2], the problem was proved to be strongly NP-hard. On the other hand, further studies have shown computational usefulness of this approach, confirmed by tests of a series of new algorithms for the problem [3-6].

[1] J. Blazewicz, P. Formanowicz, M. Kasprzak, M. Jaroszewski, W.T. Markiewicz, "Construction of DNA restriction maps based on a simplified experiment", Bioinformatics 17 (2001) 398–404.

[2] J. Blazewicz, M. Kasprzak, "Combinatorial optimization in DNA mapping – a computational thread of the Simplified Partial Digest Problem", RAIRO – Operations Research 39 (2005) 227–241.

[3] J. Blazewicz, M. Jaroszewski, "New algorithm for the Simplified Partial Digest Problem", Lecture Notes in Bioinformatics 2812 (2003) 95–110.

[4] J. Blazewicz, E.K. Burke, M. Kasprzak, A. Kovalev, M.Y. Kovalyov, "The Simplified Partial Digest Problem: enumerative and dynamic programming algorithms", IEEE/ACM Transactions on Computational Biology and Bioinformatics 4 (2007) 668–680.

[5] J. Blazewicz, E.K. Burke, M. Kasprzak, A. Kovalev, M.Y. Kovalyov, "On the approximability of the Simplified Partial Digest Problem", Discrete Applied Mathematics 157 (2009) 3586-3592.

[6] J. Blazewicz, E.K. Burke, M. Kasprzak, A. Kovalev, M.Y. Kovalyov, "The Simplified Partial Digest Problem: approximation and a graph-theoretic model", European Journal of Operational Research 208 (2011) 142-152.