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

Η ομοιότητα έχει και ποιοτικά και ποσοτικά χαρακτηριστικά. Μία μέτρηση της ομοιότητας (σε μονάδες που εμείς επιλέγουμε) μας δίνει μία ποσοτική πληροφορία, δηλαδή το βαθμό ομοιότητας μεταξύ δύο ακολουθιών. Μια ευθυγράμμιση από την άλλη μεριά (δηλαδή η στοίχιση των γραμμάτων δύο γραμμών όπου τα κοινά γράμματα βρίσκονται στις ίδιες στήλες), είναι μια διευθέτηση (παρουσίαση) των δύο ακολουθιών, που αντιπροσωπεύει μια ποιοτική πληροφορία. Στην ευθυγράμμιση θα δούμε τα σημεία στα οποία οι δύο ακολουθίες ταυτίζονται και τα σημεία στα οποία διαφέρουν. Η ιδανική ευθυγράμμιση φυσικά, είναι αυτή που έχει τις περισσότερες ομοιότητες και τις λιγότερες διαφορές.

Εισαγωγικές Έννοιες

Τα βασικότερα μεγέθη που χρειαζόμαστε για τη μελέτη της ομοιότητας μεταξύ αμινοξικών ακολουθιών και κατ' επέκταση για την επίτευξη της ιδανικότερης ευθυγράμμισης είναι το αλφάβητο, οι ακολουθίες, οι υποακολουθίες, η απόσταση, οι λειτουργίες διαχείρισης και οι μονάδες μέτρησης.

α) Αλφάβητο

Το αλφάβητο ορίζεται σαν ένα σύνολο χαρακτήρων από το οποίο δημιουργούνται οι ακολουθίες. Στη συγκεκριμένη περίπτωση το αλφάβητο μας αποτελείται από τα είκοσι γράμματα που αντιπροσωπεύουν τα είκοσι αμινοξικά κατάλοιπα που συνθέτουν όλες τις πρωτε? νες. Άλλη περίπτωση αλφάβητου είναι αυτό που απαρτίζεται από τα τέσσερα γράμματα που αντιστοιχούν στις τέσσερις βάσεις του DNA, Στην παρουσίαση που θα ακολουθήσει θα κάνουμε χρήση των ακόλουθων συμβολισμών :

• Α δηλώνουμε το αλφάβητο,
• Α^* είναι το σύνολο όλων των πεπερασμένων ακολουθιών χαρακτήρων που παράγονται από το Α,
• a, b, c είναι μεταβλητές που αντιπροσωπεύουν μεμονωμένους χαρακτήρες του αλφάβητου,
• s, t, u, v είναι μεταβλητές που αντιπροσωπεύουν ακολουθίες από το Α^*,
• |s| δηλώνει το μήκος της ακολουθίας s σε χαρακτήρες.

Η ακολουθία φυσικά ορίζεται σαν ένας πεπερασμένος συνδυασμός των στοιχείων (γραμμάτων) του αλφάβητου. Σαν υποακολουθία ορίζουμε ένα οποιοδήποτε γραμμικό τμήμα μίας ακολουθίας, δηλαδή ένα υποσύνολο του συνόλου των στοιχείων που απαρτίζουν την ακολουθία. Για παράδειγμα ας θεωρήσουμε την ακολουθία s = KLMN

που τα γράμματα αντιστοιχούν στις θέσεις K₀L₁M₂N₃. Μια υποακολουθία δηλώνεται σαν _i:s:_j που σημαίνει ότι αντιστοιχεί στο τμήμα μεταξύ των θέσεων i και j .

γ) Απόσταση

Οι ποσοτικές μετρήσεις της ομοιότητας δύο ακολουθιών στηρίζονται κυρίως σε δύο βασικά μεγέθη. Το πρώτο είναι η απόσταση και έχει να κάνει με την απόσταση των ακολουθιών σε ένα ιδεατό χώρο όπου αυτές αντιστοιχούν σε σημεία του. Η μέτρηση της απόστασης είναι η διαδικασία με την οποία αντιστοιχούμε μια αριθμητική τιμή σε κάθε ζευγάρι ακολουθιών. Όσο μεγαλύτερο είναι το νούμερο (και κατά συνέπεια η απόσταση) τόσο μικρότερη είναι η ομοιότητα μεταξύ δύο ακολουθιών. Οι μετρήσεις αποστάσεων ικανοποιούν τα μαθηματικά αξιώματα του μαθηματικού χώρου που ανήκουν.

Στις περισσότερες περιπτώσεις οι μετρήσεις απόστασης και ομοιότητας είναι αλληλένδετες με την έννοια ότι μια μικρή απόσταση αντιπροσωπεύει μεγάλη ομοιότητα και αντίστροφα. Το πιο απλό ίσως είδος απόστασης είναι η λεγόμενη Hamming Distance που θα αποκαλούμε 1-1 (ένα προς ένα) απόσταση. Για δύο ακολουθίες ίσου μήκους, μετράμε απλώς το πλήθος των χαρακτήρων στους οποίους διαφέρουν όταν αντιστοιχήσουμε του χαρακτήρες έναν προς έναν με τη σειρά που καταλαμβάνουν στις ακολουθίες. Για παράδειγμα :
 

ακολουθία

s

:

K

K

L

K

P

N

K

K

K

P

N

K

N

K

N

K

ακολουθία

t

:

L

K

K

K

N

K

L

K

K

N

K

N

K

N

L

K

1-1 απόσταση

(

s,

t)

:

2

3

6

Αυτό το είδος μέτρησης της απόστασης είναι πολύ χρήσιμο σε μερικές περιπτώσεις, αλλά στις περισσότερες και ειδικά στην ευθυγράμμιση αμινοξικών ακολουθιών δεν είναι αρκετά ευέλικτο. Οι λόγοι είναι κυρίως ότι οι πρωτεϊνικές ακολουθίες έχουν συνήθως διαφορετικά μήκη και ότι δεν υπάρχει γενικά μια μονοσήμαντη αντιστοιχία μεταξύ των θέσεων των χαρακτήρων (καταλοίπων). Ειδικά στην περίπτωση της αντιγραφής του DNA όπου είναι σύνηθες να έχουμε διαγραφές ή εισαγωγές νουκλεοτιδίων και παρότι η υπόλοιπη ακολουθία δεν έχει μεταβληθεί, θα παρατηρήσουμε ότι παίρνουμε υπερβολικές τιμές της 1-1 απόστασης. Αν κοιτάξουμε το τρίτο παράδειγμα παραπάνω, βλέπουμε ότι η 1-1 απόσταση είναι 6 που σημαίνει ότι οι ακολουθίες απέχουν (διαφέρουν) 6 χαρακτήρες. Από την άλλη μεριά όμως αν αφαιρέσουμε το P από την πρώτη και το L από τη δεύτερη βλέπουμε μια πλήρη ταύτιση μεταξύ τους. Με αυτή την έννοια λοιπόν απέχουν μόλις 2 χαρακτήρες.

δ) Λειτουργίες Διαχείρισης

Στην κατηγορία αυτή εντάσσουμε όλες εκείνες τις μετατροπές και τις αντιστοιχίες που μας βοηθάνε στην ευθυγράμμιση δύο ακολουθιών. Προσπαθούμε δηλαδή να μειώσουμε την απόσταση των ακολουθιών s και t υιοθετώντας τις ένα προς ένα μετατροπές χαρακτήρων που θα μετατρέψουν την s στην t. Για το σκοπό αυτό θα υιοθετήσουμε τον κενό χαρακτήρα "-"και θα λέμε ότι :

• (a,a) δηλώνει μία ταύτιση (δε χρειάζεται μετατροπή για να πάμε από την s στην t)
• (a,-) δηλώνει διαγραφή του χαρακτήρα a στην ακολουθία s
• (a,b) δηλώνει αντικατάσταση του a της s από το b της t
• (-,b) δηλώνει εισαγωγή του χαρακτήρα b στην s.

Η ευθυγράμμιση (στοίχιση) δύο ακολουθιών s και t είναι μια "οριζόντια" διευθέτηση των s και t με την μία ακριβώς κάτω από την άλλη, όπου αυτές έχουν συμπληρωθεί με κοινούς χαρακτήρες έτσι ώστε να αποκτήσουν το ίδιο μήκος. Στο τρίτο παράδειγμα που δώσαμε προηγουμένως θα έχουμε :

ακολουθία

s

:

K

P

N

K

N

K

N

-

K

K

P

-

N

K

N

K

N

K

ακολουθία

t

:

K

-

N

K

N

K

N

L

K

ή

K

N

K

N

K

N

L

-

K

Αν διαβάσουμε τις ακολουθίες ανά στήλη έχουμε τις ακόλουθες λειτουργίες διαχείρισης που θα μετατρέψουν την s στην t.

Αριστερή ευθυγράμμιση Δεξιά ευθυγράμμιση

Η αριστερή έχει μία διαγραφή, μία εισαγωγή και όλες οι άλλες λειτουργίες είναι ταύτιση ενώ η δεξιά έχει μία εισαγωγή, μία διαγραφή, δύο αντικαταστάσεις και τις υπόλοιπες ταυτίσεις.

ε) Μονάδες Μέτρησης

Απαραίτητο μέγεθος μιας ποσοτικής μέτρησης είναι ο καθορισμός μιας μονάδας μέτρησης. Στην περίπτωση των ευθυγραμμίσεων θα μετρήσουμε την απόσταση με βάση το "κόστος" ή τη "βαρύτητα" της κάθε λειτουργίας διαχείρισης. Για παράδειγμα, μπορούμε να ορίσουμε το κόστος για δύο αυθαίρετους χαρακτήρες a, b του Α ως εξής :

w(a,a) = 0, w(a,b) = 1 και w(a,-) = w(-,b) = 1.

Αυτή η συνάρτηση κόστους είναι γνωστή σαν απόσταση Levenshtein ή μοντέλο μοναδιαίου κόστους. Το φανερό πλεονέκτημά του είναι η απλότητά του. Σε γενικές γραμμές όμως δεν μπορεί να ανταποκριθεί στις δικές μας ανάγκες, για τις ευθυγραμμίσεις αμινοξικών ακολουθιών. Η αντικατάσταση για παράδειγμα ενός αμινοξέως από ένα άλλο που είναι βιοχημικά συγγενές θα πρέπει να έχει λιγότερο κόστος από την αντικατάσταση του με ένα που είναι τελείως διαφορετικό.

Θα ορίσουμε τώρα τις πιο βασικές έννοιες που σχετίζονται με την ανάλυση ακολουθιών και στηρίζονται στη μονάδα μέτρησης που χρησιμοποιούμε :

• Το κόστος μιας ευθυγράμμισης δύο ακολουθιών s και t είναι το άθροισμα του κόστους των επιμέρους λειτουργιών διαχείρισης που μετατρέπουν την s στην t.
• Η ιδανική ευθυγράμμιση των s και t είναι αυτή που έχει το μικρότερο κόστος από όλες τις δυνατές ευθυγραμμίσεις.
• Η απόσταση μεταξύ s και t είναι το κόστος της ιδανικής ευθυγράμμισης σύμφωνα με τη συνάρτηση κόστους που επιλέξαμε. Θα τη συμβολίζουμε με d_w(s,t).

Βλέπουμε πολύ εύκολα ότι η αριστερή ευθυγράμμιση έχει το χαμηλότερο κόστος και κατά συνέπεια είναι ιδανικότερη με βάση τη συνάρτηση κόστους που υιοθετήσαμε. Η απόσταση αυτής της ευθυγράμμισης θα είναι d_w(s,t) = 2.
 
 

Ειδικά Χαρακτηριστικά Αμινοξικών Ακολουθιών
 
 

Μέχρι στιγμής, έχουμε αντιμετωπίσει το σύμβολο "-" σαν έναν επιπλέον χαρακτήρα, που δηλώνει μία εισαγωγή ή μία διαγραφή. Στην περίπτωση όμως των αμινοξικών ακολουθιών αυτό δεν είναι πάντοτε αρκετό. Ειδικότερα στην περίπτωση της ευθυγράμμισης ομόλογων πρωτεϊνών, ενδιαφερόμαστε για τη συμπαγή (χωρίς κενά) ευθυγράμμιση των τμημάτων εκείνων που διατηρούνται εξελικτικά και καθορίζουν την αλληλεπίδραση πρωτεϊνών. Οποιαδήποτε διαγραφή ή εισαγωγή σ' αυτά τα τμήματα θα αλλοιώσει πιθανότατα τη βιοχημική τους δράση. Τέτοια τμήματα θέλουμε να ευθυγραμμίζονται μόνο με ταυτίσεις και αντικαταστάσεις, που δε συνεπάγονται μεταβολές στο μήκος τους. Αυτό μπορούμε να το πετύχουμε με την κατασκευή ενός απλού αλγόριθμου ή με την τροποποίηση του αλγόριθμου του δυναμικού προγραμματισμού έτσι ώστε οι διαγραφές και οι εισαγωγές σ' αυτά τα τμήματα να έχουν άπειρο κόστος ή πάρα πολύ μεγάλο. Έτσι ο αλγόριθμος θα αποφύγει αυτές τις λειτουργίες διαχείρισης.

Μερικές φορές, για καθαρά εξελικτικούς λόγους είναι πιο ρεαλιστικό να υποθέσουμε ότι η φύση εισάγει ή διαγράφει ολόκληρες υποακολουθίες (Altschul, 1989) που αντιστοιχούν σε δομικά τμήματα (συνήθως δευτεροταγείς δομές). Σ' αυτές τις περιπτώσεις η εισαγωγή ενός μόνο χαρακτήρα "-" κοστίζει πολύ περισσότερο από την εισαγωγή πολλών διαδοχικών για το λόγο ότι οι πολλοί διαδοχικοί θα αντιπροσωπεύουν τα ολόκληρα τμήματα που έχουν επηρεαστεί εξελικτικά. Και αυτή η απαίτηση μπορεί να ικανοποιηθεί με απλή μετατροπή του αλγόριθμου του δυναμικού προγραμματισμού.

Πίνακες Κόστους

Η ευθυγράμμιση αμινοξικών ακολουθιών επηρεάζει αισθητά το τρόπο σύγκρισης και αξιολόγησης που μέχρι τώρα έχουμε παρουσιάσει, ακόμα και για τις περιπτώσεις που δεν ισχύουν οι περιορισμοί που αναφέραμε παραπάνω. Αυτό οφείλεται στις σχέσεις ομοιότητας που έχουν μεταξύ τους τα είκοσι αμινοξικά κατάλοιπα που συνθέτουν τις πρωτε? νες. Ένα βασικό στοιχείο για μια πετυχημένη ευθυγράμμιση είναι η ύπαρξη μιας αξιόλογης συνάρτησης κόστους που θα συσχετίζει τα χαρακτηριστικά και τις ιδιότητες των διαφόρων καταλοίπων. Οι συναρτήσεις που υπάρχουν αυτή τη στιγμή, διατυπώνονται πάντα με τη μορφή πίνακα με στοιχεία τις τιμές κόστους του κάθε ζεύγους αμινοξέων.

Η σπουδαιότητα αυτών των πινάκων είναι καθοριστική για τους εξής λόγους :

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

• Τα στοιχεία των πινάκων καθορίζουν τη βαρύτητα ή το κόστος που αναθέτουμε σε κάθε σύγκριση. Για την περίπτωση των αμινοξικών ακολουθιών το κόστος της αντικατάστασης ενός καταλοίπου με κάποιο άλλο δηλώνει την απόσταση μεταξύ τους ενώ με την έννοια της ομοιότητας μας δίνει την τάση για αντικατάσταση του ενός με το άλλο.
• Η απόσταση είναι πιο αντιπροσωπευτική στην αξιολόγηση για την κατασκευή φυλογενετικών δένδρων ενώ η ομοιότητα χρησιμοποιείται για αναζήτηση σε βάσεις δεδομένων.
• Η λογική των αλγόριθμων δεν αλλάζει : η μεγιστοποίηση της ομοιότητας ισοδυναμεί ουσιαστικά με την ελαχιστοποίηση της απόστασης.
• Οι πίνακες ομοιότητας και απόστασης συσχετίζονται (μετατρέπονται) άμεσα μεταξύ τους με τη χρήση της κατάλληλης συνάρτησης για την κάθε περίπτωση που εφαρμόζονται.

Παραλλαγές της Ευθυγράμμισης Ανά Ζεύγη.

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

Με τον όρο τοπική ευθυγράμμιση εννοούμε τις περιπτώσεις που η ακολουθία s είναι πολύ μικρότερη της ακολουθίας t και ψάχνουμε την υποακολουθία της t που ευθυγραμμίζεται καλύτερα με την s. Για να το πετύχουμε αυτό τροποποιούμε τον αλγόριθμο του δυναμικού προγραμματισμού έτσι ώστε να μη χρεώνονται με κόστος οι διαγραφές τμημάτων της t. Εναλλακτικά μπορούμε να δούμε την τελευταία γραμμή του πίνακα κόστους που δημιουργούμε στη γενική περίπτωση, όπου οι ελάχιστες τιμές αντιστοιχούν σε μερική ταύτιση.

Η τοπική ομοιότητα από την άλλη μεριά αναφέρεται σε λειτουργική ομοιότητα (φυσικών και χημικών χαρακτηριστικών) τμημάτων των πρωτεϊνών με ιδιαίτερα τριτοταγή χαρακτηριστικά, όπως το ενεργό κέντρο των πρωτεϊνών. Με εξαίρεση αυτά τα τμήματα οι υπόλοιπες περιοχές των πρωτεϊνών μπορεί να διαφέρουν ριζικά. Έτσι μια ευθυγράμμιση δύο τέτοιων πρωτεϊνών είναι απίθανο να εμφανίσει καθαρές περιοχές υψηλής ομοιότητας, διότι ο αλγόριθμος τείνει να ελαχιστοποιήσει τις αποστάσεις στο σύνολο των ακολουθιών, διαχέοντας έτσι την ομοιότητα των υποπεριοχών. Σ' αυτές τις περιπτώσεις προσαρμόζουμε τον αλγόριθμο έτσι ώστε να μεγιστοποιείται η ομοιότητα αντί να ελαχιστοποιείται η απόσταση.

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

Ταυτόχρονη Ευθυγράμμιση Πολλών Ακολουθιών

Με τον όρο "πολλαπλή ευθυγράμμιση" ενός πλήθους k ακολουθιών (όπου k ³3), εννοούμε μια ορθογώνια διάταξη (πίνακα) χαρακτήρων, που σχηματίζεται από τους χαρακτήρες των ακολουθιών έτσι ώστε :

• Να περιέχει ακριβώς k γραμμές.
• Αγνοώντας τον κενό χαρακτήρα "-", η γραμμή i να ταυτίζεται με την ακολουθία s_i .
• Κάθε στήλη να περιέχει τουλάχιστον ένα χαρακτήρα διαφορετικό του "-".

Ένα άλλο στοιχείο που μπορούμε να παρατηρήσουμε μέσα από τις ευθυγραμμίσεις είναι η ιστορία της εξέλιξης των ακολουθιών. Από την παραπάνω ευθυγράμμιση φαίνεται ότι μάλλον οι τέσσερις πρώτες και οι τέσσερις τελευταίες εξελίχθηκαν από δύο διαφορετικούς προγόνους, που με τη σειρά τους εξελίχθηκαν από κάποιον αρχικό πρόγονο. Ξεχωρίζουν βασικά τα τέσσερα τμήματα που αντιστοιχούν σε "μεταβλητές" περιοχές των αντισωμάτων και τα τέσσερα τμήματα από τις "σταθερές" περιοχές τους. Βέβαια, για να μπορέσουμε να κάνουμε μια πιο αξιόπιστη φυλογενετική ανάλυση, θα πρέπει να συμπεριλάβουμε μεγαλύτερα τμήματα των πρωτεϊνών στην πολλαπλή μας ευθυγράμμιση.

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

Κόστος Στήλης  = 26

Ο τρόπος που προέκυψε το παραπάνω κόστος είναι με άθροιση του κόστους όλων των πιθανών συνδυασμών των χαρακτήρων της στήλης με βάση το μοντέλο της 1-1 αντιστοίχησης τους. Δηλαδή των (L,L), (L,A), (L,P), (L,G), .... (P,G), (P,S), (P,-), .... (-,G). Σε γενικές γραμμές οποιοδήποτε μοντέλο (πίνακας) κόστους - βαρύτητας μπορεί να χρησιμοποιηθεί, αρκεί να αντιστοιχεί ζεύγη χαρακτήρων σε αριθμητικές τιμές.

Για να πάρουμε μια ποσοτική μέτρηση (απόσταση) των ευθυγραμμίσεων δεν έχουμε παρά να προσθέσουμε το κόστος όλων των στηλών. Αν ο στόχος μας είναι να ελαχιστοποιήσουμε το κόστος ή την απόσταση, τότε το μικρότερο είναι και καλύτερο. Αν αντιθέτως, θέλουμε να μεγιστοποιήσουμε την ομοιότητα μπορούμε να χρησιμοποιήσουμε τον πίνακα PAM που περιγράφουμε στο παράρτημα Γ. Η κάθε στήλη μπορεί να αντιμετωπιστεί σα μία γενικότερη περίπτωση των λειτουργιών διαχείρισης όπως η αντικατάσταση - ταύτιση, η εισαγωγή και η διαγραφή. Θα αντιστοιχίσουμε τις λειτουργίες αυτές σε στήλες με δύο γραμμές, δηλαδή :

όπου s_i,m και s_j,m ανήκουν στο A

Το πρότυπο της 1-1 αντιστοίχησης των γραμμάτων των στηλών είναι το πιο απλό που μπορούμε να χρησιμοποιήσουμε. Έτσι μπορούμε να υπολογίσουμε το κόστος των ευθυγραμμίσεων ανά δύο (όπως αναφέραμε στην παράγραφο 3.1) και να προσθέσουμε τα αποτελέσματα όλων των συνδυασμών.

Μεθοδολογία Ευθυγράμμισης HoMo

Για τις αμινοξικές ακολουθίες των πρωτεϊνών που μελετάμε συνήθως το πλήθος των πιθανών ευθυγραμμίσεων μεταξύ τους είναι τεράστιο. Ο μόνος τρόπος για να περιορίσουμε κάπως τους πιθανούς συνδυασμούς και να μπορέσουμε να καταλήξουμε σε κάποια ικανοποιητική ευθυγράμμιση είναι να χρησιμοποιήσουμε μια σχετικά απλή συνάρτηση κόστους. Ο πιο συστηματικός τρόπος που διαθέτουμε αυτή τη στιγμή για την εύρεση της ιδανικότερης ευθυγράμμισης είναι η χρήση του αλγόριθμου του "δυναμικού προγραμματισμού" (Myers, 1988 και Carrilo, 1988).

Θεωρούμε τις υποακολουθίες ₀:s:_i και ₀:t:_j με . Θα υποθέσουμε τώρα ότι γνωρίζουμε τις ιδανικές ευθυγραμμίσεις μεταξύ όλων των μικρότερων υποακολουθιών των s και t, και ειδικότερα των

₀:s:_(i-1) και ₀:t:_(j-1), των ₀:s:_(i-1) και ₀:t:_j και των ₀:s:_i και ₀:t:_(j-1). Η ιδανική ευθυγράμμιση θα πρέπει να είναι κάποια επέκταση μιας από τις πιο πάνω με τις εξής λειτουργίες διαχείρισης :

• μία αντικατάσταση (s_i,t_j) ή μία ταύτιση (s_i,t_j) εφόσον s_i = t_j
• μία διαγραφή (s_i,-) ή
• μία εισαγωγή (-,t_j).

Εννοείται ότι δεν μπορεί να γίνει επιλογή όταν μία από τις υποακολουθίες είναι κενή, δηλαδή i = 0 ή j = 0 ή και τα δύο :

d_w(₀:s:₀, ₀:t:₀) = 0

d_w(₀:s:_i, ₀:t:₀) = d_w(₀:s:_(i-1), ₀:t:₀) + w(s_i,-) i = 1,...,m

d_w(₀:s:₀, ₀:t:_j) = d_w(₀:s:₀, ₀:t:_(j-1)) + w(-,t_j) j = 1,...,n

Σύμφωνα με αυτές τις διατυπώσεις , και για συγκεκριμένο w, οι αποστάσεις μεταξύ όλων των τιμών των i και j, ορίζουν έναν πίνακα διαστάσεων (m+1)x(n+1) που συμβολίζεται D = d_i,_j = d_w(₀:s:_i, ₀:t:_j).

Οι τρεις τρόποι πρόσβασης στη σχέση ελαχιστοποίησης για το d_i,_j καθορίζουν τους παρακάτω τρόπους εξάρτησης μεταξύ των στοιχείων του πίνακα :

d_i,_j-1 d_i,_j

Η κάτω δεξιά γωνία του πίνακα των αποστάσεων θα περιέχει το επιθυμητό αποτέλεσμα : d_mn = d_w(₀:s:_m, ₀:t:_n) = d_w(s,t).

Στο παράδειγμα των ακολουθιών s = KPNKNKNK και t = KNKNKNLK αντιστοιχεί ο ακόλουθος πίνακας αποστάσεων :
 

	t	K	N	K	N	K	N	L	K
s	0	1	2	3	4	5	6	7	8
K	1	0	1	2	3	4	5	6	7
P	2	1	1	2	3	4	5	5	7
N	3	2	1	2	2	3	4	5	6
K	4	3	2	1	2	2	3	4	5
N	5	4	3	2	1	2	2	3	4
K	6	5	4	3	2	1	2	3	3
N	7	6	5	4	3	2	1	2	3
K	8	7	6	5	4	3	2	2	2

Ο πίνακας σχηματίζεται με τις αποστάσεις (κόστος) μεταξύ όλων των υποακολουθιών που μπορούμε να πάρουμε από τις δύο ακολουθίες. Για παράδειγμα το αρχικό τμήμα της t : ΚΝΚ με το αρχικό τμήμα της s : KPNKN έχουν μια απόσταση 2 διότι το πρώτο με δύο εισαγωγές K-NK- δίνει το δεύτερο. Έτσι το νούμερο δύο βρίσκεται στη θέση με συντεταγμένες τα μήκη 3 και 5 των δύο υποακολουθιών (τμημάτων) των t και s. Η πρώτη γραμμή και η πρώτη στήλη αγνοούνται. Με παρόμοια διαδικασία συμπληρώνεται και ο υπόλοιπος πίνακας.

Με πιο έντονο χρώμα έχουμε σημειώσει τη διαδρομή που ακολουθούμε για την επιλογή του ελάχιστου. Οι διαγώνιες μετακινήσεις αντιστοιχούν σε αντικαταστάσεις ή ταυτίσεις ενώ οι οριζόντιες αντιστοιχούν σε εισαγωγές. Έτσι βλέπουμε ότι οι λειτουργίες διαχείρισης που υιοθετήσαμε οδηγούν σε μια ιδανική ευθυγράμμιση με απόσταση (κόστος) d_w(s,t) = 2. Θα πρέπει να σημειώσουμε ότι η επιλογή του ελάχιστου δεν είναι μοναδική, Έτσι μπορούμε να ακολουθήσουμε διαφορετικές πορείες που υποδηλωνουν την ύπαρξη άλλων ιδανικών ευθυγραμμίσεων.

Η μέθοδος του "δυναμικού προγραμματισμού" είναι μια πολύ γενική τεχνική διερεύνησης. Εφαρμόζεται συνήθως στις περιπτώσεις που θέλουμε να εξερευνήσουμε έναν πολύ μεγάλο χώρο και μπορούμε να δομήσουμε τη διαδικασία έρευνας σε διαδοχικά βήματα έτσι ώστε :

• η αρχική κατάσταση να περιέχει κάποιες λύσεις στα υποπροβλήματα,
• κάθε μερική λύση κάποιου σταδίου (σαν την ιδανική ευθυγράμμιση υποακολουθιών) μπορεί να προκύψει από μερικές λύσεις προηγούμενων σταδίων,
• το τελικό στάδιο της διαδικασίας περιέχει την ιδανική λύση.

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

• Ο όρος απόσταση θα πρέπει να χρησιμοποιείται μόνο όταν τα αξιώματα του μετρικού χώρου ικανοποιούνται. Πιο ειδικά, δε θα μπορούμε να έχουμε αρνητικές αποστάσεις και η ιδανική ευθυγράμμιση θα είναι αυτή που θα ελαχιστοποιεί την απόσταση.
• Ο όρος κόστος αναφέρεται συνήθως σε θετικές τιμές, με το συνολικό κόστος να τείνει να ελαχιστοποιηθεί. Τα μετρικά αξιώματα δεν είναι απαραίτητο να ικανοποιούνται.
• Η βαρύτητα και το ποσοστό επιτυχίας μπορούν να πάρουν θετικές και αρνητικές τιμές. Η πιο συνήθης παραδοχή είναι ότι το υψηλό ποσοστό επιτυχίας αντιπροσωπεύει υψηλό βαθμό ομοιότητας. Κατά συνέπεια, η ιδανική ευθυγράμμιση μεγιστοποιεί το ποσοστό επιτυχίας.
• Ο όρος ομοιότητα συνεπάγεται ότι έχουμε υψηλές τιμές κάποιας ποσότητας και ότι η ιδανική ευθυγράμμιση μεγιστοποιεί την ομοιότητα. Αρνητική τιμή δεν αποκλείεται αλλά αγνοείται όταν παρουσιάζεται.

Ειδικά Χαρακτηριστικά Αμινοξικών Ακολουθιών

Μέχρι στιγμής, έχουμε αντιμετωπίσει το σύμβολο "-" σαν έναν επιπλέον χαρακτήρα, που δηλώνει μία εισαγωγή ή μία διαγραφή. Στην περίπτωση όμως των αμινοξικών ακολουθιών αυτό δεν είναι πάντοτε αρκετό. Ειδικότερα στην περίπτωση της ευθυγράμμισης ομόλογων πρωτεϊνών (Kruskal, 1995), ενδιαφερόμαστε για τη συμπαγή (χωρίς κενά) ευθυγράμμιση των τμημάτων εκείνων που διατηρούνται εξελικτικά και καθορίζουν την αλληλεπίδραση πρωτεϊνών. Οποιαδήποτε διαγραφή ή εισαγωγή σ' αυτά τα τμήματα θα αλλοιώσει πιθανότατα τη βιοχημική τους δράση. Τέτοια τμήματα θέλουμε να ευθυγραμμίζονται μόνο με ταυτίσεις και αντικαταστάσεις, που δε συνεπάγονται μεταβολές στο μήκος τους. Αυτό μπορούμε να το πετύχουμε με την κατασκευή ενός απλού αλγόριθμου ή με την τροποποίηση του αλγόριθμου του δυναμικού προγραμματισμού έτσι ώστε οι διαγραφές και οι εισαγωγές σ' αυτά τα τμήματα να έχουν άπειρο κόστος ή πάρα πολύ μεγάλο. Έτσι ο αλγόριθμος θα αποφύγει αυτές τις λειτουργίες διαχείρισης.

Μερικές φορές, για καθαρά εξελικτικούς λόγους είναι πιο ρεαλιστικό να υποθέσουμε ότι η φύση εισαγάγει ή διαγράφει ολόκληρες υποακολουθίες που αντιστοιχούν σε δομικά τμήματα (συνήθως δευτεροταγείς δομές). Σ' αυτές τις περιπτώσεις η εισαγωγή ενός μόνο χαρακτήρα "-" κοστίζει πολύ περισσότερο από την εισαγωγή πολλών διαδοχικών για το λόγο ότι οι πολλοί διαδοχικοί θα αντιπροσωπεύουν τα ολόκληρα τμήματα που έχουν επηρεαστεί εξελικτικά. Και αυτή η απαίτηση μπορεί να ικανοποιηθεί με απλή μετατροπή του αλγόριθμου του δυναμικού προγραμματισμού.

Πίνακες Κόστους (Dayhoff)

Η ευθυγράμμιση αμινοξικών ακολουθιών επηρεάζει αισθητά τον τρόπο σύγκρισης και αξιολόγησης που μέχρι τώρα έχουμε παρουσιάσει, ακόμα και για τις περιπτώσεις που δεν ισχύουν οι περιορισμοί που αναφέραμε παραπάνω. Αυτό οφείλεται στις σχέσεις ομοιότητας που έχουν μεταξύ τους τα είκοσι αμινοξικά κατάλοιπα που συνθέτουν τις πρωτε? νες. Ένα βασικό στοιχείο για μια πετυχημένη ευθυγράμμιση είναι η ύπαρξη μιας αξιόλογης συνάρτησης κόστους που θα συσχετίζει τα χαρακτηριστικά και τις ιδιότητες των διαφόρων καταλοίπων. Οι συναρτήσεις που υπάρχουν αυτή τη στιγμή, διατυπώνονται πάντα με τη μορφή πίνακα με στοιχεία τις τιμές κόστους του κάθε ζεύγους αμινοξέων.

Η σπουδαιότητα αυτών των πινάκων είναι καθοριστική για τους εξής λόγους :

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

• Τα στοιχεία των πινάκων καθορίζουν τη βαρύτητα ή το κόστος που αναθέτουμε σε κάθε σύγκριση. Για την περίπτωση των αμινοξικών ακολουθιών το κόστος της αντικατάστασης ενός καταλοίπου με κάποιο άλλο δηλώνει την απόσταση μεταξύ τους ενώ με την έννοια της ομοιότητας μας δίνει την τάση για αντικατάσταση του ενός με το άλλο.
• Η απόσταση είναι πιο αντιπροσωπευτική στην αξιολόγηση για την κατασκευή φυλογενετικών δένδρων ενώ η ομοιότητα χρησιμοποιείται για αναζήτηση σε βάσεις δεδομένων.
• Η λογική των αλγόριθμων δεν αλλάζει : μεγιστοποιώντας την ομοιότητα είναι ουσιαστικά το ίδιο με την ελαχιστοποίηση της απόστασης.
• Οι πίνακες ομοιότητας και απόστασης συσχετίζονται (μετατρέπονται) άμεσα μεταξύ τους με τη χρήση της κατάλληλης συνάρτησης για την κάθε περίπτωση που εφαρμόζονται.

Παραλλαγές της Ευθυγράμμισης Ανά Ζεύγη.

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

Με τον όρο τοπική ευθυγράμμιση εννοούμε τις περιπτώσεις που η ακολουθία s είναι πολύ μικρότερη της ακολουθίας t και ψάχνουμε την υποακολουθία της t που ευθυγραμμίζεται καλύτερα με την s. Για να το πετύχουμε αυτό τροποποιούμε τον αλγόριθμο του δυναμικού προγραμματισμού έτσι ώστε να μη χρεώνονται με κόστος οι διαγραφές τμημάτων της t. Εναλλακτικά μπορούμε να δούμε την τελευταία γραμμή του πίνακα κόστους που δημιουργούμε στη γενική περίπτωση, όπου οι ελάχιστες τιμές αντιστοιχούν σε ταύτιση επιμέρους τμημάτων.

Η τοπική ομοιότητα από την άλλη μεριά αναφέρεται σε λειτουργική ομοιότητα (φυσικών και χημικών χαρακτηριστικών) τμημάτων των πρωτεϊνών με ιδιαίτερα τριτοταγή χαρακτηριστικά, όπως το ενεργό κέντρο των πρωτεϊνών. Με εξαίρεση αυτά τα τμήματα οι υπόλοιπες περιοχές των πρωτεϊνών μπορεί να διαφέρουν ριζικά. Έτσι μια ευθυγράμμιση δύο τέτοιων πρωτεϊνών είναι απίθανο να εμφανίσει καθαρές περιοχές υψηλής ομοιότητας, διότι ο αλγόριθμος τείνει να ελαχιστοποιήσει τις αποστάσεις στο σύνολο των ακολουθιών, διαχέοντας έτσι την ομοιότητα των υποπεριοχών. Αυτό που κάνουμε σ' αυτές τις περιπτώσεις είναι να προσαρμόσουμε τον αλγόριθμο έτσι ώστε να μεγιστοποιείται η ομοιότητα αντί να ελαχιστοποιείται η απόσταση.

Η λύση στα περισσότερα προβλήματα ευθυγράμμισης ακολουθιών περιλαμβάνει οργάνωση όλων αυτών των χαρακτηριστικών, που αναφέραμε στις προηγούμενες παραγράφους, σε υπολογιστική δομή ώστε να μπορούμε να καταλήξουμε σε θετικά αποτελέσματα. Αυτό που κάνουμε τουλάχιστον στα προγράμματα που υπάρχουν χρησιμοποιούνται και τα οποία θα δούμε παρακάτω, είναι να υιοθετήσουμε ιεραρχικές μεθόδους επιλογής που θα προσεγγίζουν τις λύσεις (αποστάσεις, ευθυγραμμίσεις).