Hierarchical classification of directed graph with cyclically equivalent nodes

5^th International Conference on Biometrics & Biostatistics

October 20-21, 2016 Houston, USA

G Sh Tsitsiashvili

Far Eastern Federal University, Russia

Posters & Accepted Abstracts: J Biom Biostat

Abstract :

In this paper, an algorithm of a hierarchical classification of a directed graph with cyclically equivalent nodes is constructed. An example of this algorithm application to an analysis of secondary metabolism sub-network in protein network of Arabidopsis is represented. Suggested algorithm is based on a relation of cyclic equivalence of nodes pair in directed graph (an existence of a cycle containing a pair of nodes in directed graph) and a relation of partial order between classes of cyclic equivalence (an existence of a way between nodes from different classes of cyclic equivalence). A sequential algorithm of graph nodes classification and their partial order definition is suggested. This algorithm occurred very fast and allowed to find a core- an equivalence class with 958 nodes in Arabidopsis protein network with 2824 nodes. An algorithm of hierarchical classification of undirected graph nodes by similarity matrix is constructed. This approach gives single solution of classification problem. Each hierarchical level is defined by some critical value of a similarity. Using critical value the similarity matrix is transformed into contiguity matrix of some undirected graph in which connectivity components are constructed. Increasing successfully critical values, it is possible to define hierarchical classification of initial objects. This algorithm is applied for hierarchical classification of species of a plant by presence of some matters in them. An algorithm of hierarchical classification of directed graph nodes is based on a concept of minimal length of cycles passing through a pair of nodes. Using well known Floyd�Warshall algorithm, it is possible to calculate matrix of cycles minimal length and then to apply to this matrix previous algorithm. This algorithm is applied to secondary metabolism protein network of Arabidopsis.

Biography :

G Sh Tsitsiashvili finished the Moscow Physical and Technical Institute in 1972 (the faculty of Control and Applied Mathematics) and started working in Mathematical Department of Far Eastern Branch of Russian Academy Sciences in Vladivostok. In 1976, he protected candidate thesis and in 1992 doctor thesis. His researches are devoted to different problems in applied probability, mainly to synergetic effects in stochastic systems: queuing, reliability, risk and data processing in different areas: mining, meteorology, parasitology and infection diseases, demography, biochemistry. He is the author/co-author of approximately 500 scientific articles and 10 monographs. Currently, he is the General Scientific Collaborator of Institute for Applied Mathematics, Far Eastern Branch of RAS and the Professor of Far Eastern State University.

Email: guram@iam.dvo.ru