Institute of Computer Science Pattern Recognition and Bioinformatics

Stefan Posch: Lehre

Algorithmen der Bioinformatik I - Übungen

• Übungsblatt 1 (pdf)
• Übungsblatt 2 (pdf)
• Übungsblatt 3 (pdf)
  Zum Testen der Suchalgorithmen stellen wir einige Testdaten zur Verfügung:
  • Das gesamte E. coli Genom ist in der Datei ecolim52.fas abgelegt. Das Orginal dieser Datei befindet sich an der Webadresse http://www.genome.wisc.edu/pub/sequence/ecolim52.fas. Wir stellen eine Version dieser Datei, die nur das Genom (keine Kommentare, keine Newlines) enthält unter dem Namen ecolim52-trimmedNoNewLines.fas zur Verfügung.
    In diesem Genom kann man nun nach Transkriptionsfaktorbindestellen suchen. Die populärsten bei E. coli sind die der lacI, trpR oder araC Repressoren. Die Konsensussequenzen dieser Bindestellen kann man auf der Internetseite http://bayesweb.wadsworth.org/binding_sites/full.html abrufen. Wir geben hier ein paar Beispiele: "ggaggcattttgcttcc" (4630288), "acaatggcgacatatt" (4630312), "tccatccaaaaaaacgggtatgga" (70056), "gcaaagtgtgacgccgtgc" (70154), "aaataatcaatgtggactttt" (70173) und "atatggacaattggtttcttc" (70340). In Klammern ist jeweils der Startindex der Fundstelle angegeben (Zählung beginnt bei Null). Will man mehr Treffer haben, dann kürze man einfach die Muster.
    Zu bemerken ist zu diesem Beispiel, dass man in Anwendungen diese Muster nicht mit exaktem Mustervergleich suchen würde, sondern mit fehlertoleranten Verfahren (Warum?). Für einen Test der Verfahren ist es aber trotzdem ein gutes Beispiel.
    Wir danken Thomas Thiel für die Bereitstellung der Information.
  • Ein kurzes Beispiel mit überlappendem Muster und Muster am Ende (Test, ob das Programm Stringgrenzen überschreitet) sind Text="ababcababcababcabcabxxxxxxxxabcab" und Muster="abcab".
  • Ein kleines Beispiel, um den Effekt der bad character rule zu sehen ist Text=" xpbctbxabpqxctbpq" und Muster="tpabxab" (aus dem Buch von Gusfield).
• Übungsblatt 4 (pdf)
• Übungsblatt 5 (pdf)
• Übungsblatt 6 (pdf)
• Übungsblatt 7 (pdf)
• Übungsblatt 8 (pdf)
• Übungsblatt 9 (pdf)