Με την πάροδο των χρόνων, η βάση δεδομένων KEGG έχει καταλήξει να είναι μία από τις μεγαλύτερες σε περιεχόμενο βάσεις δεδομένων διεθνώς όσον αφορά βιολογικές διαδικασίες. Το μεγαλύτερο μέρος των δεδομένων που περιλαμβάνει είναι στη μορφή μονοπατιών (pathways) τα οποία είναι γράφοι που απεικονίζουν τις σχέσεις μεταξύ μιας πληθώρας κατηγοριών αντικειμένων όπως γονίδια και χημικές ουσίες. Το μέγεθος, η πολυπλοκότητα και η ποικιλία, όμως, των γράφων αυτών καθιστά δύσκολο το να εξερευνηθούν και να γίνουν κατανοητοί όπως και το να εξαχθεί ένα ξεκάθαρο συμπέρασμα σχετικά με σημαντικότερα μέρη τους. Κινούμενοι προς αυτή την κατεύθυνση, σε αυτή την εργασία παρουσιάζουμε τον KEGGSum, ένα σύστημα με τους αντίστοιχους αλγόριθμους που υποστηρίζουν την υψηλής αποδοτικότητας και αποτελεσματικότητας περίληψη μονοπατιών της KEGG. Ο KEGGSum δέχεται το KEGG Identifier (kid) ενός μονοπατιού της KEGG, λαμβάνει από τη βάση δεδομένων μια ειδικά προσαρμοσμένη μορφή του και αναγνωρίζει τους σημαντικότερους κόμβους κάνοντας χρήση ενός εξειδικευμένου αρθρώματος (module) υπολογισμών. Σε αυτή την εργασία, για την αποτελεσματικότερη αναγνώριση των πιο σημαντικών κόμβων σε γράφους της KEGG, εντοπίσαμε και εξερευνήσαμε πολλά από τα μέτρα κεντρικότητας που έχουν προταθεί στη βιβλιογραφία ως κατάλληλα για γενικούς γράφους, υποδεικνύοντας ταυτόχρονα και την δυνατότητα εφαρμογής τους σε γράφους της KEGG. Συνεχίζοντας, ο KEGGSum δεν σταματάει στην αναγνώριση των σημαντικότερων κόμβων αλλά τους ενώνει δημιουργώντας έτσι έναν περιληπτικό γράφο (summary graph) του αρχικού γράφου της KEGG. Τέλος, το σύστημά μας οπτικοποιεί την δημιουργηθείσα περίληψη του προηγούμενου σταδίου διευκολύνοντας την κατανόηση των σημαντικότερων μερών του αρχικού γράφου. Στα τελευταία τμήματα της εργασίας, παρουσιάζεται η πειραματική αξιολόγηση του συστήματός μας καθώς και τα πλεονεκτήματα και τα οφέλη που προσφέρει.
Over time, the renowned KEGG database has grown to become one of the most comprehensive online databases for biological procedures. The majority of the data is stored in the form of pathways, which are graphs that depict the relationships between the diverse items participating in biological procedures such as genes and chemical compounds. However, the size, the complexity and the diversity of those graphs make them difficult to be explored and understood, as well as to extract a clear conclusion regarding their most important components. To this direction, in this work we present KEGGSum, a system and the corresponding algorithms enabling efficient and effective summarization of KEGG pathways. The KEGGSum system takes the KEGG Identifier (kid) of a KEGG pathway as input, connects to the KEGG database, downloads a specialized form of the pathway, and determines the most important nodes of the graph using a specific module of computations. To identify the most important nodes in the KEGG graphs, in this work, we explore multiple centrality measures that have been proposed for generic graphs showing their applicability for KEGG graphs as well. We do not stop in just identifying the most important nodes but we also link the selected nodes in order to produce a summary graph out of the initial KEGG graph. Finally, our system visualizes the generated summary enabling the understanding of the most important parts of the initial graph. We experimentally evaluate our system and we show its advantages and benefits.
KEGGSum: a biological procedures summarization algorithm