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

Abstract

Τα μόρια του RNA διαδραματίζουν σημαντικό ρόλο σε όλα τα κύτταρα των ζωντανών οργανισμών. Επιπλέον, το μεγαλύτερο μέρος του ανθρώπινου γονιδιώματος μετατρέπεται σε μη κωδικοποιητικό RNA του οποίου η λειτουργία είναι άγνωστη. Ωστόσο, για να αποκρυπτογραφήσουμε τη λειτουργία του RNA, είναι σημαντικό να διερευνήσουμε τη δομή του. Επιπροσθέτως, η παρουσία του ιού SARS-CoV-2, ο οποίος έπληξε μεγάλο μέρος του παγκόσμιου πληθυσμού, κατέστησε ακόμα πιο σημαντική τη γνώση της δομής του RNA. Ένα από τα βήματα στην αποσαφήνιση της δομής του RNA αποτελεί ο ακριβής υπολογισμός της δευτεροταγούς δομής του. Ιστορικά, διάφορες προσεγγίσεις πρόβλεψης της δευτεροταγούς δομής του έχουν αποκλείσει τη δομή του ψευδοκόμβου καθώς θεωρείται ότι το συνολικό πρόβλημα γίνεται ακόμα πιο σύνθετο και πιο χρονοβόρο ως προς τη λύση του. Ωστόσο, η παράλειψη αυτής της δομής από διάφορες προσεγγίσεις για το συγκεκριμένο πρόβλημα περιορίζει τη χρησιμότητα τους ως προς την αποδοτική επίλυση του.

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