Μοντελοποίηση DNA ακολουθιών με κρυφές ημιμαρκοβιανές αλυσίδες για τη μελέτη των CpG islands
Creators: name: Γιαννόπουλος, Βασίλειος Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2015
Subjects: κρυφές μαρκοβιανές αλυσίδες
νησιά CpG
μοντελοποίηση DNA
hidden markov chains
CpG islands
DNA modeling

description: Στόχος της παρούσας εργασίας είναι η μοντελοποίηση των DNA ακολουθιών με κρυφά Μαρκοβιανά (ΚΜΜ) και Ημιμαρκοβιανά μοντέλα (ΚΗΜΜ) και η εφαρμογή της μοντελοποίησης αυτής σε πραγματικές DNA αλυσίδες με σκοπό την μελέτη και τον εντοπισμό των CpG islands σε αυτές. Τα CpG islands παρουσιάζονται κυρίως στους προμότορες και λειτουργούν ως διακόπτες on/off στο DNA. Με τον τρόπο αυτό, ρυθμίζεται η λειτουργία των γονιδίων που βρίσκονται αμέσως μετά από τους προμότορες. Αρχικά, παρατίθεται η βασική θεωρία των μοντέλων. Δίνεται η περιγραφή των χαρακτηριστικών τους και παρουσιάζονται τα τρία βασικά προβλήματα που προκύπτουν με την χρήση τους, μαζί με τις αντίστοιχες λύσεις: (α) το πρόβλημα αξιολόγησης, (β) το πρόβλημα αποκωδικοποίησης και (γ) το πρόβλημα εκπαίδευσης. Επίσης, παρουσιάζεται η αλγοριθμική κατασκευή των ΚΗΜΜ μέσω της επέκτασης του ΕΜ (Estimation-Maximization) αλγόριθμου για τα κρυφά Μαρκοβιανά μοντέλα, με σκοπό τον υπολογισμό των εκτιμητών μέγιστης πιθανοφάνειας. Στη συνέχεια, δίνεται η περιγραφή των βασικών και απαραίτητων αρχών της Βιολογίας που αφορούν τις DNA αλυσίδες, με συγκεκριμένο αντικείμενο μελέτης τον εντοπισμό των CpG islands σε αυτές. Κατόπιν, πραγματοποιείται μελέτη τριών πραγματικών DNA αλυσίδων με την εφαρμογή και χρήση των ΚΜΜ πρώτης και δεύτερης τάξης και των ΚΗΜΜ. Οι αλυσίδες αυτές είναι (α) το Χρωμόσωμα 21, (β) το Χρωμόσωμα 22 και (γ) το γονιδίωμα Zebrafish. Στην περίπτωση των ΚΜΜ χρησιμοποιούνται τα μοντέλα Markov πρώτης τάξης με πλήθος καταστάσεων 2 και 8 και Markov δεύτερης τάξης με πλήθος καταστάσεων 4 και 64. Για την περίπτωση των ΚΗΜΜ χρησιμοποιούνται μοντέλα στα οποία η εμβαπτισμένη Μαρκοβιανή αλυσίδα είναι πρώτης τάξης. Σε ότι αφορά τους χρόνους παραμονής, προσαρμόζονται τόσο συνεχείς, όσο και διακριτές κατανομές. Τέλος, μελετάται η ασυμπτωτική συμπεριφορά των ΚΜΜ, αλλά και των ΚΗΜΜ, με τρόπο κατάλληλο κάθε φορά για το αντίστοιχο μοντέλο.
description: The goal of this thesis is the modeling of DNA sequences with hidden Markov (HMM) and hidden semi-Markov (HSMM) models, as well as the application of the aforementioned modeling on real DNA sequences, in order to study and locate CpG islands in them. Most CpG islands appear in the promoter regions and work as on/off switches in DNA. This way, the function of the genes located after the promoter regions is controlled. In the beginning, we present the basic theory behind the models. After providing the description of the models, as well as their properties, we study the three basic problems that occur with their usage: (a) the evaluation problem, (b) the decoding problem and (c) the learning problem. The next step in our study is the algorithmic construction of HSMMs through the induction of the EM algorithm (Expectation-Maximization), from Hidden Markov Models, to Hidden Semi-Markov Models, in order to calculate the maximum likelihood estimators of the HSMMs. Afterwards, some fundamental information needed in regards to Biology and specifically the DNA and CpG islands is presented. Following this, we study three real DNA chains with the application and usage of both HMMs of first and second order, as well as HSMMs. The aforementioned chains are (a) Chromosome 21, (b) Chromosome 22 and (c) the Zebrafish genome. In the case of the HMMs, first order Markov models (with 2 and 8 states) and second order Markov models (with 4 and 64 states) are used, while in the case of HSMMs, models in which the underlying Markov chain is of first order are presented. While studying the holding times, both continuous and discrete distributions are fitted. Ultimately, we study the asymptotical behavior of the HMMs, as well as that of the HSMMs, appropriately for each model.