Bakgrund: I regelbaserad modellering, grafer används för att representera molekyler: en färgad vertex representerar en komponent i en molekyl, ett vertex attribut representerar det interna tillståndet för en komponent, och en kant representerar ett band mellan komponenter. Komponenter i en molekyl delar samma färg. Dessutom används grafskrivande regler för att representera molekylära interaktioner. En regel som anger addition (borttagande) av en kant representerar en klass av associationsreaktioner (dissociation) och en regel som anger en ändring av ett vertex-attribut representerar en klass av reaktioner som påverkar det inre tillståndet hos en molekylär komponent. En uppsättning regler består av en körbar modell som kan användas för att på olika sätt bestämma dynamiken på systemnivå av molekylära interaktioner i ett biokemiskt system. Resultat: För modellanmärkning föreslår vi att hierarkiska grafer används för att representera strukturella relationer mellan komponenter och delkomponenter av molekyler. Vi illustrerar hur hierarkiska grafer kan användas för att naturligt dokumentera den strukturella organisationen av de funktionella komponenterna och delkomponenterna av två proteiner: proteinet tyrosinkinas Lck och Tcellreceptorn (TCR) komplexet. Vi visar också att beräkningsmetoder som utvecklats för regelbundna grafer kan tillämpas på hierarkiska grafer. I synnerhet beskriver vi en generalisering av Nauty, en graf isomorfism och kanonisk märkalgoritm. Den generaliserade versionen av Nauty-proceduren, som vi kallar HNauty, kan användas för att tilldela kanoniska etiketter till hierarkiska grafer eller mer allmänt till grafer med flera kanttyper. Skillnaden mellan Nauty- och HNauty-procedurerna är liten, men för fullständighetens skull ger vi en förklaring till hela HNauty-algoritmen. Slutsatser: Hierarkiska grafer ger mer intuitiva formella representationer av proteiner och andra strukturerade molekyler med flera funktionella komponenter än de vanliga grafer av aktuella språk för att specificera regelbaserade modeller, såsom BioNetGen språk (BNGL). Den föreslagna användningen av hierarkiska diagram bör därför främja tydlighet och bättre förståelse för regelbaserade modeller.
I detta sammanhang, en generaliserad graf isomorfism och märkning algoritm som HNauty REF kan vara av särskild betydelse.
Hierarchical graphs for rule-based modeling of biochemical systems
{'venue': 'BMC Bioinformatics', 'journal': 'BMC Bioinformatics', 'mag_field_of_study': ['Computer Science', 'Medicine']}