Μαρκοβιανή Αλυσίδα Μόντε Κάρλο στη Βιολογία

Μέθοδος Μόντε Κάρλο

Οι μέθοδοι Μόντε Κάρλο είναι μεγάλη κατηγορία υπολογιστικών αλγορίθμων που στηρίζονται σε τυχαία δειγματοληψία με σκοπό την εξαγωγή αριθμητικών αποτελεσμάτων.

Μαρκοβιανή αλυσίδα Μόντε Κάρλο (Markov Chain Monte Carlo , MCMC)

Όταν η κατανομή πιθανότητας της μεταβλητής είναι παραμετροποιημένη, πολλές φορές γίνεται χρήση της Mαρκοβιανής Αλυσίδας.
Οι μέθοδοι Μαρκοβιανής αλυσίδας Μόντε Κάρλο (Markov chain Monte Carlo, MCMC)  βασίζονται στη δημιουργία μιας λογικής μαρκοβιανής αλυσίδας με μια προκαθορισμένη στάσιμη κατανομή πιθανότητας.
Όπως αναφέρθηκε προηγουμένως, ο Νόμος των Μεγάλων Αριθμών αποτελεί τη βάση των μεθόδων Μόντε Κάρλο και μπορεί να εφαρμοστεί εξίσου και στις μεθόδους MCMC καθώς αυτό μας επιτρέπει να αγνοήσουμε παντελώς την εξάρτηση μεταξύ των τιμών της μαρκοβιανής αλυσίδας, αφού μπορούμε να υπολογίσουμε από τις τιμές τα χαρακτηριστικά που μας ενδιαφέρουν. Κοινώς, αν γνωρίζουμε τη στάσιμη κατανομή της αλυσίδας τότε μπορούμε να λάβουμε πληροφορίες για χαρακτηριστικά όπως πληθυσμιακός μέσος, τυπική απόκλιση κλπ, απλά περιμένοντας να συγκλίνει η αλυσίδα δηλαδή να επιτευχθεί στασιμότητα ή ισορροπία.
Είναι επιθυμητό οι τιμές του δείγματος να προσομοιάζουν τις τιμές από τη ζητούμενη συνάρτηση κατανομής.

Aρχή λειτουργίας μεθόδων MCMC

Η αρχή λειτουργίας των MCMC μεθόδων μπορεί να περιγραφεί συνοπτικά ως εξής:
Έστω ότι γνωρίζουμε μια συνάρτηση πυκνότητας πιθανότητας ή μια συνάρτηση μάζας πιθανότητας, την f, τότε δημιουργούμε ένα μαρκοβιανό πυρήνα Κ με μία στάσιμη κατανομή και μετά παράγουμε μία μαρκοβιανή αλυσίδα {Χₜ} κάνοντας χρήση του πυρήνα έτσι ώστε η στάσιμη κατανομή να είναι η f.Η μεγαλύτερη δυσκολία έγκειται στην κατασκευή του πυρήνα Κ.
Η συνθήκη της εργοδικότητας είναι απαραίτητη έτσι ώστε η Μαρκοβιανή αλυσίδα να μπορεί να περάσει από όλες τις δυνατές καταστάσεις με πεπερασμένο πλήθος βημάτων.

Αλγόριθμος Metropolis-Hastings

Βασική ιδέα του αλγορίθμου Metropolis-Hastings είναι η προσομοίωση μιας αλυσίδας Μαρκόφ με στάσιμη κατανομή (δηλαδή την κατανομή στόχο). Χρησιμοποιείται επίσης μια κατανομή δικής μας πρότασης. Από τον αλγόριθμο Metropolis-Hastings προκύπτει μία αλυσίδα Μαρκόβ καθώς η τελική τιμή εξαρτάται μόνο από την τωρινή κατάσταση και όχι από τις προηγούμενες καταστάσεις.
Ο αλγόριθμος Metropolis-Hastings είναι στην ουσία μια διαδικασία αποδοχής-απόρριψης.
Το πρώτο βήμα είναι να επιλέξουμε ένα αυθαίρετο σημείο εκκίνησης. Στη συνέχεια μετά από κάθε βήμα i η κατάσταση της αλυσίδας προσομοιώνεται ως εξής: κάθε βήμα παρέχει μία υποψήφια κατάσταση και αυτή γίνεται αποδεκτή ή απορριπτέα. Το κριτήριο αποδοχής εξαρτάται από τη συνάρτηση πυκνότητας πιθανότητας. Αν η τωρινή κατάσταση έχει μεγαλύτερη συνάρτηση πυκνότητας πιθανότητας από την προηγούμενη τότε η τωρινή είναι αποδεκτή. Όταν η τωρινή κατάσταση δεν είναι αποδεκτή, απορρίπτεται και τότε η προηγούμενη κατάσταση επαναλαμβάνεται.
Ένα από τα σημαντικότερα πλεονεκτήματα του αλγορίθμου Metropolis-Hastings είναι ότι εξασφαλίζει υπό ελάχιστες συνθήκες τη σύγκλιση μιας ακολουθίας η οποία προσομοιώνεται στην κατανομή στόχο που θέτουμε. Επίσης, είναι αρκετά δημοφιλής διότι σε πάρα πολλά ρεαλιστικά προβλήματα αρκεί να γνωρίζουμε την συναρτησιακή μορφή της κατανομής στόχου και της κατανομής-πρότασης, αφού ο αναλυτικός υπολογισμός αυτών των σταθερών είναι εξαιρετικά δύσκολος και σε πολλές περιπτώσεις αδύνατος.
Μια ειδική περίπτωση του αλγορίθμου Metropolis-Hastings είναι ο λεγόμενος τυχαίος περίπατος (random walk).

Μαρκοβιανή Αλυσίδα Μόντε Κάρλο στη φυλογένεση

Στην μοριακή φυλογένεση είναι πολύ διαδεδομένο να χρησιμοποιούνται μπεϋζιανές μέθοδοι. Αν και αυτές οι μέθοδοι είναι δυσνόητες , τα λογισμικά που τις χρησιμοποιούν, κατασκευάζουν αποτελεσματικά μπεϋζιανά φυλογεντικά μοντέλα φιλικά προς τον χρήστη . Οι μπεϋζιανές φυλογενετικές  μέθοδοι ξεκίνησαν να χρησιμοποιούνται τη δεκαετία του '90 και από τότε άλλαξαν τον τρόπο ανάλυσης της αλληλουχίας του γονιδιώματος. Παραδείγματα τέτοιων αναλύσεων είναι η φυλογεωγραφική ανάλυση της εξάπλωσης του ιού στο ανθρώπινο είδος και τα συμπεράσματα από την μετανάστευση των ειδών. Ταυτόχρονα , τα μοντέλα που κατασκευάζονται , αν και είναι εύκολο να δημιουργηθούν , μπορεί να βγάζουν λάθος συμπεράσματα , να παραπλανούν , σε περίπτωση που ο χρήστης δεν είναι γνώστης των παραμέτρων και των μαθηματικών υποθέσεων.
Στις μέρες μας, όλα τα μπεϋζιανά φυλογενετικά προγράμματα χρησιμοποιούν τη μαρκοβιανή αλυσίδα Μόντε Κάρλο (MCMC) ή τον αλγόριθμο των Metropolis-Hastings. Παρόλα αυτά, επειδή ο MCMC αλγόριθμος  αποτελεί ένα μείγμα επιστήμης και τέχνης , είναι επιτακτική η ανάγκη να κατανοηθούν οι τρόποι λειτουργίας του για την ορθή χρήση των προγραμμάτων.

Μέθοδος Bayes

H μέθοδος αυτή αποτελεί μία μεθοδολογία για την στατιστική συμπερασματολογία. Βασίζεται στο Θεώρημα Μπέυζ με τύπο :
f(θ|D) =(1/z)f(θ)f(D|θ)
όπου D είναι τα παρατηρηθέντα δεδομένα και θ η άγνωστη παράμετρος. Ταυτόχρονα , η f(θ) ονομάζεται εκ των προτέρων κατανομή , η οποία βασίζεται στη γνώση μας για το θ , πριν την επεξεργασία δεδομένων. Μετά την επεξεργασία δημιουργείται η εκ των υστέρων κατανομή f(θ|D) με z να είναι μία σταθερά ,με ανώτατη τιμή το 1, και τη f(D|θ) να αποτελεί την πιθανοφάνεια. Ο παραπάνω τύπος υποδεικνύει ότι η γνώση οφείλεται στον συνδυασμό της προηγούμενης γνώσης με τα καινούργια δεδομένα.
Στη φυλογένεση, η τοπολογία των δέντρων και το μοντέλο υποκατάστασης προσδιορίζουν από κοινού το στατιστικό μοντέλο των δεδομένων.Οι διαφορετικές τοπολογίες των δένδρων αντιστοιχούν έτσι σε διαφορετικά μοντέλα και τα δεδομένα είναι συνήθως ευθυγράμμιση μοριακής ακολουθίας ή ευθυγράμμιση μορφολογικών χαρακτήρων (ή συνδυασμός και των δύο).

Τι είδους δεδομένα μπορούν να χρησιμοποιηθούν για φυλογενετική ανάλυση

Οι πιο κοινοί τύποι δεδομένων που χρησιμοποιούνται για φυλογενετική ανάλυση είναι το DNA και η στοίχιση αμινοξικών ακολουθιών. Τα δεδομένα –πληροφορίες που θα χρησιμοποιηθούν στα φυλογενετικά προγράμματα χρειάζεται να είναι αποτελέσματα από την στοίχιση των ακολουθιών με έμφαση στην ακρίβεια της στοίχισης , η οποία διαδραματίζει σημαντικό ρόλο στην φυλογενετική ανάλυση. Αξίζει να τονισθεί ότι έχει γίνει μεγάλη προσπάθεια να κατασκευαστούν μοντέλα για τις διαγραφές και τις ενθέσεις αμινοξέων. Επιπροσθέτως , για την εκτίμηση της φυλογένεσης μεταξύ των  ειδών , οι ακολουθίες χρειάζεται να είναι ορθόλογες. Σε αντίθεση , η λανθασμένη χρήση των παράλογων ακολουθιών μπορεί να οδηγήσει σε άστοχες σχέσεις-αποτελέσματα.

Πόσες επαναλήψεις και πόσα δείγματα απαιτούνται

Ο χρόνος που χρειάζεται ο  αλγόριθμος MCMC για  να αποκτήσει μία αξιόπιστη εκτίμηση για την εκ των υστέρων κατανομή διαρκεί τόσο ώστε  να μην επιβαρύνει τον υπολογιστή που τον εκτελεί. Όμως , αφού δεν υπάρχουν αυτόματοι κανόνες παύσης , ο χρήστης πρέπει να έχει σκεφτεί τον αριθμό των επαναλήψεων και , ύστερα , να αποφασίσει αν η μαρκοβιανή αλυσίδα είναι τόσο μεγάλη όσο χρειάζεται ή απαιτούνται κι άλλες επαναλήψεις . Οι MCMC αλγόριθμοι τείνουν να παράγουν τεράστια αρχεία ως output. Για την εξοικονόμηση χώρου στο δίσκο, τα δείγματα λαμβάνονται μετά από ένα καθορισμένο αριθμό επαναλήψεων. Λόγου χάριν, για παράδειγμα, η εκτέλεση μιας αλυσίδας MCMC για 10⁷ επαναλήψεις και η χρήση μιας συχνότητας δειγματοληψίας 10³ επαναλήψεων, θα παράγει 10⁴ δείγματα.
Υπόψη ότι σε ορισμένα προγράμματα (όπως MCMCΤree και BPP), κάθε επανάληψη MCMC αποτελείται από μια σταθερή ακολουθία προτάσεων MCMC, ενώ σε κάποιες άλλες(όπως MrBayes και BEAST), αποτελείται από μία πρόταση, τυχαία επιλεγμένη από μια συλλογήπροτάσεων. Έτσι, αν υπάρχουν στο μοντέλο 1.000 παράμετροι και εάν κάθε πρόταση αλλάζει μία παράμετρο, κάθε επανάληψη MCMC στο πρώτο πρόγραμμα αξίζει περίπου 1.000 επαναλήψεις στα τελευταία προγράμματα. Έτσι, οι επαναλήψεις MCMC από διαφορετικά προγράμματα δεν είναι συγκρίσιμες. Ο βιολόγος θα πρέπει να στοχεύει να συγκεντρώσει ένα λογικό (όσο το δυνατόν πιο πιθανό) αποτελεσματικό μέγεθος δείγματος για κάθε παράμετρο.

Γιατί θα έπρεπε να εκτελέσουμε τον αλγόριθμο MCMC χωρίς δεδομένα

Είναι χρήσιμο να εκτελεστεί η δειγματοληψία αλγορίθμου MCMC στην εκ των προτέρων κατανομή .Αυτό επιτυγχάνεται με τον καθορισμό της πιθανοφάνειας f(D|θ)  σε 1 στην εξίσωση του Bayes. Ορισμένα προγράμματα δημιουργούν μια dummy "κενή" στοίχιση που μπορεί να χρησιμοποιηθεί για να επιτευχθεί το ίδιο αποτέλεσμα.Οι εκτελέσεις πρέπει επίσης να αξιολογούνται για καλή σύγκλιση και ανάμειξη.Η εκτέλεση της αλυσίδας, χωρίς δεδομένα. είναι ένας καλός τρόπος για τον έλεγχο της ορθότητας του λογισμικού, επειδή ο μέσος όρος, η διακύμανση και άλλα στοιχεία της εκ των προτέρων  είναι συχνά αναλυτικά διαθέσιμα και μπορούν να ελεγχθούν βάσει του δείγματος MCMC.
Το δείγμα από την εκ των προτέρων μπορεί επίσης να συγκριθεί με το δείγμα από την εκ των υστέρων (η οποία παράγεται με τη χρήση των δεδομένων) για να εκτιμηθεί ο τρόπος πληροφόρησης των δεδομένων και αν υπάρχουν σοβαρές συγκρούσεις μεταξύ της πρώτης και των δεδομένων.Ένας υψηλός βαθμός ομοιότητας μεταξύ της πρώτης και της δεύτερης κατανομής υποδηλώνει ότι τα δεδομένα περιέχουν ελάχιστες πληροφορίες σχετικά με τις παραμέτρους. Σημαντική αλληλοεπικάλυψη μεταξύ αυτών των δύο κατανομών σημαίνει ότι τα δεδομένα είναι πληροφοριακά  και λογικά. Αντιθέτως , αν δεν υπάρχει αλληλοεπικάλυψη , τότε μπορεί να υπάρχει σύγκρουση μεταξύ της πρώτης κατανομής και των δεδομένων.

Εφαρμογές

Είναι γεγονός ότι το θεώρημα του Bayes και η μαρκοβιανή αλυσίδα Μόντε Κάρλο έχουν χρησιμοποιηθεί στην κατανόηση  και την απόδειξη της εξέλιξης των ειδών . Με αυτήν την γνώση ,για παράδειγμα,  έχουν κατασκευασθεί εφαρμογές για την συμπερασματολογία και τον υπολογισμό της αβεβαιότητας στην φυλογένεση, για την συμπερασματολογία των επιπέδων της εξέλιξης και των αρχέγονων περιοχών , για την διερεύνηση  μοτίβων σε παθογόνους οργανισμούς όπως και  για τη μοντελοποίηση της διαφοροποίησης και της εξαφάνισης των ειδών.

Εφαρμογές MCMC στην βιολογία συστημάτων

Πολλοί κλάδοι της βιολογίας, και ιδίως η bιοπληροφορική, η Υπολογιστική Βιολογία και η Γενετική, βρίσκονται εν μέσω μιας επανάστασης, εξαιτίας της ανάπτυξης των Μπεϋζιανών μεθόδων ανάλυσης. Ο λόγος είναι ότι τα βιολογικά φαινόμενα είναι πολύπλοκα και υπάρχει πολύς θόρυβος στα πειραματικά δεδομένα. Οι παραδοσιακές στατιστικές τεχνικές δεν μπορούν να αντεπεξέλθουν στην ανάλυση πολύπλοκων, μη γραμμικών μοντέλων. Ο κυριότερος περιοριστικός παράγοντας στην εφαρμογή Μπεϋζιανών μεθόδων είναι υπολογιστικός. Για μη τετριμμένα προβλήματα, αναλυτικές προσεγγίσεις στην Μπεϋζιανή συμπερασματολογία δεν είναι εφικτές. Τις τελευταίες δεκαετίες έχει σημειωθεί σημαντική πρόοδος στην ταχύτητα των υπολογιστικών συστημάτων καθώς επίσης και στην ανάπτυξη υπολογιστικά αποδοτικών αλγορίθμων για Μπεϋζιανή συμπερασματολογία. Η πιο σημαντική εξέλιξη είναι η ανάπτυξη ενός εύρους τεχνικών που βασίζονται στην MCMC. Προσεκτικά σχεδιασμένοι MCMC αλγόριθμοι που εκτελούνται σε γρήγορους υπολογιστές είναι ικανοί να επιλύσουν ένα εξαιρετικά μεγάλο εύρος βιολογικών προβλημάτων που θεωρούνταν μη επιλύσιμα μόλις λίγα χρόνια πριν.
Ακολουθούν παραδείγματα εφαρμογών της τεχνικής MCMC για επίλυση προβλημάτων βιολογικού ενδιαφέροντος.

Γενετική

Ο κλάδος της γενετικής έχει αξιοποιήσει την τεχνική MCMC σε πολλές εφαρμογές Μπεϋζιανής συμπερασματολογίας. Στον τομέα της γενετικής πληθυσμών έχει αξιοποιηθεί για την εκτίμηση παραμέτρων σε δημογραφικά μοντέλα και για τον εντοπισμό συμβάντων φυσικής επιλογής. Στον τομέα της γονιδιωματικής έχει χρησιμοποιηθεί για την ανάλυση ακολουθιών, για την ταυτοποίηση σημειακών μεταλλάξεων, για την εξαγωγή του απλοτύπου μέσω δειγμάτων πληθυσμού και για την εκτίμηση των επιπέδων της γονιδιακής έκφρασης και ρύθμισης. Στον τομέα της γενετικής ανθρώπου έχει χρησιμοποιηθεί κυρίως για την γονιδιακή χαρτογράφηση.

Ανάλυση αλληλουχιών

Η τεχνική ΜCMC μπορεί να χρησιμοποιηθεί για την αλληλούχιση γονιδιωμάτων. Σε αντίθεση με τις περισσότερες μεθόδους αλληλούχισης ολόκληρων γονιδιωμάτων, οι οποίες επιλέγουν μόνο μία γονιδιωματική αλληλουχία μεταξύ πολλών εναλλακτικών υποθέσεων, που μπορούν να συναχθούν από τα δεδομένα, η προσέγγιση με χρήση MCMC παράγει κατανομές υποθέσεων συναρμολόγησης του προς αλληλούχιση γονιδιώματος μέσω εκ των υστέρων πιθανοτήτων, παρέχοντας ένα στατιστικό πλαίσιο για την εκτίμηση εναλλακτικών υποθέσεων και της αβεβαιόττας του προτεινόμενου μοντέλου.
Επίσης, έχει αναπτυχθεί μέθοδος για την ανίχνευση ανασυνδυασμών. Η συμπερασματολογία μέσω αυτής της μεθόδου έγινε με Μπεϋζιανό τρόπο, χρησιμοποιώντας την τεχνική MCMC. O σκοπός της μεθόδου ήταν να εντοπιστούν με ακρίβεια σημεία σε στοιχίσεις αλληλουχιών DNA, τα οποία αντιστοιχούν σε σημεία θραύσης και ανασυνδυασμού, σε έναν μικρό αριθμό τάξα. Η προσέγγιση αυτή μοντελοποιεί την αλληλουχία των τοπολογιών  των φυλογενετικών δέντρων σε μια πολλαπλή στοίχιση αλληλουχιών. Ο αλγόριθμος επιστρέφει την εκ των υστέρων πιθανότητα κάθε τοπολογίας δέντρου, η οποία χρησιμοποιείται για την ανίχνευση των περιοχών ανασυνδυασμού και τον εντοπισμό των σημείων θραύσης.

Πρωτεωμική

Η τεχνική MCMC χρησιμοποιήθηκε για τον εντοπισμό μοριακών βιοδεικτών σε δεδομένα ανάλυσης υγρής χρωματογραφίας-φαρματομετρίας μάζας (LC-MS). Τα δεδομένα που εξάγονται από μια ανάλυση LC-MS προέρχονται κατά κανόνα από μικρά δείγματα και χαρακτηρίζονται από υψηλή διαστασιμότητα. Η ανάλυση δεδομένων μέσω Μπαεσιανών μοντέλων με χρήση της τεχνικής MCMC φάνηκε να έχει καλύτερα αποτελέσματα σε σχέση με άλλες προσεγγίσεις, όταν το μέγεθος τους δείγματος είναι μικρό ή όταν ο αριθμός των επιλεγμένων πρωτεϊνών για κατηγοριοποίηση είναι μεγάλος.

Γενετικά Ρυθμιστικά Δίκτυα

Η κατασκευή ενός λεπτομερούς χάρτη του συνόλου των μοριακών αλληλεπιδράσεων ενός οργανισμού είναι ένας από τους βασικούς στόχους της Βιολογίας Συστημάτων. Επί του παρόντος, αυτά τα πολύπλοκα βιολογικά δίκτυα παραμένουν σε μεγάλο βαθμό άγνωστα. Η διαθεσιμότητα διαφορετικών τύπων μετρήσεων που προέρχονται από διάφορα συστατικά αυτών των δικτύων καθιστά δυνατή την προσπάθεια ανασύστασης ενός δικτύου μέσω τέτοιων μετρήσεων. Τα Μπεϋζιανά δίκτυα είναι κατάλληλα για τον σκοπό αυτόν, εξαιτίας της πιθανοκρατικής τους φύσης και της ευελιξία τους, ως προς την ενσωμάτωση παρεμβάσεων και πρόσθετων πηγών πληροφοριών. Όταν τα Μπεϋζιανά μοντέλα υιοθετούνται ως μοντέλα για Γενετικά Ρυθμιστικά Δίκτυα, συνήθως συνδυάζονται με χρήση της τεχνικής MCMC. Αυτό συμβαίνει γιατί τα διαθέσιμα δεδομένα είναι γενικώς μη επαρκή και είναι αδύνατον να γίνει απαρίθμηση όλων των πιθανών δικτύων ακόμα και για έναν σχετικά μικρό αριθμό κόμβων. Η τεχνική MCMC έχει το πλεονέκτημα ότι είναι εγγυημένο θεωρητικά ότι θα συγκλίνει σε μια εκ των υστέρων κατανομή.