You are here: home » teaching » 2003summer » genomvergleich

Seminar: Algorithmen zum Genomvergleich auf höherer Ebene
Universität Bielefeld - Technische Fakultät - AG Genominformatik

Algorithmen zum Genomvergleich auf höherer Ebene

Seminar im Sommersemester 2003

Montag, 16-18 Uhr, T2-233

Jens Stoye, Constantin Bannert

Kurzbeschreibung

Eine aktuelle Forschungsrichtung in der Bioinformatik ist der Genomvergleich "auf höherer Ebene", bei dem ein Genom durch die Reihenfolge seiner Gene modelliert wird. Sind von zwei oder mehr Genomen die jeweils korrespondierenden Gene bekannt und werden diese mit eindeutigen Nummern versehen, ergibt sich eine einfache kombinatorische Struktur: Jedes Genom entspricht einer Permutation der Zahlen 1,...,n. In diesem Modell beschränkt sich ein Genomvergleich auf den Vergleich von Permutationen von Zahlen. In der Vergangenheit wurden verschiedene Distanzmodelle und Algorithmen zum Genomvergleich auf Basis von Permutationen definiert, die in diesem Seminar näher betrachtet werden sollen.

Voraussetzungen

Algorithmen und Datenstrukturen I und II

Zeitplan

DatumThema
21.04.2003 - entfällt - (Ostermontag)
28.04.2003 Vorbesprechung
05.05.2003 Nadeau/Taylor (1984)
12.05.2003 Sankoff (1992)
19.05.2003 Ozery-Flato/Shamir (2003), Kececioglu/Sankoff (1994)
26.05.2003 Kececioglu/Sankoff (1994)
02.06.2003 Kececioglu/Sankoff (1994), Kaplan/Shamir/Tarjan (1999)
09.06.2003 - entfällt - (Pfingstmontag)
16.06.2003 Kaplan/Shamir/Tarjan (1999)
23.06.2003 Kaplan/Shamir/Tarjan (1999)
30.06.2003 Kaplan/Shamir/Tarjan (1999)
07.07.2003 Caprara (1999) -- Vortrag Julia Mixtacki
14.07.2003 Bader/Moret/Yan (2001)
21.07.2003 Bergeron (2001a)
28.07.2003 Bergeron (2001a)

Literatur

Einführungen in das Thema
  • Nadeau/Taylor: PNAS 81, 814, 1984.
  • Sankoff: Proc. 3rd CPM (LNCS 644), 121-135, 1992.
  • Ozery-Flato/Shamir 2003: J. Bioinf. Comput Biol. (to appear)
Signed reversal sorting problem
  • Kececioglu/Sankoff: Proc. 5th CPM (LNCS 807), 307-325, 1994.
  • Bafna/Pevzner: SIAM J. Computing 25, 272-289, 1996.
  • Hannenhalli/Pevzner: J. ACM 46, 1-27, 1999.
  • Berman/Hannenhalli: Proc. 7th CPM (LNCS 1075), 168-185, 1996.
  • Kaplan/Shamir/Tarjan: SIAM J. Computing 29, 880-892, 1999.
  • Bergeron: Proc. 12th CPM (LNCS 2089), 106-117, 2001a.
  • Bergeron: Proc. 1st WABI (LNCS 2149), 164-174, 2001b.
Signed reversal distance problem
  • Berman/Hannenhalli 1996, s.o.
  • Bader/Moret/Yan: J. Comput. Biol. 8, 483-492, 2001.
  • Bergeron/Heber/Stoye: Bioinformatics 18 (Suppl. 2) S54-S63, 2002.
Unsigned reversal sorting problem
  • Kececioglu/Sankoff: Algorithmica 13, 180-210, 1995.
  • Bafna/Pevzner 1996, s.o.
  • Caprara: SIAM J. Disc. Math. 12, 91-110, 1999.
Transposition distance problem
  • Bafna/Pevzner: SIAM J. Discrete Math. 11(2), 224-240, 1998.
Translocation distance problem
  • Kececioglu/Ravi: Proc. SODA, 604-613, 1995.
  • Hannenhalli: Discrete Appl. Math. 71, 137-151, 1996.
Reversal and translocation sorting problem
  • Hannenhalli/Pevzner: Proc. 36th FOCS, 581-592, 1995.
  • Tesler: J. Comp. Sys. Sci. 65(3), 587-609, 2002.
  • Ozery-Flato/Shamir 2003, s.o.
Breakpoint distance
  • Blanchette/Kunisawa/Sankoff: J. Mol. Evol. 49, 193-203, 1999.
Multichromosomal rearrangements
  • Tesler: J. Comput. Syst. Sci. 65, 587-609, 2002.
  • Hannenhalli/Pevzner: Proc. 36th FOCS, 581-592, 1995.
Syntenic distance
  • ...
Interval distance
  • Bergeron/Stoye: Proc. COCOON 2003. (to appear)