Anchored sequence alignment and motif discovery

• Applicant: Professor Dr. Burkhard Morgenstern
• Subject Area: Bioinformatics and Theoretical Biology
• Term: from 2008 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 92485091

The proposed project is part of an interdisciplinary French-German collaboration. The goal of this cooperation is to develop and apply combinatorial algorithms for alignment and motif-finding in biological sequences. The N-local-decoding (NLD) method developed by our project partners shall be further improved and combined with the program DIALIGN developed by the applicant of the present proposal. Here, the key tool will be a recently developed anchoring option in DIALIGN. Also, DIALIGN will be improved directly by using new optimization algorithms. Our project has two main goals. The ultimate goal is to improve the performance of DIALIGN in terms of its ability to detect homologies in nucleic-acid and protein sequence families. From a more theoretical point-of-view, we are also interested in the combinatorial optimization problem of finding multiple fragment alignments with optimal scores. NLD is a promising approach for this purpose since, like DIALIGN, it is based on gap-free segment comparison. Unlike DIALIGN, however, it directly finds motifs occurring simultaneously in several or all of the input sequences. Our project partners will apply the newly developed methods to improve motif-finding and classification for the topoisomerase protein family. A second area of application will be HIV sequences.

• DFG Programme: Research Grants