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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Μέθοδος Μόντε Κάρλο[Επεξεργασία | επεξεργασία κώδικα]

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

Αρχή Λειτουργίας Μεθόδων Μόντε Κάρλο[Επεξεργασία | επεξεργασία κώδικα]

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

Τα περισσότερα προβλήματα στα οποία βρίσκουν επίλυση οι μέθοδοι Μόντε Κάρλο μπορούν να κατηγοριοποιηθούν ως εξής:

  • Υπολογισμός ολοκληρωμάτων (Ολοκλήρωση Monte Carlo): Δηλαδή ο υπολογισμός αναμενόμενων τιμών (expected values) συναρτήσεων μιας ή περισσοτέρων ανεξάρτητων (τυχαίων) μεταβλητών.
  • Εύρεση ελαχίστου ή μεγίστου συναρτήσεων (Βελτιστοποίηση Monte Carlo): Σε πολλά προβλήματα κυρίως από τη βελτιστοποίηση διεργασιών, καταλήγουμε σε υπολογισμούς που αφορούν ακρότατα συναρτήσεων.[1]

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

Γεννήτρια Τυχαίων Αριθμών ονομάζεται ο αλγόριθμος δημιουργίας τυχαίων αριθμών σε κάποιο διάστημα ακολουθώντας κανονική κατανομή. Συνήθως το διάστημα είναι το [0,1] και οι αριθμοί δημιουργούνται ούτως ώστε να ακολουθούν Ομοιόμορφη Κατανομή (Uniform Distribution), δηλαδή την U[0,1]. [1]


Η κεντρική ιδέα της μεθόδου είναι η επανάληψη ενός πειράματος πολλές φορές μέχρι να προκύψουν κάποια αποτελέσματα, κάνοντας χρήση του Νόμου των Μεγάλων Αριθμών καθώς και άλλες μεθόδους στατιστικής συμπερασματολογίας.

Από μαθηματική άποψη μπορούμε να αντιληφθούμε τη μεθοδολογία ως εξής: οτιδήποτε χρειάζεται να γνωρίζουμε για μία τυχαία μεταβλητή Χ μπορούμε να το μάθουμε μέσα από την επαναλαμβανόμενη δειγματοληψία στη συνάρτηση κατανομής της Χ, δηλαδή την F(X).[2]

Πλεονεκτήματα των μεθόδων Μόντε Κάρλο[Επεξεργασία | επεξεργασία κώδικα]

Οι μέθοδοι Μόντε Κάρλο είναι αρκετά δημοφιλείς για τους εξής λόγους:

  • Ευκολία και Αποδοτικότητα: Οι αλγόριθμοι Μόντε Κάρλο τείνουν να είναι απλοί, ευέλικτοι και επιδέχονται περαιτέρω ανάπτυξης. Όταν εφαρμόζονται σε φυσικά συστήματα, οι τεχνικές Μόντε Κάρλο μπορούν να περιορίσουν πολύπλοκα μοντέλα σε μια σειρά βασικών γεγονότων και αλληλεπιδράσεων. Έτσι παρέχεται η δυνατότητα να κωδικοποιηθεί η συμπεριφορά ενός μοντέλου μέσα από μια σειρά κανόνων πλήρως εφαρμοσμένων σε ηλεκτρονικό υπολογιστή. Κατ' επέκταση, πολύ γενικά μοντέλα υψηλής τυχαιότητας μπορούν να εφαρμοστούν και να μελετηθούν σε υπολογιστή ευκολότερα από ότι με τη χρήση αναλυτικών μεθόδων. Επίσης, οι αλγόριθμοι Μόντε Κάρλο είναι εξαιρετικά αποδοτικοί, αφού προσφέρουν τη δυνατότητα παράλληλου υπολογισμού. Συγκεκριμένα, μπορεί να γίνει καταμερισμός σε μικρότερες εργασίες και κάθε εργασία να διεκπεραιώνεται παράλληλα σε διαφορετικούς υπολογιστές ή επεξεργαστές, μειώνοντας κατά πολύ τον υπολογιστικό χρόνο.
  • Τυχαιότητα: Η έμφυτη τυχαιότητα των Μόντε Κάρλο μεθόδων δεν είναι μόνο απαραίτητη για την προσομοίωση ρεαλιστικών μοντέλων, αλλά αποτελεί και ένα μεγάλο πλεονέκτημα για ντετερμινιστικούς αριθμητικούς υπολογισμούς. Π.χ. η τυχαιότητα επιτρέπει στους στοχαστικούς αλγορίθμους να διαφεύγουν τοπικά ακρότατα και έτσι ευνοείται η ανακάλυψη μεγαλύτερου χώρου στο μοντέλο.
  • Έρευνα: Υπάρχει έντονη δραστηριότητα για μαθηματική και στατιστική υποστήριξη των τεχνικών Μόντε Κάρλο, προκειμένου να αυξηθεί η ακρίβεια των εκτιμητών Μόντε Κάρλο και της αποδοτικότητας των αλγορίθμων. Ταυτόχρονα, ερευνώνται σειρές κανόνων και παραμέτρων ώστε να μειωθεί ο χρόνος υπολογισμού και να αυξηθεί η βελτιστοποίηση.[3]

Οι αλγόριθμοι Μόντε Κάρλο χρησιμοποιούνται ευρέως σε προβλήματα φυσικής, μηχανικής, επιστήμης υπολογιστών, χρηματοοικονομικών, εφαρμοσμένης στατιστικής, κοινωνικών επιστημών, καθώς και στην υπολογιστική βιολογία και στη βιοπληροφορική.[4][5]

Μαρκοβιανή αλυσίδα Μόντε Κάρλο (Markov Chain Monte Carlo , MCMC)[Επεξεργασία | επεξεργασία κώδικα]

Όταν η κατανομή πιθανότητας της μεταβλητής είναι παραμετροποιημένη, πολλές φορές γίνεται χρήση της Mαρκοβιανής Αλυσίδας.

Οι μέθοδοι Μαρκοβιανής αλυσίδας Μόντε Κάρλο (Markov chain Monte Carlo, MCMC) βασίζονται στη δημιουργία μιας λογικής μαρκοβιανής αλυσίδας με μια προκαθορισμένη στάσιμη κατανομή πιθανότητας.

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

Είναι επιθυμητό οι τιμές του δείγματος να προσομοιάζουν τις τιμές από τη ζητούμενη συνάρτηση κατανομής.

Aρχή λειτουργίας μεθόδων MCMC[Επεξεργασία | επεξεργασία κώδικα]

Η αρχή λειτουργίας των MCMC μεθόδων μπορεί να περιγραφεί συνοπτικά ως εξής:

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

Η συνθήκη της εργοδικότητας είναι απαραίτητη έτσι ώστε η Μαρκοβιανή αλυσίδα να μπορεί να περάσει από όλες τις δυνατές καταστάσεις με πεπερασμένο πλήθος βημάτων.

Πιθανά προβλήματα των MCMC μεθόδων[Επεξεργασία | επεξεργασία κώδικα]

  • Συνήθως χρειάζεται πολύ μεγάλο χρονικό διάστημα μέχρι η μαρκοβιανή αλυσίδα να συγκλίνει στη στάσιμη κατανομή της.
  • Τα αποτελέσματα που προκύπτουν από MCMC δειγματοληψίες έχουν συχνά μεγαλύτερη διασπορά σε σχέση με δείγματα που προκύπτουν από δειγματοληψία ανεξάρτητων και ισόνομων δειγμάτων.
  • Επίσης, τα δείγματα που προκύπτουν από μια δειγματοληψία μεθόδου MCMC έχουν μεγάλη συσχέτιση μεταξύ τους.

Αλγόριθμος Metropolis-Hastings[Επεξεργασία | επεξεργασία κώδικα]

Βασική ιδέα του αλγορίθμου Metropolis-Hastings είναι η προσομοίωση μιας αλυσίδας Μαρκόβ με στάσιμη κατανομή (δηλαδή την κατανομή στόχο). Χρησιμοποιείται επίσης μια κατανομή δικής μας πρότασης. Από τον αλγόριθμο Metropolis-Hastings προκύπτει μία αλυσίδα Μαρκόβ καθώς η τελική τιμή εξαρτάται μόνο από την τωρινή κατάσταση και όχι από τις προηγούμενες καταστάσεις.

Ο αλγόριθμος Metropolis-Hastings είναι στην ουσία μια διαδικασία αποδοχής-απόρριψης.

Το πρώτο βήμα είναι να επιλέξουμε ένα αυθαίρετο σημείο εκκίνησης. Στη συνέχεια μετά από κάθε βήμα i η κατάσταση της αλυσίδας προσομοιώνεται ως εξής: κάθε βήμα παρέχει μία υποψήφια κατάσταση και αυτή γίνεται αποδεκτή ή απορριπτέα. Το κριτήριο αποδοχής εξαρτάται από τη συνάρτηση πυκνότητας πιθανότητας. Αν η τωρινή κατάσταση έχει μεγαλύτερη συνάρτηση πυκνότητας πιθανότητας από την προηγούμενη τότε η τωρινή είναι αποδεκτή. Όταν η τωρινή κατάσταση δεν είναι αποδεκτή, απορρίπτεται και τότε η προηγούμενη κατάσταση επαναλαμβάνεται.

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

Μια ειδική περίπτωση του αλγορίθμου Metropolis-Hastings είναι ο λεγόμενος τυχαίος περίπατος (random walk).

Μαρκοβιανή Αλυσίδα Μόντε Κάρλο στη φυλογένεση [6][Επεξεργασία | επεξεργασία κώδικα]

Αναπαράσταση φυλογενετικού δένδρου δίνοντας έμφαση στα βασίλεια Αρχαία, Βακτήρια και Ευκάρυα. Η ρίζα του δένδρου αντιστοιχεί στον κοινό πρόγονο των βασιλείων.

Στην μοριακή φυλογένεση είναι πολύ διαδεδομένο να χρησιμοποιούνται μπεϋζιανές μέθοδοι. Αν και αυτές οι μέθοδοι είναι δυσνόητες, τα λογισμικά που τις χρησιμοποιούν, κατασκευάζουν αποτελεσματικά μπεϋζιανά φυλογεντικά μοντέλα φιλικά προς τον χρήστη. Οι μπεϋζιανές φυλογενετικές μέθοδοι ξεκίνησαν να χρησιμοποιούνται τη δεκαετία του '90 [7]και από τότε άλλαξαν τον τρόπο ανάλυσης της αλληλουχίας του γονιδιώματος. Παραδείγματα τέτοιων αναλύσεων είναι η φυλογεωγραφική ανάλυση της εξάπλωσης του ιού στο ανθρώπινο είδος και τα συμπεράσματα από την μετανάστευση των ειδών. Ταυτόχρονα, τα μοντέλα που κατασκευάζονται, αν και είναι εύκολο να δημιουργηθούν, μπορεί να βγάζουν λάθος συμπεράσματα, να παραπλανούν, σε περίπτωση που ο χρήστης δεν είναι γνώστης των παραμέτρων και των μαθηματικών υποθέσεων.

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

Μέθοδος Bayes[Επεξεργασία | επεξεργασία κώδικα]

H μέθοδος αυτή αποτελεί μία μεθοδολογία για την στατιστική συμπερασματολογία. Βασίζεται στο Θεώρημα Μπέυζ με τύπο :

f(θ|D) = (1/z)f(θ)f(D|θ)

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

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

Προγράμματα που στηρίζονται σε Bayes και MCMC αλγορίθμους[Επεξεργασία | επεξεργασία κώδικα]

ΌΝΟΜΑ ΧΡΗΣΗ ΣΥΝΔΕΣΜΟΣ ΣΤΟ ΔΙΑΔΙΚΤΥΟ
MCMCTree Γίνεται εκτίμηση των χρόνων αποκλίσεων σε ένα σταθερό φυλογενετικό δέντρο. https://web.archive.org/web/20180731124253/http://www.fish-evol.com/mcmctreeExampleVert6/text1Eng.html
Tracer Πρόκειται ένα  πρόγραμμα για διαγνώσεις MCMC και περιλήψεις. http://tree.bio.ed.ac.uk/software/tracer/
AWTY Αφορά ένα πακέτο για διαγνώσεις MCMC για φυλογενετική συμπερασματολογία. https://web.archive.org/web/20180601160859/http://king2.scs.fsu.edu/CEBProjects/awty/awty_start.php
BEAST Εφαρμόζει ένα μεγάλο αριθμό μοντέλων. Παραδείγματα είναι η ταυτόχρονη εκτίμηση της τοπολογίας των δέντρων και των χρόνων απόκλισης, της φυλοδυναμικής, της φυλογεωγραφίας. http://beast.community/
ΜrBayes Εφαρμόζει ένα μεγάλο αριθμό μοντέλων για ανάλυση νουκλεοτιδίων, αμινοξέων και μορφολογικών δεδομένων και γίνεται εκτίμηση της φυλογένεσης των ειδών. http://mrbayes.sourceforge.net/
Phycas Γίνεται εκτίμηση φυλογενετικών δέντρων βασισμένα σε δεδομένα νουκλεοτιδίων. http://www.phycas.org/[νεκρός σύνδεσμος]
PhyloBayes Ανακατασκευάζει φυλογενετικά δέντρα χρησιμοποιώντας μοντέλα απεριόριστων μιγμάτων για να υπολογίσει την ετερογένεια μεταξύ των θέσεων και μεταξύ των γενεών σε συνθέσεις νουκλεοτιδίων ή αμινοξέων, οι οποίες μπορεί να είναι σημαντικές για την εξαγωγή βαθιών φυλογενιών. http://www.atgc-montpellier.fr/phylobayes/
BPP Εφαρμόζει την εκτίμηση των δένδρων ειδών και την οριοθέτηση των ειδών σύμφωνα με το μοντέλο MSC χρησιμοποιώντας δεδομένα γονιδιωματικής ακολουθίας πολλαπλών τόπων. http://abacus.gene.ucl.ac.uk/software.html
Migrate Εκτιμά τα μεγέθη του πληθυσμού και τα ποσοστά μετανάστευσης. https://www.westgrid.ca/support/software/migrate Αρχειοθετήθηκε 2020-09-24 στο Wayback Machine.
IMa2 Εκτιμά τους χρόνους απόκλισης, τα μεγέθη του πληθυσμού και τους ρυθμούς μετανάστευσης σύμφωνα με το μοντέλο isolation-with-migration χρησιμοποιώντας δεδομένα αλληλουχίας DNA πολλαπλών τόπων και σταθερό φυλογενετικό δέντρο για πληθυσμούς. https://bio.cst.temple.edu/~hey/software#ima2-div
Structure Υπολογίζει τη δομή του πληθυσμού από δεδομένα γενοτύπου πολλαπλών τόπων. https://web.stanford.edu/group/pritchardlab/structure.html
BAMM Εκτιμά τα ποσοστά διαφοροποίησης των αρσενικών φυλογενιών. http://bamm-project.org/

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

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

Πόσες επαναλήψεις και πόσα δείγματα απαιτούνται[Επεξεργασία | επεξεργασία κώδικα]

Ο χρόνος που χρειάζεται ο αλγόριθμος MCMC για να αποκτήσει μία αξιόπιστη εκτίμηση για την εκ των υστέρων κατανομή διαρκεί τόσο ώστε να μην επιβαρύνει τον υπολογιστή που τον εκτελεί. Όμως, αφού δεν υπάρχουν αυτόματοι κανόνες παύσης, ο χρήστης πρέπει να έχει σκεφτεί τον αριθμό των επαναλήψεων και, ύστερα, να αποφασίσει αν η μαρκοβιανή αλυσίδα είναι τόσο μεγάλη όσο χρειάζεται ή απαιτούνται κι άλλες επαναλήψεις. Οι MCMC αλγόριθμοι τείνουν να παράγουν τεράστια αρχεία ως output. Για την εξοικονόμηση χώρου στο δίσκο, τα δείγματα λαμβάνονται μετά από ένα καθορισμένο αριθμό επαναλήψεων. Λόγου χάριν, για παράδειγμα, η εκτέλεση μιας αλυσίδας MCMC για 107 επαναλήψεις και η χρήση μιας συχνότητας δειγματοληψίας 103 επαναλήψεων, θα παράγει 104 δείγματα.

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

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

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

Το δείγμα από την εκ των προτέρων μπορεί επίσης να συγκριθεί με το δείγμα από την εκ των υστέρων (η οποία παράγεται με τη χρήση των δεδομένων) για να εκτιμηθεί ο τρόπος πληροφόρησης των δεδομένων και αν υπάρχουν σοβαρές συγκρούσεις μεταξύ της πρώτης και των δεδομένων. Ένας υψηλός βαθμός ομοιότητας μεταξύ της πρώτης και της δεύτερης κατανομής υποδηλώνει ότι τα δεδομένα περιέχουν ελάχιστες πληροφορίες σχετικά με τις παραμέτρους. Σημαντική αλληλοεπικάλυψη μεταξύ αυτών των δύο κατανομών σημαίνει ότι τα δεδομένα είναι πληροφοριακά  και λογικά. Αντιθέτως, αν δεν υπάρχει αλληλοεπικάλυψη, τότε μπορεί να υπάρχει σύγκρουση μεταξύ της πρώτης κατανομής και των δεδομένων.

Εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

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

Εφαρμογές MCMC στην βιολογία συστημάτων[Επεξεργασία | επεξεργασία κώδικα]

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

Ακολουθούν παραδείγματα εφαρμογών της τεχνικής MCMC για επίλυση προβλημάτων βιολογικού ενδιαφέροντος.

Γενετική[Επεξεργασία | επεξεργασία κώδικα]

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

Ανάλυση αλληλουχιών[Επεξεργασία | επεξεργασία κώδικα]

Η τεχνική ΜCMC μπορεί να χρησιμοποιηθεί για την αλληλούχιση γονιδιωμάτων. Σε αντίθεση με τις περισσότερες μεθόδους αλληλούχισης ολόκληρων γονιδιωμάτων, οι οποίες επιλέγουν μόνο μία γονιδιωματική αλληλουχία μεταξύ πολλών εναλλακτικών υποθέσεων, που μπορούν να συναχθούν από τα δεδομένα, η προσέγγιση με χρήση MCMC παράγει κατανομές υποθέσεων συναρμολόγησης του προς αλληλούχιση γονιδιώματος μέσω εκ των υστέρων πιθανοτήτων, παρέχοντας ένα στατιστικό πλαίσιο για την εκτίμηση εναλλακτικών υποθέσεων και της αβεβαιόττας του προτεινόμενου μοντέλου.[18]

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

Πρωτεωμική[Επεξεργασία | επεξεργασία κώδικα]

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

Γενετικά Ρυθμιστικά Δίκτυα[Επεξεργασία | επεξεργασία κώδικα]

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

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. ↑ 1,0 1,1 1,2 1. Κομηνέας Σ., 2. Χαρμανδάρης Ε. (2016). Στοχαστικά Συστήματα – Μέθοδοι Monte Carlo. ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ ΚΑΙ ΕΦΑΡΜΟΣΜΕΝΩΝ ΜΑΘΗΜΑΤΙΚΩΝ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΚΡΗΤΗΣ. σελ. 151. 
  2. ↑ Ταπίρη Ε. (2013). «Στοχαστική προσομοίωση με μεθόδους Markov Chain Monte Carlo (MCMC)» (PDF). [νεκρός σύνδεσμος]
  3. ↑ Kroese, Dirk P.; Brereton, Tim; Taimre, Thomas; Botev, Zdravko I. (2014-06-20). «Why the Monte Carlo method is so important today» (στα αγγλικά). Wiley Interdisciplinary Reviews: Computational Statistics 6 (6): 386–392. doi:10.1002/wics.1314. ISSN 1939-5108. https://onlinelibrary.wiley.com/doi/abs/10.1002/wics.1314. 
  4. ↑ Ρούσσος Ι. (2009). «Μελέτη των Self – avoiding Random Walks» (PDF). 
  5. ↑ Mode, Charles (2011). Applications of Monte Carlo Methods in Biology, Medicine and Other Fields of Science. Ινδία. σελ. 1. ISBN 978-953-307-427-6. 
  6. ↑ Nascimento, Fabrícia· Mario dos Reis· Yang, Ziheng (2017). «A biologist's guide to Bayesian phylogenetic Analysis» (PDF). Nature ecology&evolution. 
  7. ↑ Rannala, Bruce; Yang, Ziheng (1996-09). «Probability distribution of molecular evolutionary trees: A new method of phylogenetic inference» (στα αγγλικά). Journal of Molecular Evolution 43 (3): 304–311. doi:10.1007/bf02338839. ISSN 0022-2844. https://link.springer.com/article/10.1007/BF02338839. 
  8. ↑ Lewis, Paul O. (2001-11-01). «A Likelihood Approach to Estimating Phylogeny from Discrete Morphological Character Data» (στα αγγλικά). Systematic Biology 50 (6): 913–925. doi:10.1080/106351501753462876. ISSN 1076-836X. https://academic.oup.com/sysbio/article/50/6/913/1628902. 
  9. ↑ Redelings, Benjamin D.; Suchard, Marc A. (2005-6). «Joint Bayesian estimation of alignment and phylogeny». Systematic Biology 54 (3): 401–418. doi:10.1080/10635150590947041. ISSN 1063-5157. PMID 16012107. https://www.ncbi.nlm.nih.gov/pubmed/16012107. 
  10. ↑ Löytynoja, Ari; Goldman, Nick (2009-06-19). «Uniting Alignments and Trees» (στα αγγλικά). Science 324 (5934): 1528–1529. doi:10.1126/science.1175949. ISSN 0036-8075. PMID 19541988. http://science.sciencemag.org/content/324/5934/1528. 
  11. ↑ Chatzou, Maria; Magis, Cedrik; Chang, Jia-Ming; Kemena, Carsten; Bussotti, Giovanni; Erb, Ionas; Notredame, Cedric (11 2016). «Multiple sequence alignment modeling: methods and applications». Briefings in Bioinformatics 17 (6): 1009–1023. doi:10.1093/bib/bbv099. ISSN 1477-4054. PMID 26615024. https://www.ncbi.nlm.nih.gov/pubmed/26615024. 
  12. ↑ Villemereuil, Pierre de; Wells, Jessie A.; Edwards, Robert D.; Blomberg, Simon P. (2012-06-28). «Bayesian models for comparative analysis integrating phylogenetic uncertainty». BMC Evolutionary Biology 12 (1): 102. doi:10.1186/1471-2148-12-102. ISSN 1471-2148. PMID 22741602. PMC PMC3582467. https://doi.org/10.1186/1471-2148-12-102. 
  13. ↑ Filipowicz, Natalia; Renner, Susanne S. (2012-7). «Brunfelsia (Solanaceae): a genus evenly divided between South America and radiations on Cuba and other Antillean islands». Molecular Phylogenetics and Evolution 64 (1): 1–11. doi:10.1016/j.ympev.2012.02.026. ISSN 1095-9513. PMID 22425729. https://www.ncbi.nlm.nih.gov/pubmed/22425729. 
  14. ↑ Lemey, Philippe; Rambaut, Andrew; Drummond, Alexei J.; Suchard, Marc A. (2009-09-25). «Bayesian Phylogeography Finds Its Roots» (στα αγγλικά). PLOS Computational Biology 5 (9): e1000520. doi:10.1371/journal.pcbi.1000520. ISSN 1553-7358. PMID 19779555. PMC PMC2740835. http://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1000520. 
  15. ↑ Silvestro, Daniele; Schnitzler, Jan; Liow, Lee Hsiang; Antonelli, Alexandre; Salamin, Nicolas (2014-5). «Bayesian estimation of speciation and extinction from incomplete fossil occurrence data». Systematic Biology 63 (3): 349–367. doi:10.1093/sysbio/syu006. ISSN 1076-836X. PMID 24510972. PMC PMC4361715. https://www.ncbi.nlm.nih.gov/pubmed/24510972. 
  16. ↑ Darren J. Wilkinson. «Bayesian methods in bioinformatics and computational systems biology». Briefings in Bioinformatics, Volume 8, Issue 2, 1 March 2007, Pages 109–116. 
  17. ↑ Mark A. Beaumont, Bruce Rannala (2004). «The Bayesian revolution in genetics». Nature Reviews Genetics volume 5, pages 251–261. 
  18. ↑ Howison, Mark· Zapata, Felipe· Edwards, Erika J.· Dunn, Casey W. (2014). «Bayesian Genome Assembly and Assessment by Markov Chain Monte Carlo Sampling». PLoS ONE 9(6): e99497. 
  19. ↑ «Detecting recombination with MCMC». Bioinformatics. 2002;18 Suppl 1:S345-53. 
  20. ↑ «Bayesian ABC-MCMC Classification of Liquid Chromatography–Mass Spectrometry Data». Cancer Inform. 2015; 14(Suppl 5): 175–182. 
  21. ↑ Nilzair B. Agostinho, Karina S. Machado and Adriano V. Werhli. «Inference of regulatory networks with a convergence improved MCMC sampler». BMC Bioinformatics 2015 16:306. 
Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Μαρκοβιανή_Αλυσίδα_Μόντε_Κάρλο_στη_Βιολογία&oldid=10383711"