CoCoNUT: Ein Software-System zum multiplen Genomvergleich
Final Report Abstract
Die Erbinformation eines Organismus, das Genom, ist in DNA-Molekülen gespeichert, die aus den vier Basen Guanin, Cytosin, Adenin und Thymin aufgebaut sind. Die Abfolge der Basen stellt letztendlich den Bauplan für den ganzen Organismus dar. Allerdings ist die Erbinformation in höheren Organismen nicht gleichmäßig verteilt. Das menschliche Genom besteht zum Beispiel aus über 3 Milliarden Basen, von denen aber nur ca. 1,8% Gene bilden. Ein Gen ist ein Abschnitt des Genoms, der ein Protein kodiert, also den Bauplan für ein Zelleiweiß darstellt. Im Laufe der Evolution kommt es zu Mutationen, d.h. es ändern sich einzelne Basen in der DNA. Es kann aber auch zu Umstrukturierungen des gesamten Genoms kommen; diese Ereignisse sind jedoch viel seltener. Meistens ist eine Mutation bzw. eine Umstrukturierung nachteilig im Kampf ums Überleben, manchmal ist sie jedoch von Vorteil und breitet sich deshalb über die Nachfahren durch natürliche Selektion aus. Durch moderne Sequenziertechnik ist es heutzutage möglich, die Erbinformation von Organismen, d.h. die Abfolge der Basen im Genom, äußerst effizient zu entschlüsseln. In dem Projekt "CoCoNUT: Ein Software-System zum multiplen Genomvergleich" wurden Informatikmethoden zur Analyse großer genomischer Datenmengen entwickelt. Im Zentrum der Arbeit stand die computergestützte vergleichende Genomanalyse (computational comparative genomics), bei der die vollständigen Genome von mehreren Organismen miteinander verglichen werden, z.B. von Mensch, Maus und Ratte. Die Ziele solcher Analysen sind u.a. die Berechnung von sogenannten Alignments (an denen man Gemeinsamkeiten und Unterschiede zwischen den Genomen ablesen kann) und das automatisierte Erkennen von Genomumstrukturierungen. Die vergleichende Genomanalyse beruht auf der Tatsache, dass funktionelle Bereiche des Genoms (z.B. Gene) im Laufe der Evolution stärker konserviert werden als nicht funktioneile Bereiche. Der Grund für dieses Phänomen ist, dass eine Mutation in einem funktionellen Bereich bewirken kann, dass die damit gekoppelte Funktion verloren geht. Dies wirkt sich in der Regel negativ für das Überleben des Individuums aus. Eine Mutation in einem nicht funktionellen Bereich bleibt dagegen folgenlos. In dem Projekt wurden u.a. neue Algorithmen, und Datenstrukturen zur effizienten Identifikation von konservierten Bereichen entwickelt. Zuerst wurden DNA-Abschnitte identifiziert, die in allen zu vergleichenden Genomen identisch sind. Auf Grund der Größe der Datenmengen muss dies mit möglichst wenig Speicherplatz und Rechenzeit geschehen. Diese Anforderung konnte mit Hilfe der neuen Datenstruktur "verstärktes Suffbcarray" (enhanced suffix array] erfüllt werden. Durch die stattgefundenen Mutationen sind die identifizierten DNA-Abschnitte in der Regel allerdings sehr kurz. Da kurze Übereinstimmungen auch zufällig auftreten können, müssen diese nun zu größeren Bereichen zusammengefasst (verkettet) werden. Die neuen Bereiche sind nicht mehr in allen Genomen identisch, müssen aber eine signifikante Ähnlichkeit aufweisen. Zur Bestimmung dieser Bereiche wurden neue Verkettungsalgorithmen (chaining algorithms] entwickelt, die Techniken aus der Algorithmischen Geometrie verwenden. Weiterhin wurden neue Algorithmen zur Rekonstruktion von Genomumstrukturierungen, die sich im Laufe der Evolution ereigneten, entwickelt. Dabei konnten neben Inversionen auch Transpositionen berücksichtigt werden. Schließlich wurden die theoretischen Fortschritte in Form eines Software-Werkzeuges für Anwender nutzbar gemacht.
Publications
- C. Wawra, M. Abouelhoda, and E. Ohlebusch. Efficient mapping of large cDNA/EST databases to genomes: A comparison of two different strategies. In Proc. German Conference on Bioinformatics, volume 71 of Lecture Notes in Informatics, pages 29-43. GI, 2005.
- E. Ohlebusch and M. Abouelhoda. Chaining algorithms and applications in comparative genomics. In S. Aluru, editor, Handbook of Computational Molecular Biology, chapter 15. Chapman & Hall/CRC Computer and Information Science Series, 2006.
- E. Ohlebusch and S. Kurtz. Space efficient computation of rare maximal exact matches between multiple sequences. Journal of Computational Biology, 15(4):357-377, 2008.
- E. Ohlebusch, M. Abouelhoda, and K. Hockel. A linear time algorithm for the inversion median problem in circular bacterial genomes. Journal of Discrete Algorithms^ 5:637- 646, 2007.
- E. Ohlebusch, M. Abouelhoda, K. Hockel, and J. Stallkamp. The median problem for the reversal distance in circular bacterial genomes. In Proc. 16th Annual Symposium on Combinatorial Pattern Matching, volume 3537 of Lecture Notes in Computer Science, pages 116-127, Berlin, 2005. Springer-Verlag.
- M. Abouelhoda and E. Ohlebusch. Chaining algorithms for multiple genome comparison. Journal of Discrete Algorithms, 3:321-341, 2005.
- M. Abouelhoda, S. Kurtz, and E. Ohlebusch. Enhanced suffix arrays and applications. In S. Aluru, editor, Handbook of Computational Molecular Biology, chapter 7. Chapman &; Hall/CRC Computer and Information Science Series, 2006.
- M. Abouelhoda. A chaining algorithm for mapping cDNA sequences to multiple genomic sequences. In Proc. 14th International Symposium on String Processing and Information Retrieval, volume 4726 of Lecture Notes in Computer Science, pages 1-13, Berlin, 2007. Springer-Verlag.
- M. Bader and E. Ohlebusch. Sorting by weighted reversals, transpositions, and inverted transpositions. In Proc. 10th Annual International Conference on Research in Computational Molecular Biology, volume 3909 of Lecture Notes in Computer Science, pages 564-578. Springer-Verlag, 2006.
