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
| Datum | Thema |
|---|
| 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)