Αλγόριθμοι δυναμικού προγραμματισμού και εφαρμογές στην [sic] βιοπληροφορική
Loading...
Date
2026-07-08
Authors
Τσιρίκος, Αναστάσιος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Η παρούσα διπλωματική εργασία πραγματεύεται το πρόβλημα της ευθυγράμμισης ακολουθιών στη βιοπληροφορική, ένα από τα σημαντικότερα προβλήματα της υπολογιστικής ανάλυσης βιολογικών δεδομένων. Η ραγδαία ανάπτυξη των τεχνολογιών αλληλούχισης DNA και RNA έχει οδηγήσει στη δημιουργία τεράστιου όγκου γενετικών δεδομένων, γεγονός που καθιστά απαραίτητη την ανάπτυξη αποδοτικών και αξιόπιστων αλγορίθμων για τη σύγκριση και ανάλυση βιολογικών ακολουθιών. Μέσω της ευθυγράμμισης ακολουθιών καθίσταται δυνατός ο εντοπισμός περιοχών ομοιότητας, η ανίχνευση μεταλλάξεων, καθώς και η μελέτη λειτουργικών και εξελικτικών σχέσεων μεταξύ οργανισμών.
Στο πλαίσιο της εργασίας παρουσιάζονται αρχικά οι βασικές έννοιες της μοριακής βιολογίας και της βιοπληροφορικής, καθώς και οι κύριες κατηγορίες ευθυγράμμισης ακολουθιών. Στη συνέχεια αναλύονται οι σημαντικότεροι κλασικοί αλγόριθμοι ευθυγράμμισης, όπως οι Needleman–Wunsch και Smith–Waterman, οι οποίοι βασίζονται στη μέθοδο του δυναμικού προγραμματισμού και εξασφαλίζουν βέλτιστα αποτελέσματα με αυξημένο όμως υπολογιστικό κόστος.
Κεντρικό αντικείμενο της εργασίας αποτελεί η ανάπτυξη και υλοποίηση ενός νέου ευρετικού αλγορίθμου ευθυγράμμισης ακολουθιών με την ονομασία DIAL (Diagonal Algorithm). Ο προτεινόμενος αλγόριθμος βασίζεται σε τεχνικές τύπου dot-plot και στην ανάλυση διαγωνίων για την ταχεία ανίχνευση περιοχών υψηλής ομοιότητας μεταξύ βιολογικών ακολουθιών, χωρίς την ανάγκη πλήρους υπολογισμού δυναμικού προγραμματισμού. Η σχεδίαση του αλγορίθμου στοχεύει στην επίτευξη ενός ισορροπημένου συμβιβασμού μεταξύ ταχύτητας εκτέλεσης και ποιότητας ευθυγράμμισης, ώστε να μπορεί να αξιοποιηθεί σε εφαρμογές μεγάλης κλίμακας.
Η υλοποίηση πραγματοποιήθηκε στη γλώσσα προγραμματισμού Python και αξιολογήθηκε μέσω πειραμάτων σε τεχνητά και πραγματικά βιολογικά δεδομένα. Η συγκριτική αξιολόγηση πραγματοποιήθηκε έναντι του αλγορίθμου Smith–Waterman, χρησιμοποιώντας κοινά κριτήρια, όπως ο χρόνος εκτέλεσης, το ποσοστό ταύτισης και το μήκος της ευθυγράμμισης.
Τα πειραματικά αποτελέσματα έδειξαν ότι ο προτεινόμενος αλγόριθμος παρουσιάζει σημαντικά μειωμένο χρόνο εκτέλεσης σε σχέση με τον Smith–Waterman, διατηρώντας παράλληλα ικανοποιητικά επίπεδα ακρίβειας σε περιπτώσεις υψηλής και μέσης ομοιότητας. Ωστόσο, σε πιο απαιτητικά σενάρια ο Smith–Waterman εξακολουθεί να υπερέχει ως προς την ποιότητα της ευθυγράμμισης. Συνολικά, η εργασία αναδεικνύει τον συμβιβασμό μεταξύ ταχύτητας και ακρίβειας στους αλγορίθμους ευθυγράμμισης ακολουθιών και προτείνει μία αποδοτική εναλλακτική προσέγγιση για εφαρμογές σύγχρονης βιοπληροφορικής.
Description
Keywords
Βιοπληροφορική, Αλγόριθμοι, Δυναμικός προγραμματισμός