progintro @ dit
Εργασία 2 - Άσκηση 2: DNA Matching
Σχόλιο 1 - Η πρώτη σκέψη
Για να βρούμε τη μέγιστη κοινή αλυσίδα, πρέπει να συγκρίνουμε κάθε χαρακτήρα του dna2 με κάθε χαρακτήρα του dna1 και να βρούμε ποιος είναι ο μέγιστος αριθμός διαδοχικών βάσεων που είναι ίδιες και στα δύο dna.
Θα βοηθούσε να κάναμε τη σύγκριση αυτή με ένα δισδιάστο πίνακα dnas[dna1_length][dna2_length], του οποίου η εγγραφή dnas[i][j] θα ήταν ίση με 1 μόνο αν dna1[i] == dna2[j], αλλιώς 0. Μετά, θα ήταν εύκολο να βρούμε τη μέγιστη κοινή αλυσίδα, αφού αυτή θα αντιστοίχουσε στη μακρύτερη διαγώνιο από άσσους.
Π.χ. A C T G C G G
A 1 0 0 0 0 0 0
G 0 0 0 1 0 1 1
T 0 0 1 0 0 0 0
G 0 0 0 1 0 1 1
C 0 1 0 0 1 0 0
A 1 0 0 0 0 0 0
Ωστόσο, για μεγάλες αλυσίδες, αυτή η τεχνική οδηγεί σε άσκοπη σπατάλη μνήμης, η δέσμευση της οποίας ακόμη και στο σωρό υπάρχει πιθανότητα να αποτύχει .
Σχόλιο 2 - Προσπάθεια εξοικονόμησης μνήμης - η συνάρτηση find_longest_common_sequence
Παρατήρωντας τον παραπάνω πίνακα από κάτω προς τα πάνω, φαίνεται ότι ίσως να μπορούσαμε να ξεφορτωθούμε περιττές γραμμές, αν σε κάθε επόμενη αθροίζαμε τα μέγιστα μήκη κοινών ακολουθιών που είχαμε εντοπίσει ως την προηγούμενη.
Έτσι, δημιουργούμε έναν πίνακα common_suffixes με μέγεθος dna1_length, τον οποίο ανανεώνουμε dna2_length φορές, προσθέτωντας κάθε φορά τις νέες κοινές βάσεις (που αλλάζουν τα μήκη των μέγιστων κοινών καταλήξεων) και ανανεώνοντας σε κάθε αλλαγή τις global μεταβλητές max_length και starting_index.
Κατά την εκτέλεση του προγράμματος για το παραπάνω παράδειγμα, ο πίνακας θα είχε αυτή την εξέλιξη:
1 0 0 0 0 0 0
0 1 0 0 1 0 0
0 0 0 2 0 1 1
0 0 3 0 0 0 0
0 0 0 1 0 1 1
1 0 0 0 0 0 0
Ιδιαίτερη σημασία έχει το γεγονός ότι η ανανέωση του common_suffixes πραγματοποιείται κατά μήκος διαγωνίων και όχι καθέτως, αφού αν dna1[i] == dna2[j] δεν θέλουμε dna1[i] = dna2[j+1], αλλά dna1[i+1] = dna2[j+1], ώστε οι κοινές βάσεις να είναι διαδοχικές και στα δύο dna.
Αν κάποιο ζεύγος βάσεων δεν είναι κοινό, τότε διακόπτεται και η κοινή αλυσίδα βάσεων (η διάγωνιος) που οδηγούσε σε αυτό και η τιμή του αντίστοιχου στοιχείου στον πίνακα common_suffixes γίνεται 0. Ωστόσο, αν το μήκος της ακολουθίας που είχε δημιουργηθεί μέχρι εκείνη τη στιγμή ήταν μέγιστο, αυτό έχει αποθηκευτεί.
Μετά τον τερματισμό της συνάρτησης (όταν δεν υπάρχουν πια άλλες βάσεις στο dna2 για να συγκριθούν), γνωρίζουμε και το μέγιστο μήκος και το σημείο του dna1 όπου αρχίζει η μέγιστη κοινή ακολουθία, άρα μπορούμε να την προσδιόρισουμε και να την τυπώσουμε.
Με αυτόν τον τρόπο, κατάφεραμε από Ο(n * m) μνήμη να χρησιμοποιούμε μόνο Ο(n), όπου n = dna1_length και m = dna2_length.