Λειτουργικά μοτίβα δικτύων
Λειτουργικά μοτίβα δικτύων ονομάζονται οι στατιστικά υπερ-αντιπροσωπευμένοι υπο-γράφοι που απαντώνται σε δίκτυα του πραγματικού κόσμου (εν αντιθέσει με δίκτυα που έχουν προκύψει από κάποιο μοντέλο τυχαιοποιημένου δικτύου).
Η Βιολογία των ζωντανών οργανισμών περιλαμβάνει πολλά περίπλοκα δίκτυα ανεξάρτητων γεγονότων και αλληλεπιδράσεων μεταξύ των βιομορίων. Παραδείγματα τέτοιων δικτύων που περιλαμβάνουν δίκτυα που σχετίζονται με τη μεταγραφή, ή την ρύθμιση των γονιδίων, δίκτυα που αφορούν την αλληλεπίδραση πρωτεΐνης-πρωτεΐνης (PPI), μεταβολικά μονοπάτια και άλλα, έδειξαν πως τα δίκτυα από διάφορους τομείς, βιολογικούς ή μη, περιλαμβάνουν αρκετά μικρά τοπολογικά πρότυπα τα οποία είναι τόσο συχνά, που είναι απίθανο να εμφανίζονται τυχαία, αλλά σχετίζονται με κάποια λειτουργική και καίρια σημασία. Διαφορετικά δίκτυα τείνουν να έχουν διαφορετικά σύνολα τέτοιων συχνά εμφανιζόμενων δομών. Αυτές οι δομές αναφέρονται ως «μοτίβα δικτύων» και είναι γνωστές ως το απλό δομικό στοιχείο ενός σύνθετου δικτύου. Η ανακάλυψη αυτή προκάλεσε ένα πλήθος ερευνητικών προσπαθειών την προηγούμενη δεκαετία και ο συγκεκριμένος τομέας έχει ακόμα πολλές προοπτικές νέων ανακαλύψεων ακόμα και σήμερα.[1] Τα μοτίβα δικτύων έχουν επίσης μελετηθεί και σε άλλους τομείς, όπως των ηλεκτρονικών κυκλωμάτων, της διανομής ενέργειας, της οικολογίας (food web), του Διαδικτύου, των μέσων κοινωνικής δικτύωσης και φυσικά των μοριακών δομών.
Μία πιθανή επιβεβαίωση για την σημαντικότητα των μοτίβων αποτελεί η συντήρησή τους. Κατά την εξέλιξη, η συντήρηση είναι άρρηκτα συνδεδεμένη με την σημαντικότητα. Συγκεκριμένα, στα βιολογικά δίκτυα η συντήρηση των πρωτεϊνών σε ένα μοτίβο μπορεί να είναι ενδεικτική της βιολογικής σημαντικότητας αυτού του μοτίβου. Εάν υπάρχει εξελικτική πίεση στο να διατηρηθούν συγκεκριμένα μοτίβα, θα αναμενόταν τα στοιχεία που τα απαρτίζουν να είναι εξελικτικά συντηρημένα και να έχουν αναγνωρίσιμα ορθολογικά στοιχεία και σε άλλους οργανισμούς.[2]
Ιστορία[Επεξεργασία | επεξεργασία κώδικα]
Η ιδέα παρουσιάστηκε πρώτη φορά το 2002 από τον Uri Alon και την ομάδα του, όταν τα μοτίβα δικτύων βρέθηκαν στα δίκτυα γονιδιακής ρύθμισης (μεταγραφή) του βακτηρίου E.coli και έπειτα σε μεγαλύτερα δίκτυα φυσικών δικτύων.[3] Από τότε, ένας σημαντικός αριθμός μελετών διεξάγεται πάνω σε αυτό το αντικείμενο. Κάποιες από τις μελέτες εστιάστηκαν σε βιολογικά δίκτυα, ενώ άλλες στην υπολογιστική θεωρία των μοτίβων των δικτύων. Οι βιολογικές μελέτες προσπαθούν να ερμηνεύσουν τα μοτίβα που ανιχνεύονται στα βιολογικά δίκτυα. Ένα διακριτό σύνολο μοτίβων δικτύων αναγνωρίστηκε σε διάφορους τύπους βιολογικών δικτύων, όπως τα νευρωνικά δίκτυα και τα δίκτυα που αφορούν αλληλεπιδράσεις πρωτεϊνών.[4] Η έρευνα εστιάστηκε στη βελτίωση των ήδη υπαρχόντων εργαλείων ανίχνευσης μοτίβων προκειμένου να βοηθήσει στις βιολογικές έρευνες και να επιτρέψει την ανάλυση μεγαλύτερων δικτύων.
Είδη Λειτουργικών Μοτίβων[Επεξεργασία | επεξεργασία κώδικα]
Κάθε δίκτυο αποτελείται από κόμβους, που αντιπροσωπεύουν τα γονίδια και κατευθυνόμενες ακμές, που απεικονίζουν τον έλεγχο ενός γονιδίου από έναν παράγοντα μεταγραφής που κωδικοποιείται από κάποιο άλλο γονίδιο. Με τον τρόπο αυτό δημιουργούνται μοτίβα γονιδίων που ρυθμίζουν αναμεταξύ τους τα επίπεδα μεταγραφής τους.[5] Αναλύοντας τέτοια μεταγραφικά δίκτυα παρατηρείται εμφάνιση των ίδιων μοτίβων πολλές φορές και σε ποικίλους οργανισμούς, από τα βακτήρια έως και τον άνθρωπο. Τα μοτίβα των δικτύων εντοπίστηκαν αρχικά στο βακτήριο E.coli καθώς και στο ζυμομύκητα S.cerevisiae, λόγω της πληθώρας των δεδομένων που έχουν συγκεντρωθεί.[6] Οι λειτουργίες που σχετίζονται με τα πιο κοινά μοτίβα δικτύων έχουν ερευνηθεί και αποδειχθεί με αρκετές ερευνητικές μελέτες τόσο σε θεωρητικό όσο και πειραματικό επίπεδο και παρακάτω παρουσιάζονται ορισμένα από τα πιο κοινά μοτίβα μαζί με τη λειτουργία τους.
Negative auto-regulation (NAR)[Επεξεργασία | επεξεργασία κώδικα]
Η αρνητική αυτορρύθμιση (NAR) συμβαίνει όταν ένας παράγοντας μεταγραφής καταστέλλει την μεταγραφή του ίδιου του του γονιδίου. Το μοτίβο αυτό εμφανίζεται στους μισούς περίπου καταστολείς της E.coli και σε πολλούς ευκαρυωτικούς καταστολείς. Έχει δειχθεί ότι εμφανίζει δύο ειδών σημαντικές λειτουργίες: 1) επιταχύνει το χρόνο απόκρισης των κυκλωμάτων των γονιδίων και 2) μειώνει τη μεταβλητότητα από κύτταρο σε κύτταρο σε πρωτεϊνικό επίπεδο.[7]
Positive auto-regulation (PAR)[Επεξεργασία | επεξεργασία κώδικα]
Η θετική αυτορρύθμιση (PAR) συμβαίνει όταν ένας παράγοντας μεταγραφής ενισχύει τα επίπεδα της δικής του παραγωγής. Το μοτίβο αυτό λειτουργεί αντίθετα συγκριτικά με το μοτίβο NAR, καθώς επιβραδύνει το χρόνο απόκρισης των κυκλωμάτων των γονιδίων και συνήθως ενισχύει τη μεταβλητότητα από κύτταρο σε κύτταρο σε επίπεδο πρωτεϊνών.[7]
Feed-forward loop (FFL)[Επεξεργασία | επεξεργασία κώδικα]
Το μοτίβο FFL αποτελείται από 3 γονίδια: τον ρυθμιστή Χ, ο οποίος ρυθμίζει το Ψ, και ένα γονίδιο Ζ που ρυθμίζεται από το γονίδιο Ψ. Το μοτίβο αυτό εμφανίζεται σε εκατοντάδες συστήματα γονιδίων στην E.coli και στη ζύμη καθώς και σε άλλους οργανισμούς. Κάθε μία από τις τρεις ρυθμιστικές αντιδράσεις μπορεί να είναι είτε ενεργοποίηση είτε καταστολή και για το λόγο αυτό υπάρχουν 8 πιθανοί τύποι FFL, που χωρίζονται σε συνδεδεμένους και μη-συνδεδεμένους. Δύο από τους 8 πιθανούς τύπους απαντώνται συχνότερα στα μεταγραφικά δίκτυα, ο C1-FFL και ο I1-FFL.[7]
Single-input models (SIM)[Επεξεργασία | επεξεργασία κώδικα]
Το μοτίβο SIM χαρακτηρίζεται από ένα ρυθμιστή Χ ο οποίος ρυθμίζει μία ομάδα γονιδίων-στόχων ενώ ταυτόχρονα ρυθμίζει και τον εαυτό του. Σε ιδανικές περιπτώσεις δεν υπάρχει άλλος ρυθμιστής για τη ρύθμιση των γονιδίων-στόχων. Κύρια λειτουργία του μοτίβου αυτού είναι η συντονισμένη έκφραση μιας ομάδας γονιδίων με κοινή λειτουργία.[7]
Dense overlapping regulons (DOR)[Επεξεργασία | επεξεργασία κώδικα]
Το μοτίβο DOR χαρακτηρίζεται από ένα πλήθος ρυθμιστών που ελέγχουν συνδυαστικά ένα πλήθος γονιδίων εξόδου, δηλαδή πολλαπλές είσοδοι μεταφράζονται σε πολλαπλές εξόδους. Για την πλήρη κατανόηση του μοτίβου απαιτούνται τόσο τα βέλη που συνδέουν την είσοδο με την έξοδο όσο και οι ακριβείς λειτουργίες εισόδου. Στο δίκτυο της E.coli απαντώνται αρκετά μοτίβα DOR που περιλαμβάνουν εκατοντάδες γονίδια εξόδου, καθένα από τα οποία είναι υπεύθυνο για μια πληθώρα βιολογικών λειτουργιών. Αντίστοιχα μοτίβα απαντώνται και στο δίκτυο της ζύμης.[7]
Αλγόριθμοι[Επεξεργασία | επεξεργασία κώδικα]
Τα βιολογικά και τα μηχανικά δίκτυα έχει αποδειχθεί πως παρουσιάζουν μοτίβα, δηλαδή μία μικρή ομάδα χαρακτηριστικών προτύπων, που συναντώνται πολύ συχνά. Τα μοτίβα αυτά διαδραματίζουν σημαντικό ρόλο στα Πολύπλοκα Βιολογικά Δίκτυα. Έχουν προταθεί ποικίλες λύσεις για το καίριο πρόβλημα της ανίχνευσης μοτίβων.[8] Έτσι, υπάρχουν πολλοί διαφορετικοί αλγόριθμοι για την ανίχνευση μοτίβων, οι οποίοι παρουσιάζονται συνοπτικά παρακάτω.
mfinder[Επεξεργασία | επεξεργασία κώδικα]
Ο αλγόριθμος "mfinder" αποτελεί το πρώτο εργαλείο για την εξόρυξη μοτίβων και εφαρμόζει δύο ειδών αλγορίθμους: την πλήρη απαρίθμηση και τη μέθοδο δειγματοληψίας.[9]
FPF (Mavisto)[Επεξεργασία | επεξεργασία κώδικα]
Ο αλγόριθμος "Mavisto" καλείται ανιχνευτής ευέλικτων σχημάτων και χρησιμοποιείται για την εξαγωγή συχνά χρησιμοποιούμενων υπο-γράφων ενός δικτύου εισόδου και την εισαγωγή τους στο σύστημα που καλείται Mavisto.[10]
ESU (FANMOD)[Επεξεργασία | επεξεργασία κώδικα]
Ο συγκεκριμένος αλγόριθμος "FANMOD" παρέχει σημαντικές βελτιώσεις σε σχέση με τον mfinder και χρησιμοποιείται τόσο για κατευθυνόμενα όσο και για μη-κατευθυνόμενα δίκτυα.[11]
ΝeMoFinder[Επεξεργασία | επεξεργασία κώδικα]
Ο αλγόριθμος "NeMoFinder" χρησιμοποιείται για την εύρεση μοτίβων μεγέθους έως 12, για δίκτυα που αφορούν μόνο PPI, τα οποία παρουσιάζονται ως μη-κατευθυνόμενοι γράφοι. Δεν μπορεί να χρησιμοποιηθεί για την εύρεση μοτίβων σε κατευθυνόμενα δίκτυα.[12]
Grochow-Kelis[Επεξεργασία | επεξεργασία κώδικα]
Ο αλγόριθμος Grochow-Kelis επινοήθηκε από τους Grochow και Kellis το 2007 και αποτελεί το πρώτο παράδειγμα μοτιβο-κεντρικού αλγορίθμου. Ο Grochow χρησιμοποίησε ρήξη της συμμετρίας με χαρτογράφηση προκειμένου να μετρήσει την συχνότητα του υπογράφου. Χρησιμοποιεί τα πακέτα ‘geng’ and ‘directg’ από τον McKay για να παράγει όλους τους μη ισομετρικούς υπογράφους μεγέθους κ. Στη συνέχεια, ελέγχει αν κάποιος από αυτούς είναι μοτίβο.[13]
Color-Coding Approach[Επεξεργασία | επεξεργασία κώδικα]
Το 2008 οι Alon et al. παρουσίασαν μία προσέγγιση προκειμένου να βρίσκονται μη επαγόμενοι υπογράφοι. Αυτή η τεχνική (Color-Coding Approach) δουλεύει σε μη κατευθυνόμενα δίκτυα, όπως το PPI. Εφαρμόζεται για υπογράφους μεγέθους μέχρι και 10.[14]
MODA[Επεξεργασία | επεξεργασία κώδικα]
Αναπτύχθηκε από τον Omidi et al. το 2009. Αυτός ο μοτιβο-κεντρικός αλγόριθμος MODA χρησιμοποιεί το μοτίβο ανάπτυξης δένδρου, το οποίο αποκαλείται δένδρο επέκτασης (expansion tree) και το οποίο χρησιμοποιεί ρήξη της συμμετρίας για να παράγει μοναδικές επεκτάσεις. Στη συνέχεια, χρησιμοποιεί χαρτογράφηση του πρώτου επιπέδου αυτού του δένδρου. Οι πληροφορίες που πήρε από το προηγούμενο επίπεδο χρησιμοποιούνται για κάθε επόμενο επίπεδο. Αξίζει να σημειωθεί πως αυτός ο αλγόριθμος υλοποιεί μία εξελιγμένη στρατηγική σε κάθε επίπεδο, αντιθέτως με τον αλγόριθμο Grochow.[15]
Kavosh[Επεξεργασία | επεξεργασία κώδικα]
Αποτελεί έναν αλγόριθμο (Αλγόριθμος Kavosh) ο οποίος είναι δικτυο-κεντρικός. Χρησιμοποιεί το μοτίβο ανάπτυξης δένδρου για να απαριθμήσει όλα τα μεγέθη υπό-γράφων του δικτύου. Ο συγκεκριμένος αλγόριθμος διατρέχει όλο το δένδρο για να εξασφαλίσει ότι κάθε υποψήφιο μοτίβο συναντάται μόνο μία φορά.[16]
G-Tries[Επεξεργασία | επεξεργασία κώδικα]
Το 2010 οι Pedro Ribeiro και Fernando Silva πρότειναν μία νέα δομή δεδομένων (Δομή δεδομένων G-Tries) για την αποθήκευση μίας ομάδας υπογράφων, η οποία ονομάστηκε g-trie. Αυτή η δομή δεδομένων αποθηκεύει τους υπογράφους ανάλογα με τις δομές τους και βρίσκει αν καθένας από αυτούς εμφανίζεται σε ένα μεγαλύτερο γράφο. Μία από τις πλέον αξιοσημείωτες πτυχές αυτής της δομής δεδομένων είναι η ανακάλυψη των μοτίβων των δικτύων. Έτσι, δεν υπάρχει ανάγκη να βρεθούν κάποιοι τυχαία που δεν ανήκουν στο βασικό δίκτυο.[17]
Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]
- ↑ Elisabeth Wong, Brittany Baur, Saad Quader and Chun-Hsi Huang. «Biological network motif detection:principles and practice». Briefing in Bioinformatics.
- ↑ «Analysis of Biological Networks:Network motifs» (PDF).
- ↑ Shen-Orr SS, Milo R, Mangan S, Alon U (2002). «Network motifs in the transcriptional regulation network of Escherichia coli». Nature Genetics 31 (1): 64-68. doi:.
- ↑ Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U (2004). «Superfamilies of designed and evolved networks». Science 303 (5663): 1538-1542. doi:.
- ↑ Babu MM, Luscombe NM, Aravind L, Gerstein M, Teichmann SA (2004). «Structure and evolution of transcriptional regulatory networks». Current Opinion in Structural Biology 14 (3): 283-291. doi:.
- ↑ Conant GC, Wagner A (2003). «Convergent evolution of gene circuits». Nature Genetics 34 (3): 264-266. doi:.
- ↑ 7,0 7,1 7,2 7,3 7,4 Uri Alon (2007). «Network motifs:theory and experimental approaches». Nature Genetics 8: 450-461.
- ↑ N. Kashtan, S. Itzkovitz, R. Milo and U. Alon (2004). «Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs». Bioinformatics 20 (11): 1746-1758. doi:.
- ↑ Milo R, Shen-Orr SS, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002). «Network motifs:simple building blocks of complex networks». Science 298 (5594): 824-827. doi:.
- ↑ Schreiber F, Schwobbermeyer Η (2005). «MAVisto: a tool for the exploration of network motifs». Bioinformatics 21 (17): 3572-3574. doi:.
- ↑ Kashtan N, Itzkovitz S, Milo R, Alon U (2004). «Efficient sampling algorithm for estimating sub-graph concentrations and detecting network motifs». Bioinformatics 20 (11): 1746-1758. doi:.
- ↑ Chen J, Hsu W, Li Lee M (2006). «NeMoFinder: dissecting genome-wide protein-protein interactions with meso-scale network motifs». the 12th ACM SIGKDD international conference on Knowledge discovery and data mining: 106-115. doi:.
- ↑ Grochow JA, Kellis M (2007). Network Motif Discovery Using Sub-graph Enumeration and Symmetry-Breaking, σελ. 92-106. doi:.
- ↑ Alon N, Dao P, Hajirasouliha I, Hormozdiari F, Sahinalp S.C (2008). «Biomolecular network motif counting and discovery by color coding». Bioinformatics 24: 241-249.
- ↑ Omidi S, Schreiber F, Masoudi-Nejad A (2009). «MODA: an efficient algorithm for network motif discovery in biological networks». Genes Genet Syst 84 (5): 385-395. doi:.
- ↑ Kashani ZR, Ahrabian H, Elahi E, Nowzari-Dalini A, Ansari ES, Asadi S, Mohammadi S, Schreiber F, Masoudi-Nejad A (2009). «Kavosh: a new algorithm for finding network motifs». Bioinformatics 10 (318). doi:.
- ↑ Ribeiro P, Silva F. «G-Tries: an efficient data structure for discovering network motifs"». ACM 25th Symposium On Applied Computing - Bioinformatics Track: 1559-1566.