Διερεύνηση συσχετίσεων μακράς εμβέλειας σε ακολουθίες συμβόλων
Creators: name: Παπαπέτρου, Μαρία Β.
Publisher: name: Aristotle University of Thessaloniki
Year: 2020
Subjects: Ακολουθίες συμβόλων
Εκτίμηση τάξης μαρκοβιανών αλυσίδων
Δεσμευμένη αμοιβαία πληροφορία
Στατιστικός έλεγχος
DNA
Symbol sequences
Markov chain order estimation
Conditional mutual information
Significance test

description: Η παρούσα διατριβή έχει ως στόχο την εισαγωγή μιας νέας μεθοδολογίας με σκοπό την εκτίμηση της τάξης μαρκοβιανών αλυσίδων, χρησιμοποιώντας το μέτρο της δεσμευμένης αμοιβαίας πληροφορίας (Conditional Mutual Information, CMI). Αρχικά σε μια πρώτη προσέγγιση, προτείνουμε έναν έλεγχο σημαντικότητας, τον ονομαζόμενο CMI- έλεγχο, εφαρμόζοντας επαναληπτικά έλεγχο τυχαιοποίησης για το CMI αυξάνοντας κάθε φορά την τάξη. Σε δεύτερο επίπεδο προτείνονται παραμετρικοί έλεγχοι σημαντικότητας της δεσμευμένης αμοιβαίας πληροφορίας αυξανόμενης τάξης. Η μηδενική κατανομή του CMI προσεγγίζεται από κανονική και γάμμα κατανομή, εξάγοντας τις αναλυτικές εκφράσεις των παραμέτρων τους, καθώς και γάμμα κατανομή όπου εκτιμούμε τις παραμέτρους της από τη μέση τιμή και τη διασπορά της κανονικής κατανομής. Το πλεονέκτημα ενός παραμετρικού ελέγχου έναντι ενός ελέγχου τυχαιοποίησης είναι το υπολογιστικό κέρδος. Επομένως, αν ένας παραμετρικός έλεγχος εμφανίζει την δυνατότητα να μπορεί να εκτιμήσει με ακρίβεια την πραγματική τάξη μιας συμβολοσειράς και συμπεριφέρεται εξίσου καλά με τον έλεγχο τυχαιοποίησης, τότε αυτό αποτελεί ισχυρό πλεονέκτημα καθώς μας επιτρέπει να εφαρμόσουμε τη συγκεκριμένη μέθοδο σε πολύ μεγάλες ακολουθίες συμβόλων, όπως αυτές των DNA ακολουθιών. Η εφαρμογή της μεθόδου CMI σε πραγματικές ακολουθίες DNA, όπου πρόκειται για συμβολοσειρές με μεγάλα μήκη και μακράς εμβέλειας συσχετίσεις (μεγάλη μνήμη), μας οδήγησε στην ανάγκη δημιουργίας ενός βελτιωμένου αλγορίθμου υπολογισμού του CMI για αυξανόμενη τάξη. Ο νέος αυτός αλγόριθμος που προτείνουμε βελτιώνει τα θέματα που προκύπτουν σχετικά με τον χρόνο υπολογισμού και τον χώρο στην μνήμη σε εφαρμογές τέτοιου μεγέθους. Στην πορεία, σε μια προσπάθειά μας να βελτιώσουμε τη μέθοδο εκτίμησης που προτείνουμε, εισάγουμε τη χρήση του μέτρου της δεσμευμένης αμοιβαίας πληροφορίας Tsallis (TCMI) για την εκτίμηση μαρκοβιανών αλυσίδων χαμηλής και υψηλότερης τάξης, καθώς και για την εκτίμηση μακράς εμβέλειας συσχετίσεων (LRC) σε ακολουθίες DNA. Ένας ακόμη σκοπός της παρούσας διατριβής είναι η πρόταση μιας διαφορετικής προσέγγισης, όσον αφορά τη δομή των μακράς εμβέλειας συσχετίσεων, κατά την οποία διερευνούμε τις LRCs μέσω της εκτίμησης της τάξης μαρκοβιανών αλυσίδων. Η συγκεκριμένη μέθοδος μπορεί να αξιολογήσει αν η ακολουθία συμβόλων προέρχεται από μαρκοβιανή αλυσίδα χαμηλής τάξης ή έχει δομή LRC, που είναι στατιστικά ισοδύναμο με μαρκοβιανή αλυσίδα υψηλής τάξης η οποία δεν μπορεί να εκτιμηθεί με βάση το δεδομένο μήκος της συμβολοσειράς. Κατά την διερεύνησή μας γίνεται μελέτη ακολουθιών τόσο του ανθρώπινου γενετικού υλικού όσο και του DNA άλλων πρότυπων οργανισμών. Στόχος μας είναι να δώσουμε απάντηση στα ερωτήματα που μας απασχολούν, όπως αν υπάρχουν συσχετίσεις μεταξύ των περιοχών των οργανισμών αυτών και αν ναι τι είδους συσχετίσεις είναι αυτές. Τελευταία, ένα επίσης ερώτημα που απασχολεί τους επιστήμονες είναι αν οι μακράς εμβέλειας συσχετίσεις εντοπίζονται στο DNA όπου περιέχει κωδικοποιούσες και μη-κωδικοποιούσες περιοχές ή εντοπίζονται μονάχα σε οργανισμούς όπου περιέχουν μόνο μη-κωδικοποιούσες ακολουθίες. Το ερώτημα αυτό είναι πολύ σημαντικό καθώς τα αποτελέσματα βοηθάνε στην κατανόηση της δομής και της εξέλιξης του DNA όπως και στον διαχωρισμό των κωδικοποιουσών και μη κωδικοποιουσών περιοχών.
description: The aim of the present PhD thesis is to introduce the Conditional Mutual Information (CMI) for the estimation of the Markov chain order. First, we propose a significance test, CMI-test, where the randomized symbol sequences are formed by random permutation of the components of the original symbol sequence. The significance test is applied for increasing m and the Markov chain order is estimated by the last order for which the null hypothesis is rejected. Then, we propose parametric significant tests for the conditional mutual information. The null distribution of CMI is approximated with a normal and gamma distribution deriving analytic expressions of their parameters, and a gamma distribution deriving its parameters from the mean and variance of the normal distribution. The advantage of parametric test over a randomization test is the computational efficiency, allowing the order estimation based on CMI to be possible for very long symbol sequences, such as the DNA sequences. The use of Markov chain order estimation from symbol sequences of systems exhibiting long memory or long-range correlations (LRC), such as DNA sequences, led us to create an optimized iterative algorithm for calculating CMI at increasing order m. Afterwards, we consider the Tsallis entropy and define the Tsallis conditional mutual information (TCMI) for Markov chain order estimation, which is more suitable to identify large orders suggesting effectively LRC. Another purpose of this thesis is to propose a different approach to the structure of long-range correlations, in which we explore LRCs through the estimation of the order of Markov chains. During our investigation, sequences of both human genomes and DNA of other types are studied. Our goal is to answer the questions that concern us, such as whether there are correlations between the regions of these organisms and if so what kind of correlations are they. Finally, another question that concerns scientists is whether long-range correlations are found in DNA where it contains coding and non-coding regions or are found only in organisms where they contain non-coding sequences. This question is very important as the results help us to understand the structure and evolution of DNA as well as to separate the coding and non-coding regions.