| Περίληψη: | Αντικείμενο της παρούσας διδακτορικής διατριβής είναι η μελέτη και η σχεδίαση αποδοτικών αλγορίθμων για τη διαχείριση και ανάλυση ακολουθιών βιολογικών δεδομένων. Οι αλγόριθμοι που θα περιγράψουμε εφαρμόζονται σε προβλήματα Βιοπληροφορικής, όπως η αναγνώριση γνωστών ή άγνωστων μοτίβων του DNA και RNA, που εμπλέκονται σε ποικίλες βιολογικές διεργασίες καθώς και η ανακάλυψη περιοδικοτήτων.
Ειδικότερα οι αλγόριθμοι που θα παρουσιάσουμε χρησιμοποιούνται για την ανάλυση Βιολογικών Ακολουθιών με “αδιάφορους χαρακτήρες” και Βιολογικών Ακολουθιών με Βάρη. Οι Βιολογικές Ακολουθίες με “αδιάφορους χαρακτήρες” αναπαριστούν συνήθως οικογένειες πρωτεϊνών ενώ οι Βιολογικές Ακολουθίες με βάρη αναπαριστούν συναρμολογούμένες ακολουθίες γονιδιωμάτων που έχουν πρόσφατα αλληλουχηθεί.
Στις Βιολογικές Ακολουθίες με αδιάφορους χαρακτήρες παρουσιάζουμε δυο αποδοτικούς αλγορίθμους γραμμικού χρόνου για τον υπολογισμό της περιόδου και τον υπολογισμό του καλύμματος. Ο δεύτερος αλγόριθμος εφαρμόζεται και σε κυκλικά (circular DNAs).
Στις Βιολογικές Ακολουθίες με βάρη παρουσιάζουμε δυο αλγορίθμους για τον υπολογισμό των βασικών περιοδικοτήτων: της περιόδου και του καλύμματος ενώ επιλύουμε και το πρόβλημα της εύρεσης προτύπου. Η ανάγκη για αποδοτική διαχείριση βιολογικών ακολουθιών με βάρη μας ώθησε να εισάγουμε μια νέα αποδοτική δομή η οποία επιλύει αποδοτικά τα 2 προηγούμενα προβλήματα. Η δομή αυτή ονομάζεται Δέντρο Επιθεμάτων με Βάρη. Χρησιμοποιώντας το Δέντρο Επιθεμάτων με Βάρη επιλύουμε διάφορες παραλλαγές του προβλήματος εξαγωγής μοτίβων από Βιολογικές Ακολουθίες με Βάρη.
Τέλος αποφασίσαμε να μελετήσουμε τη χρήση των Γενετικών Αλγορίθμων και του Εξελικτικού Προγραμματισμού στην ανάλυση ακολουθιών βιολογικών δεδομένων. Αποτέλεσμα αυτής της μελέτης είναι η περιγραφή ενός γενετικού αλγορίθμου που υπολογίζει τις επαναλήψεις σε μια βιολογική ακολουθία.
|
|---|
