| Περίληψη |
Τα δίκτυα χρησιμοποιούνται ευρύτατα για την μοντελοποίηση γνώσης και δεδομένων στον τομέα των βιοεπιστημών. Δύο χαρακτηριστικά παραδείγματα είναι η οντολογία γονιδίων και τα λειτουργικά δίκτυα του εγκεφάλου. Η οντολογία γονιδίων (GO) είναι δομημένη ως κατευθυνόμενος άκυκλος γράφος (DAG). Η οπτικοποίηση ολόκληρης της οντολογίας γονιδίων, με τους κόμβους να αναπαρίστανται ως μικροί κύκλοι ή πολύγωνα και τις ακμές ως γραμμές, οδηγεί σε μια δυσνόητη εικόνα. Γι΄ αυτό προτείνουμε την τεχνική της οπτικοποίησης με
πλήρωση του χώρου για κατευθυνόμενους άκυκλους γράφους. Αυτή η τεχνική έχει δοκιμαστεί σε δένδρα (treemaps) και παρέχει την δυνατότητα να απεικονιστούν ευανάγνωστα χιλιάδες κόμβοι σε περιορισμένο χώρο. Η τεχνική treemap έχει χρησιμοποιηθεί για να απεικονίσει την οντολογία γονιδίων, η οποία πρώτα μετατρέπεται σε δένδρο δημιουργώντας τόσα αντίγραφα ενός κόμβου v, ό σα είναι και τα μονοπάτια που ξεκινούν από τον κόμβο αφετηρία και καταλήγουν στον κόμβοv. ΄Ομως αυτή η μετατροπή δημιουργεί σημαντικά προβλήματα, όπως ο μεγάλος αριθμός κόμβων των παραγόμενων δένδρων και το ότι τα αντίγραφα ενός κόμβου βρίσκονται διασκορπισμένα μέσα στην περιοχή σχεδίασης. Σε αυτή την διατριβή
παρουσιάζεται το πρόβλημα της απεικόνισης κατευθυνόμενων άκυκλων γράφων με πλήρωση του χώρου, χωρίς ο γράφος να μετατραπεί σε δένδρο. Καταρχήν, ορίζεται το πρόβλημα έτσι, ώστε να γενικεύει την περίπτωση των δένδρων και ονομάζεται DAGmap. Κατόπιν, αποδεικνύεται ότι το να αποφασίσουμε αν ένας τυχαίος γράφος επιδέχεται μια απεικόνιση DAGmap είναι ένα NP-πλήρες πρόβλημα. Επομένως, αξίζει να μελετηθούν ειδικές περιπτώσεις του προβλήματος, και
ευρετικοί αλγορίθμοι που μετατρέπουν τον γράφο έτσι, ώστε να επιδέχεται
μια απεικόνιση DAGmap. Μια ειδική περίπτωση του προβλήματος ονομάζεται
μονοδιάστατο DAGmap, διότι το αρχικό ορθογώνιο χωρίζεται κατά μήκος μίας
μόνο διάστασης, π.χ., την κάθετη. Αποδεικνύεται ότι ένας κατευθυνόμενος άκυκλος γράφος επιδέχεται ένα μονοδιάστατο DAGmap, εάν και μόνο εάν ο γράφος επιδέχεται μια αναπαράσταση κατευθυνόμενης ε-ορατότητας. Αυτή η ένα-προς-ένα
αντιστοιχία των δύο προβλημάτων οδηγεί σε πλήρη χαρακτηρισμότης κατηγορίας των γράφων που επιδέχονται μονοδιάστατο DAGmap, καθώς και σε γραμμικούς αλγορίθμους απόφασης και σχεδίασης. Μια άλλη ειδική περίπτωση του προβλήματος εμφανίζεται όταν οι γράφοι είναι κατευθυνόμενοι σειριακοί-παράλληλοι δύο τερματικών (TTSP). Αποδεικνύεται ότι κάθε TTSP γράφος επιδέχεται απεικόνιση DAGmap, η οποία μπορεί να ζωγραφιστεί σε γραμμικόχρό νο χρησιμοποιώντας το δένδρο αποδόμησης του γράφου. Ο ευρετικός αλγόριθμος βασίζεται σε σχέσεις
κυριαρχίας μεταξύ των κόμβων και χωρίζει ένα κατευθυνόμενο άκυκλο γράφο σε συνιστώσες έτσι, ώστε η κάθε μία απόαυτές να συνδέεται με τον υπόλοιπο γράφο μόνο μέσω του κόμβου αφετηρίας και/ή τερματισμού της. ΄Επειτα ο αλγόριθμος συνδυάζει τις απεικονίσεις των συνιστωσών για να βρει την απεικόνιση του γράφου.
Σε περίπτωση που μια συνιστώσα δεν επιδέχεται DAGmap, τότε μετατρέπεται σε TTSP γράφο. Οι αλγόριθμοι των δύο ειδικών περιπτώσεων του προβλήματος και ο ευρετικός αλγόριθμος έχουν υλοποιηθεί στο πρόγραμμα DAGmap View. Το πρόγραμμα αυτό έχει σχεδιαστεί με αρκετές νέες ιδέες, όπως ο διαχωρισμός της συνάρτησης εύρεσης συντεταγμένων των ορθογωνίων απότην συνάρτηση παρουσίασης της δομής της ιεραρχίας του γράφου. Επίσης, το DAGmap View είναι ένα
ιδανικόεργαλεί ο για την οπτικοποίηση και την πλοήγηση στην οντολογία γονιδίων.Τα λειτουργικά δίκτυα του εγκεφάλου μοντελοποιούνται απόγράφους με τιμές στις ακμές τους. Οι κόμβοι αντιστοιχούν σε περιοχές του εγκεφάλου και οι ακμές φανερώνουν στατιστική εξάρτηση μεταξύ των αντίστοιχων περιοχών. Οι τιμές των
ακμών ανήκουν στο διάστημα (0, 1] και θεωρούνται ως ένταση της εξάρτησης.
Τέτοιου είδους δίκτυα ονομάζονται γκρίζας κλίμακας (greyscale), διότι μπορούν να οπτικοποιηθούν με αποχρώσεις του γκρί. Δεδομένου ότι δεν υπάρχει διαθέσιμο ένα πρόγραμμα που αναλύει και οπτικοποιεί greyscale δίκτυα, ενώ είναι χρήσιμο στους ερευνητές που ασχολούνται με την συνδεσιμότητα του εγκεφάλου,
δημιουργήσαμε το BrainNetVis. Το πρόγραμμα αυτό οπτικοποιεί τα greyscale δίκτυα και υπολογίζει μια σειρά απόμετρικές δικτύων, οι περισσότερες από τις οποίες επιλέχθηκαν απότη σχετική βιβλιογραφία. Επίσης παρουσιάζονται και νέα θεωρητικά αποτελέσματα: α) μια συνάρτηση που μετατρέπει την ένταση μιας ακμής σε μήκος της ακμής, β) ένας τύπος που υπολογίζει την σημασία ενός κόμβου, τόσο με βάση την θέση του στο δίκτυο, όσο και από τα χαρακτηριστικά του, και γ) ορισμένες γενικεύσεις για greyscale δίκτυα μετρικών που προϋπήρχαν για γράφους. Τέλος, η παρουσίαση του προγράμματος BrainNetVis γίνεται μέσω δύο
αναλύσεων δεδομένων εγκεφαλογραφημάτων. Στην πρώτη ανάλυση συγκρίνονται
τα λειτουργικά δίκτυα του εγκεφάλου αλκοολικών και μη αλκοολικών ατόμων κατά την διάρκεια ενός πειράματος προσωρινής μνήμης. Αποδεικνύεται ότι υπάρχουν στατιστικά σημαντικές διαφορές μεταξύ των δύο ομάδων στη βήτα ζώνη συχνοτήτων (beta band). Στην δεύτερη μελέτη συγκρίνονται τα λειτουργικά δίκτυα του εγκεφάλου ενός υγιούς ατόμου κατά την διάρκεια εικονικών κινήσεων είτε του ποδιού
του (οποιοδήποτε απότ α δύο) είτε του αριστερού χεριού του. Διαπιστώνεται ότι τα αντίστοιχα δίκτυα είναι σχεδόν όμοια και προτείνεται μια μέθοδος για την διάκριση μεταξύ των δύο περιπτώσεων (ποδιού - αριστερού χεριού).
|
Algorithms for the analysis and visualization of biomedical networks
