Abstract—An evolutionary network (EN) in formatted
protein sequence space is a very large graph representing
information about sequence similarity of relatively short
protein fragments. This graph can be used for detecting hidden
relatedness between proteins, which is highly significant in
protein annotation. Effective EN analysis requires an
appropriate graph clustering approach. Based on the fact that
biological relatedness is strongly dependent on the number of
independent graph nodes connections, we develop a network
clustering method that is capable to produce quality clusters the
members of which have a satisfactory level of relatedness.
In this article we describe a new network partitioning
method which is based on the k-cycles graph connectivity
approach. After formally defining a unique structure, named
k-ladder connectivity, we demonstrate that the k-ladder-based
algorithm is able to successfully detect the groups of
functionally related proteins.
To exhibit the quality of the method, we have conducted a set
of experiments in which it has been very effective in clustering
of EN, as well as the significantly denser protein-protein
interaction networks (PPINs). Furthermore, it can be simply
adapted for more complicated structures than cycles, as well as
applied to other large networks of different types.
Index Terms—K-ladder, connectivity algorithm, network
clustering, protein evolutionary network, formatted protein
sequence space, protein-protein interaction networks.
The authors are with the ORT Braude College of Engineering, Karmiel,
Israel and Research Fellow at Institute of Evolution, University of Haifa,
Israel (e-mail: reshma.iidsalld2007@gmail.com, asoffer@braude.ac.il and
ahumu@yahoo.com, vlvolkov@braude.ac.il, zakharf@research.haifa.ac.il).
[PDF]
Cite: Reshma Nibhani, Avi Soffer, Ahuva Mu'alem, Zeev Volkovich, and Zakharia Frenkel, "Application of a K-Ladder Connectivity Algorithm for
Clustering of Protein Evolutionary Network," International Journal of Modeling and Optimization vol. 4, no. 5, pp. 367-374, 2014.