Factorization of oriented graph nodes and application to protein networks

Journal of Applied & Computational Mathematics

ISSN: 2168-9679

Open Access

Factorization of oriented graph nodes and application to protein networks

4th International Conference and Exhibition on Biometrics & Biostatistics

November 16-18, 2015 San Antonio, USA

Tsitsiashvili G Sh, Losev A S, Osipova M A and Kharchenko Yu N

Institute for Applied Mathematics FEB RAS, Russia

Posters-Accepted Abstracts: J Appl Computat Math

Abstract :

In this paper, we consider oriented graph with finite sets of nodes and edges. Such graphs appear in a description of protein networks. These graphs may be factorized by the cyclic equivalence and the partial order between equivalence classes may be introduced. A direct way to realize this procedure is the Boolean multiplication of the graph contiguity matrix, but such approach is too complicated. So, we construct a sequential algorithm of an oriented graph factorization with a square number of arithmetical operations by a number of graph nodes. A decrease of the calculation complexity is connected with an introduction of a partial order matrix which is defined recursively by assignment operations. To test suggested factorization algorithm, we consider the protein network Arabidopsis with 2824 nodes and 7500 edges. Using sufficiently powerful server, it is possible to realize the factorization procedure by the calculation of the matrixes during 21 days. Using the sequential algorithm, it is possible to fulfill the factorization procedure on a notebook during one and half hours. An analysis of a distribution of equivalence classes by numbers of their nodes shows that there is the equivalence class (a kernel) with 958 nodes which composes approximately 34 percent of all network vertices.

Biography :

Tsitsiashvili G Sh has completed his Doctorate thesis on physical and mathematical sciences. He is the Head of IAM FEB RAS laboratory on probability methods and systems analysis and has published more than 100 papers in reputed journals. The main sphere of his researches is applied probability models: queuing, reliability, insurance, epidemic, etc.


Google Scholar citation report
Citations: 1282

Journal of Applied & Computational Mathematics received 1282 citations as per Google Scholar report

Journal of Applied & Computational Mathematics peer review process verified at publons

Indexed In

arrow_upward arrow_upward