- Projects should be worked on by groups of two or three students all of whom are taking the course for credit. Each group needs to include at least one CS or ECE graduate students.
- The following are just project ideas. If you have other ideas for potential projects, come talk to Holger - I look forward to hearing about your ideas!
- Start discussing project ideas you are interested in with your fellow students and with me (Holger) as soon as possible - you need to have selected a project by September 27th and a proposal has to be submitted by October 11th. The proposal should be about 2-3 pages long and needs to reflect your understanding of the problem, briefly discuss existing and related work, describe the proposed work, specify a work schedule and distribution of work between the group members, and list relevant literature.

The goal of this project is to implement and empirically study the behaviour of iterative refinement methods for multiple sequence alignment using the SP (sum of pairs) score.

After familiarising yourself with the general approach and conducting a literature survey, you might want to implement two or three different methods (these could be all rather closely related) and study their performance on a set of homologous biological sequences. You might also consider additional tests on sets of sequences obtained from applying simulated evolution (according to one of the commonly used sequence evolution models, e.g., the Jukes-Cantor model).

References:

- Durbin, Eddy, Krogh, Mitchison: Biological Sequence Analysis. Cambridge University Press, 1998; Ch.6. (This book is available from the Reading Room; it contains a good introduction to the problem and contains further references.)
- O. Gotoh: Multiple sequence alignment: algorithms and applications. Adv. Biophys. 36, 159-206, 1999.
- Udo Tönges, Sören W. Perrey, Jens Stoye, Andreas W. M. Dres: A General Method for Fast Multiple Sequence Alignment; Preprint, Universität Bielefeld, 1996. [ electronic version ]
- Multiple Alignment Resource Page of the VSNS BioComputing Division: www.techfak.uni-bielefeld.de/bcd/Curric/MulAli/welcome.html

The project is to implement an algorithms for protein design in the 2D HP model (ideally, a new algorithm that has not been previously applied to the problem) and to carefully evaluate its performance against results known from the literature. Furthermore, given protein structures can be investigated in terms of "designability", e.g., by determining the number of sequences that have a given structure as their native structure. Implementations of high-performance algorithms for 2D HP protein structure prediction will be provided.

References:

- J. Deutsch, and T. Kurosky: New Algorithm for Protein Design. Physical Review Letters, Vol 76, Num 2, pp. 323-326, 1996.
- A. Irback, C. Peterson, F. Pottharst, and E. Sandelin: Monte Carlo procedure for protein design. Physical Review E, Vol 58. Num 5, pp. 5249-5252, 1998.
- C. Micheletti, A. Maritan, J. Banavar: A comparative study of existing and new design techniques for protein models. J. of Chem. Physics, Vol 110, Num 19, pp. 9730-9738.
- Brian Hayes: Prototeins. American Scientist, Volume 86, No. 3, 1998. [ electronic version ]
- 2D HP Benchmark Instances

Combinatorial methods for designing DNA strands have been used to obtain sets of DNA strands that do not hybridize between themselves and only with perfect complements.

Some methods used for this purpose can be found in the coding theory literature [1,2,3]. Nevertheless, few publications report results on time complexity and algorithmic behavior for their methods. The project is to implement and possibly expand one (or more) of the algorithms presented in [1,2] and/or [3], and to characterise its performance, with the goal of gaining a better understanding of the empirical performance of these methods and possibly achieving improved results.

References:

- K.U. Koshnick (1991), "Some new constant weight codes," IEEE Transactions on Information Theory, 37, 370-371.
- G. Dueck and T. Scheuer (1990), "Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing," Journal of Computational Physics, 90, 161-175
- F. Comellas and R. Roca (1993), "Using genetic algorithms to design constant weight codes," Proceedings of the International Workshop on Applications of Neural Networks to Telecomunication, LAwrence Erlbaum, Hillsdale, NJ, 119-124.
- A.E. Brouwer, J.B. Shearer, N.J.A. Sloane, W.D. Smith (1990), "A new table of constant weight codes," IEEE Transactions on Information Theory, 36, 1334-1380.

The project is to develop an algorithm (or eventually to modify a currently existing method [1]) to design DNA strands of different length. All strands must fullfil similar constraints (combinatorial and thermodynamic). The algorithm should be able to build new sets from scratch as well as to extend a initial set of DNA strands and/or to generate new DNA strands without modifying the existing ones, such that the entire resulting set fulfils all given constraints. The new algorithm should be analysed empirically and its performance should be compared to existing methods.

References:

- Dan C. Tulpan, Holger H. Hoos, Anne Condon, "Stochastic Local Search Algorithms for DNA Word Design," DNA 8 2002: 229-241.

last update 04/09/20, hh