LABORATORY OF BIOINFORMATICS


Head: Jacek Błażewicz

Reserach Staff:
Piotr Formanowicz, Marta Kasprzak, Piotr Łukasiak, Marta Szachniuk, Aleksandra Świercz

Keywords:
computational biology, computational complexity, models of parallel computing, graph theory, sequencing by hybridization,
physical mapping, searching for motifs, phylogenetic trees, RNA and protein structure analysis, restriction mapping, DNA computing



The research area of the laboratory involves many branches of computational biology focusing on combinatorial methods of analyzing and solving biological problems. Among our main areas of interest, there are sequencing by hybridization, assembling, nucleotide and amino acid sequence alignment, searching for motifs, analysis of evolutionary history, discovering of 2- and 3-dimentional structures of protein and nucleotide chains.
The general objective of the research is to explore the area of science where molecular biology meets mathematics and computer science. This allows to work on mathematical formulae of biological problems, to classify their computational complexity and to develop appropriate algorithms based on complexity analysis.
Most of recent research activities have concentrated on combinatorial aspects of sequencing by hybridization as well as on development of new approaches to this method. The approaches proposed take into account hybridization errors, being the main drawback of the SBH method. To analyze the problem, a graph theory is used and the interaction of ideas between biology and mathematics resulted in new models of sequencing (on the biological side) and a new class of graphs, called DNA graphs (on the mathematical side), for example.
The DNA sequencing is a procedure used on the lower level of nucleic acids sequence determination. The higher levels are assembling and mapping. The research is carried out also on these levels, and restriction mapping is one of the most important areas of interest. A new method for restriction map construction has been proposed.
The three research areas mentioned above concern the reading of genetic information that is usually the fist stage in molecular biology research. The second one is an analysis of this information, which in general is a much more difficult task. In this area the research in the laboratory concentrates on determining secondary protein and RNA structures. In the former case the structure is predicted on the basis of amino acid sequences, using a method called Logical Analysis of Data. In the latter case, NMR data is an input for a combinatorial problem. Moreover, new methods are being developed for sequence alignment and motif finding
allowing a modification of a classical Clustal W algorithm, for example. The other field of research is phylogeny analysis, where among others, gene duplication events are analyzed.


Current research activities:

  • computational complexity analysis and algorithms for sequencing by hybridization with
    the presence of errors;
  • algorithms for restriction mapping;
  • prediction of protein secondary structure using Logical Analysis of Data;
  • algorithms for RNA structure analysis based on NMR data;
  • algorithms for a phylogenetic tree construction;
  • gene duplication analysis;
  • development of new oligonucleotide libraries.


    SELECTED PUBLICATIONS

    J. Błażewicz, K. Ecker, B. Plateau, D. Trystram (eds.)
    Handbook on Parallel and Distributed Processing.
    Springer Verlag, Berlin, New York, (2000).

    J. Błażewicz, W. Kubiak, T. Morzy, M. Rubinkiewicz (eds.)
    Handbook on Data Management Information Systems.
    Springer Verlag, Berlin, New York, (2003).

    J. Błażewicz, M. Drozdowski, P. Formanowicz, W. Kubiak, G. Schmidt
    Scheduling preemptable tasks on parallel processors with limited availability.
    Parallel Computing 26, 1195-1211 (2000).

    J. Błażewicz, P. Formanowicz, M. Jaroszewski, M. Kasprzak, W. Markiewicz
    Construction of DNA restriction maps based on a simplified experiment.
    Bioinformatics 17, 398-404 (2001).

    J. Błażewicz, P. Hammer, P. Łukasiak
    Prediction of protein secondary structure using Logical Analysis of Data algorithm.
    Computational Methods in Science and Technology 7, 7-25 (2001).

    J. Błażewicz, P. Formanowicz, M. Kasprzak, D. Kobler
    On the recognition of de Bruijn graphs and their induced subgraphs.
    Discrete Mathematics 245, 81-92 (2002).

    J. Błażewicz, P. Formanowicz, F. Guinand, M. Kasprzak
    A heuristic managing errors for DNA sequencing. Bioinformatics 18, 652-660 (2002).

    J. Błażewicz, M. Kasprzak, W. Kuroczycki
    Hybrid genetic algorithm for DNA sequencing with errors.
    Journal of Heuristics 8, 495-502 (2002).

    W. Kubiak, J. Błażewicz, P. Formanowicz, J. Breit, G. Schmidt
    Two machine flow shops with limited machine availability.
    European Journal of Operational Research 136, 528-540 (2002).

    J. Błażewicz, M. Jaroszewski
    New algorithm for the Simplified Partial Digest Problem.
    Lecture Notes in Bioinformatics 2812, 95-111 (2003).

    J. Błażewicz, M. Kasprzak
    Complexity of DNA sequencing by hybridization.
    Theoretical Computer Science 290, 1459-1473 (2003).

    R.W. Adamiak, J. Błażewicz, P. Formanowicz, Z. Gdaniec, M. Kasprzak, M. Popenda, M. Szachniuk
    An algorithm for an automatic NOE pathways analysis of 2D NMR spectra of RNA duplexes.
    Journal of Computational Biology 11, 163-179 (2004).

    J. Błażewicz, K. Dill, P. Łukasiak, M. Miłostan
    A tabu search strategy for finding low energy structures of proteins in HP-model.
    Computational Methods in Science and Technology 10, 7-19 (2004).

    J. Błażewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz, A. ¦wiercz
    Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries.
    Computational Biology and Chemistry 28, 11-19 (2004).

    J. Błażewicz, F. Glover, M. Kasprzak
    DNA sequencing – tabu and scatter search combined.
    INFORMS Journal on Computing 16, 232-240 (2004).

    J. Błażewicz, P. Formanowicz, P. Kędziora, P. Wojciechowski
    Parallel algorithms for evolutionary history reconstruction.
    Lecture Notes in Computer Science 3019, 1138-1145 (2004).

    J. Błażewicz, P. Formanowicz, M. Kasprzak, W.T. Markiewicz
    Sequencing by hybridization with isothermic oligonucleotide libraries.
    Discrete Applied Mathematics 145, 40-51 (2004).

    J. Błażewicz, M. Jaroszewski, M. Kasprzak, B. Pali¶wiat, M. Pryputniewicz
    On the complexity of the Double Digest Problem.
    Control and Cybernetics 33, 133-140 (2004).

    J. Błażewicz, M. Szachniuk, A. Wójtowicz
    Evolutionary algorithm for a reconstruction of NOE paths in NMR spectra of RNA chains.
    Bulletin of the Polish Academy of Sciences, Technical Sciences 52, 221-230 (2004).

    J. Błażewicz, P. L. Hammer, P. Łukasiak
    Analysis of protein secondary structure prediction based on physico-chemical properties of amino acids using LAD.
    IEEE Engineering in Medicine and Biology Magazine, in press.