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