.
Στοίχιση ακολουθιών
Η στοίχιση ακολουθιών (sequence alignment), είναι μια διαδικασία κατά την οποία δύο ακολουθίες ή αλλιώς συμβολοσειρές τοποθετούνται η μία κάτω από την άλλη, με τέτοιον τρόπο που τα κοινά τους σύμβολα να είναι τοποθετημένοι στην ίδια θέση. Σκοπός είναι να βρεθεί η "βέλτιστη στοίχιση", δηλαδή η στοίχιση στην οποία οι δύο ακολουθίες ταιριάζουν περισσότερο μεταξύ τους. Η διαδικασία αυτή χρησιμοποιείται ιδιαίτερα στη βιοπληροφορική (bioinformatics), όπου ως ακολουθίες χρησιμοποιούνται τμήματα DNA, RNA ή πρωτεΐνών.
Η διαδικασία της στοίχισης, όταν συμβαίνει σε συμβολοσειρές μεγάλου μήκους (όπως αυτές που προκύπτουν από τα βιολογικά δεδομένα) είναι μια σχετικά δύσκολη διαδικασία. Στην πράξη χρησιμοποιείται πληθώρα αλγορίθμων, οι περισσότεροι από τους οποίους χρησιμοποιούν την φιλοσοφία του δυναμικού προγραμματισμού (dynamic programming).
Σκοπός στοίχισης ακολουθιών
Η στοίχιση ακολουθιών χρησιμοποιείται στο πεδίο της βιοπληροφορικής για την εύρεση ομοιοτήτων μεταξύ βιολογικών ακολουθιών (DNA, RNA, πρωτεΐνες...), μια εργασία πολύ συχνή και με ιδιαίτερη σημασία. Η σημασία της πηγάζει από το γεγονός ότι οι ομοιότητες αυτές υποδηλώνουν συνήθως κάποια βιολογική συσχέτιση, πράγμα που οδηγεί σε καλύτερη κατανόηση των διαφόρων βιολογικών μηχανισμών.
Κανόνες στοίχισης ακολουθιών
Ο βασικός κανόνας της στοίχισης ακολουθιών είναι η τοποθέτηση των δύο (υπό εξέταση) ακολουθιών με τέτοιον τρόπο την μία κάτω από την άλλη, ώστε να ταιριάζουν όσο το δυνατόν περισσότερο. Από αυτό φαίνεται ότι μπορεί κάποια από τα σύμβολα των ακολουθιών να μην ταιριάζουν μετά τη στοίχιση. Το τι γίνεται τότε έχει να κάνει με τον τρόπο με τον οποίο μετράται το "ταίριασμα". Συνήθως γίνεται προσπάθεια να στοιχιστούν οι ακολουθίες με τέτοιον τρόπο, ώστε να μεγιστοποιηθεί κάποιο σκορ. Κάθε ζεύγος συμβόλων που ταιριάζουν μεταξύ τους παίρνει κάποιο θετικό σκορ (π.χ. +1), ενώ κάθε ζεύγος που αποτυγχάνει να ταιριάξει παίρνει κάποιο αρνητικό σκορ (π.χ. -1). Αν επιτρέπεται να εισαχθούν κενοί χαρακτήρες για αποφυγή αποτυχίας σε ένα σημείο, τότε κάθε κενό "κοστολογείται" και αυτό με αρνητικό σκορ (π.χ. -1). Δύο κενά δεν γίνεται να ταιριάζουν μεταξύ τους. Αθροίζοντας όλα τα επιμέρους σκορ υπολογίζεται το συνολικό σκορ της στοίχισης.
Είδη στοίχισης ακολουθιών
Υπάρχουν δύο είδη στοίχισης, η ολική στοίχιση (global alignment) και η τοπική στοίχιση (local alignment), οι οποίες χρησιμοποιούνται ανάλογα με τον τύπο του προβλήματος που αντιμετωπίζεται.
Ολική στοίχιση ακολουθιών
Κατά την ολική στοίχιση ακολουθιών (global sequence alignment) γίνεται προσπάθεια να στοιχιστεί κάθε σύμβολο κάθε ακολουθίας. Οι δύο ακολουθίες στοιχίζονται σε ολόκληρο το μήκος τους με τον καλύτερο δυνατό τρόπο. Κάθε σύμβολο κάθε ακολουθίας, λοιπόν, αντιστοιχίζεται σε ένα σύμβολο της άλλης ή σε ένα κενό. Ένας γνωστός αλγόριθμος για ολική στοίχιση ακολουθιών είναι ο αλγόριθμος Needleman-Wunsch.
Τοπική στοίχιση ακολουθιών
Κατά την τοπική στοίχιση ακολουθιών (local sequence alignment) γίνεται η καλύτερη δυνατή στοίχιση μεταξύ τμημάτων των δύο ακολουθιών. Δηλαδή επιτρέπεται κάποια κομμάτια που "χαλούν" τη στοίχιση να μείνουν εκτός. Ένα παράδειγμα που χρησιμοποιείται συχνά είναι ότι μπορούμε να χρησιμοποιήσουμε την τοπική στοίχιση ακολουθιών προκειμένου να βρούμε τις προτάσεις δύο κειμένων, οι οποίες παρουσιάζουν την περισσότερη ομοιότητα. Ένας γνωστός αλγόριθμος για τοπική στοίχιση ακολουθιών είναι ο αλγόριθμος Smith-Waterman.
Retrieved from "http://el.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
