Εντοπισμός Κ-Type RNA Pseudoknot με τεχνικές συντακτικής αναγνώρισης προτύπων

Abstract

Η διερεύνηση της δευτεροταγούς δομής του RNA και συγκεκριμένα η πρόβλεψη της θέσης των pseudoknots τύπου K σε μια δοσμένη ακολουθία RNA είναι το ζήτημα με το οποίο ασχολείται η παρούσα διπλωματική εργασία. Στην εργασία θα παρουσιαστεί σε βάθος η διαδικασία και η ανάλυση των βημάτων με τα οποία φτάνουμε στο επιθυμητό αποτέλεσμα. Χρησιμοποιούνται κριτήρια όπως η ελάχιστη ελεύθερη ενέργεια αναδίπλωσης του RNA και η μεγιστοποίηση του αριθμού των ζευγών μεταξύ των βάσεων. Στη συνέχεια μέσω της ανάλυσης μας ξεχωρίζεται η βέλτιστη λύση καθώς σε κάθε δοσμένη ακολουθία παρατηρούνται πάνω από μία προτεινόμενες λύσεις. Τα παραπάνω γίνονται με δύο εργαλεία: με την χρήση μιας γραμματικής χωρίς συμφραζόμενα για την συντακτική αναγνώριση του pseudoknot και με έναν άπληστο αλγόριθμο δυναμικού προγραμματισμού για την εύρεση της τελικής λύσης.