Studies conducted during the last few years have brought a great change in our understanding of the role that RNA molecules play in the biological systems. They do not only take part in the protein synthesis or serve as adaptors translating information encoded in nucleotide sequences but also are involved in regulation of geneexpression. Most of them are produced from the larger molecules due to enzyme processing or spontaneous degradation and play a crucial role in the cellular processes.In our laboratory, we work on the problem of a degradation of RNA molecules. In the studies we use the artificial RNA  molecules, which were designed in such a way that they should be unstable, according to the rules developed by Kierzek and co-workers. On the basis of the results of their degradation we identify the regions of RNA molecules which are weak and the most susceptible to the cleavage. We have also proposed a formulation of a new problem, called RNA Partial Degradation Problem (RNA PDP) and the algorithm that allows to reconstruct the cleavage sites of the given RNA molecule.

Determining amino acid sequences of protein molecules is one of the most important issues in molecular biology. These sequences determine protein structure and functionality. Unfortunately, direct biochemical methods for reading amino acid sequences can be used for reading short sequences only. This is the reason, which makes peptide assembly algorithms an important complement of these methods.In our lab we have developed two algorithms solving the problem of short amino acid sequence assembly:- tabu search based method- genetic algorithm.Both algorithms have been tested in computational experiments and their performance compared.

Sequencing by hybridization (SBH) is one of the methods of reading a DNA sequence. It consists of two phases: the biochemical and computational ones. In the biochemical phase a DNA chip, which contains a library of several different oligonucleotides, is exposed to the solution containing many copies of target DNA. Hybridization occurs between the DNA sequence and oligonucleotides in their complementary places. In most of the hybridization experiments, the library is a set of oligonucleotides of the same length. After the reaction, one obtains a set of short subfragments of the examined sequence by reading a fluorescent or radioactive image of the DNA chip. This set is called spectrum.The computational phase of DNA sequencing consists in reconstructing the target DNA sequence from the oligonucleotides in the spectrum. It is known that in the case of an ideal hybridization experiment, when no errors in spectrum are involved, the reconstruction of the sequence can be solved in polynomial time.In real hybridization experiments we can get two different kinds of errors:* positive errors - these are additional oligonucleotides that appear in the spectrum, but do not fit to the target DNA,* negative errors - missing oligonucleotides in the spectrum, comparing to the ideal spectrum; a special case are negative errors coming from repetitions, that are repeated subsequences in the original sequence but present only in one copy in the spectrum.When the above errors occur in the spectrum, the reconstruction of the DNA sequence becomes strongly NP-hard.Tabu search algorithm presented in the first article can be downloaded here.In section Standard and isothermic spectra you may find instances used in computational tests of algorithms solving the standard and isothermic DNA sequencing by hybridization problem with both negative and positive errors. The following papers contain descriptions of the algorithms and the tests:* J. Blazewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz, A. Swiercz, "Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries", Computational Biology and Chemistry 28, 2004, pp. 11-19.* J. Blazewicz, C. Oguz, A. Swiercz, J. Weglarz, "DNA sequencing by hybridization via genetic search", Operations Research 54, 2006, pp. 1185-1192.* J. Blazewicz, F. Glover, M. Kasprzak, W.T. Markiewicz, C. Oguz, D. Rebholz-Schuhmann, A. Swiercz, "Dealing with repetitions in sequencing by hybridization", Computational Biology and Chemistry 30, 2006, pp 313-320.In section Standard spectra you may find the instances which were used in computational tests of algorithms solving the standard DNA sequencing by hybridization problem with both negative and positive errors. The following papers contain descriptions of the algorithms and the tests.* J. Blazewicz, M. Kasprzak, W. Kuroczycki, Hybrid genetic algorithm for DNA sequencing with errors, Journal of Heuristics 8 (2002) 495-502.* J. Blazewicz, F. Glover, M. Kasprzak, DNA sequencing - tabu and scatter search combined, INFORMS Journal on Computing 16 (2004) 232-240.* J. Blazewicz, F. Glover, M. Kasprzak, Evolutionary approaches to DNA sequencing with errors, Annals of Operations Research 138 (2005) 67-78.Most of the sequences for experiments were taken from GenBank, National Institute of Health, USA. Sequences are composed of at least 600 nucleotides.From the prefixes of the sequences of length 200, 400, 500, and 600, the ideal spectra were generated (by selecting all of the oligonucleotides being members of the library that are contained in the sequence). Next, errors were randomly added to the spectra. Some of the sequences (in the section: standard spectra) were generated according to the uniform distribution.Spectra contain both negative and positive errors (with error rate ranging from 5% up to 20%). 5% error rate means that from the ideal spectrum 5% of all the oligonucleotides were randomly deleted and the same number of oligonucleotides were added (different from the ones already existing in the spectrum). Spectra were created progressively, which means that 10% of errors contained the same errors as in the spectrum with 5% error rate plus additional 5% of errors of both types. This provides that the case with spectra containing less errors (5%) is not more difficult than the case with spectra containing more errors (10%). Spectra with 20% of errors were created accordingly. At the end, oligonucleotides in the spectra were sorted alphabetically due to lose the information about order of the oligonucleotides within the target.In specific subarticle you can read definitions of used libraries.

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.

Pairwise alignment algorithms are of great importance in computational biology. Methods based on dynamic programming, despite their high computational complexity, have been widely used over a few decades due to their accuracy. However, in real-life applications constantly increasing number of biological sequences has started to cause serious difficulties.Therefore, in response to presented needs, we developed an efficient tool for pairwise alignment called G-PAS (previously known as gpu-pairAlign).More information in article.

GRASShopPER (GPU overlap GRaph ASSembler using Paired End Reads) is the novel assembly method that follows the approach of overlap–layout–consensus (OLC). In the method, a very efficient GPU  implementation of the exact reads alignment algorithm has been used for calculating the scores and shifts on the arcs of the graph. Two-part fork detection strategy has been introduced, which highly reduces misassembly rate in the resulting contigs. The first part is carried out during the graph traversal. In the second part, a greedy hyper-heuristic identifies undetected forks on the basis of paired-end reads information. The results of computational experiments show high coverage of the tested genome.More information