Project name: Advanced Algorithms and Systems (INS4.3)

Research group: Algorithms and Complexity (INS4)

Coordinator of this project: Harry Buhrman
Startdate: 1997-01-01
Enddate: 2100-01-01

The project develops principles and algorithms for distributed and parallel systems. Moreover, it identifies limitations and possibilities of future systems by exploiting fundamental mathematical techniques of complexity theory. A major item is the descriptional complexity, leading to both the `incompressibility method' and `learning by compression'.

The last decade has witnessed an explosion in the amount and complexity of genomic data. Much of this data is publicly available for academic and commercial use by biological, medical and pharmaceutical researchers. In order for novel biological discovery to occur, computational tools must be developed to store, manipulate, visualize and analyse the genomic data. The Bioinformatics Research Group designs, develops and assesses computational tools for the exploration of genomic data. Topics include:

Genome analysis including statistical methods for gene prediction and the detection of horizontally transferred genes. Genome compression. Sequence alignment, sequence consensus, and motif discovery. Algorithms for inferring evolutionary trees. Tools for modeling sequence evolution and for conducting simulation studies.

Our research plan includes both the theoretical analysis of algorithms and development of and experimentation with practical computational tools.

We have successfully cooperated (Tromp) in designing a software package (PatternHunter) that gives faster and more sensitive homology search, and improves on popular packages like MegaBlast and BL2SEQ, and in designing (Vitanyi) a computational method to obtain a first completely automatic computed whole mitochondrial phylogeny tree.

Members
Harry Buhrman, Bruno Loff, Arie Matsliah, Leen Torenvliet, Paul Vitanyi, Ronald de Wolf.

Key publications
Publications of Advanced Algorithms and Systems

Project reports
Reports of Advanced Algorithms and Systems

Cooperation partners
We cooperate in research intensively with the Un. Chicago (Prof L. Fortnow), the Un. of California, Santa Barbara, (Prof. M. Li), BioInformatics Solutions Inc. (Prof. M. Li), Un. California, Riverside, (prof. T. Jiang), Tokyo Institute of Technology (Prof. O. Watanabe). In distributed and network computing research we cooperate with Un. Twente (dr. J.H. Hoepman).

We will cooperate with the Bioinformatics research groups of the Un. of Waterloo, Canada (Prof. M. Li), Univ. California, Santa Barbara (Prof M. Li), Univ. California, Riverside (prof. T. Jiang), and BioInformatics Solutions Inc (M. Li), and, as planned, with the University of Utrecht (A. Siebes).