Εφαρμογή Γενετικού Αλγορίθμου στη Βιολογία/Ιατρική

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

·         Τη στοιχειακή σύσταση του δείγματος

·         Τη δομή ανόργανων, οργανικών, οργανο-μεταλλικών και βιολογικών μορίων

·         Την ποιοτική και ποσοτική σύσταση μιγμάτων

·         Τη δομή και τη σύσταση επιφανειών

Την αναλογία ισοτόπων στοιχείων

Αναγνώριση πρωτεϊνών με φασματομετρία μάζας (mass spectrometry ή MS)

1.  Η μάζα των πεπτιδίων που παράγονται με επώαση με τρυψίνη δίνει ένα χαρακτηριστικό «αποτύπωμα».

2. Τα  πεπτίδια αυτά αναλύονται περαιτέρω με φασματομετρία μάζας για να προκύψουν πληροφορίες σχετικά με τη αμινοξική τους σύσταση.

3. Ανάλυση των δεδομένων από πρωτεϊνικές βάσεις δεδομένων αποκαλύπτει την εν λόγω πρωτεϊνη.

Στο παραπάνω παράδειγμα φαίνεται η εύρεση μιας “μοριακής υπογραφής”, που αποτελείται από συγκεντρώσεις 3 πεπτιδίων. Το βασικό ζητούμενο της άσκησης είναι η εύρεση της καλύτερης "μοριακής υπογραφής" η οποία θα αποτελείται από 5 συγκεντρώσεις πεπτιδίων και με βάση τις τιμές αυτών ο ταξινομητής θα αναγνωρίζει με τον καλύτερο τρόπο αν κάποιος είναι ασθενής ή όχι. Στο σχήμα 1 φαίνεται ότι οι συγκεντρώσεις πεπτιδίων χαρακτηρίζονται με βάση τον οριζόντιο άξονα (m/z), ενώ η τιμή της κάθε συγκέντρωσης φαίνεται στον κάθετο άξονα του σχήματος.

Για την εκτέλεση της παρούσας άσκησης θα χρησιμοποιήσουμε πρωτεΐνες που αντιστοιχούν σε 8192 τιμές φασματομετρίας μάζας με εύρος 1-8192 m/z.

Επίσης, θεωρούμε ότι η βέλτιστη "μοριακή υπογραφή" αποτελείται από 5 πεπτίδια που αναπαρίστανται από τις τιμές μάζας ανά φορτίο (m/z) σε δυαδική κωδικοποίηση 5 x 13 ψηφίων.

Για παράδειγμα η υπογραφή των πεπτιδίων 21,508,1201,3058,7240 έχει δυαδική κωδικοποίηση:  0000000010100 0000111111011 0010010110000 0101111110001 1110001000111

Το dataset αποτελείται από τα δεδομένα 200 συνολικά ατόμων από τα οποία οι 88 είναι ασθενείς που πάσχουν από καρκίνο και οι 112 υγιή άτομα στο αρχείο cancer_data δίνονται οι τιμές  φασματομετρίας μάζας με εύρος 1-8192 m/z ανά γραμμή για κάθε ασθενή, ενώ στο cancer_labels αναφέρεται αν το αντίστοιχο άτομο πάσχει από καρκίνο (1) ή είναι υγιές (-1).

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

Σχεδιάστηκε και υλοποιήθηκε ένας Γενετικός Αλγόριθμος με τα παρακάτω χαρακτηριστικά:

(α) δυαδική κωδικοποίηση ατόμων μήκους L=65(5*13)

(β) απλή αναλογική επιλογή (roulette wheel selection)

(γ)τελεστή διασταύρωσης (crossover operator) ενός σημείου με πιθανότητα διασταύρωσης p_c

(δ) τελεστή μετάλλαξης δυαδικών ψηφίων με πιθανότητα μετάλλαξης p_m

(ε) τη συνάρτηση καταλληλότητας με γραμμικό ταξινομητή.

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

A. Υλοποίηση Γ.Α. (10/20)

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

A.1 (3/10) Αφού μελετήσετε τον κώδικα να εντοπίσετε τη συνάρτηση ανάγνωσης και αποθήκευσης του dataset.

A.2. (7/10) Να εντοπίσετε τις γραμμές του κώδικα που υλοποιούν τη συνάρτηση καταλληλότητας και να περιγράψετε σύντομα, τον ταξινομητή που υλοποιεί.

B. (10/20) Εκτέλεση του Αλγορίθμου

Να τρέξετε τον αλγόριθμο και να συμπληρώσετε τον παρακάτω πίνακα. Ποια είναι τα συμπεράσματά σας; Με βάση τα αποτελέσματα του πίνακα να σχεδιάσετε την καμπύλη εξέλιξης (απόδοση / αριθμό γενιών) της καλύτερης "μοριακής υπογραφής".

Α/α	μεγεθοσ πληθυσμου	αριθμοσ γενιων	πιθανοτητα διαστΑΥΡΩσης	πιθανοτητα ΜΕΤΑΛΛΑΞΗΣ	ΜΕΣΗ ΑΠΟΔΟΣΗ ΠΛΗΘΥΣΜΟΥ
1	50	50	0.9	0.01
2	50	50	0.25	0.1
3	50	100	0.9	0.01
4	50	100	0.25	0.1
5	50	1000	0.9	0.01
6	50	1000	0.25	0.1
7	100	1000	0.9	0.01
8	100	1000	0.25	0.1
9	200	1000	0.9	0.01
10	200	1000	0.25	0.1

ΠΡΟΣΟΧΗ: Επειδή οι Γενετικοί είναι αλγόριθμοι οι οποίοι δεν εξασφαλίζουν την ίδια απόδοση (επειδή είναι στοχαστικοί αλγόριθμοι) σε κάθε εκτέλεσή τους θα πρέπει να εκτελέσετε τον αλγόριθμο τουλάχιστον δέκα φορές και στον πίνακα να σημειώσετε το μέσο όρο των αποδόσεων