Αλγόριθμος Needleman-Wunsch

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση



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

Περιγραφή του αλγορίθμου Needleman-Wunsch[Επεξεργασία | επεξεργασία κώδικα]

Στον πυρήνα του αλγορίθμου Needleman-Wunsch για ολική στοίχιση ακολουθιών υπάρχει ένας πίνακας του οποίου οι γραμμές αντιστοιχούν στα σύμβολα της μίας ακολουθίας και οι στήλες στα σύμβολα της άλλης. Κάθε κελλί αυτού του πίνακα αντιστοιχεί σε ένα ταίριασμα γραμμάτων των δύο ακολουθιών, και περιέχει δύο τιμές: Ένα σκορ (που υπολογίζεται με βάση ένα συγκεκριμένο σχήμα) και έναν δείκτη (του οποίου η χρήση γίνεται πιο σαφής παρακάτω). Κατά την εκτέλεση ακολουθείται μια αλληλουχία τριων φάσεων: 1. Αρχικοποίηση πίνακα, 2. Γέμισμα πίνακα και 3. Οπισθοχώρηση (traceback). Στις επόμενες ενότητες αναλύονται καθεμία από αυτές τις φάσεις.

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

Σε αυτή τη φάση προσδίδονται τιμές στην πρώτη γραμμή και στην πρώτη στήλη του πίνακα. Αυτό υπονοεί ότι για κάθε κελλί της πρώτης γραμμής και της πρώτης στήλης του πίνακα γίνονται δύο αναθέσεις: Ανατίθεται ένα σκορ και ένας δείκτης.

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

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

Οπισθοχώριση[Επεξεργασία | επεξεργασία κώδικα]

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