# findMST2.PPI: Union of the First and Second Minimum Spanning Trees for PPI... In GSAR: Gene Set Analysis in R

## Description

Find the union of the first and second minimum spanning trees for protein-protein interaction (PPI) networks.

## Usage

 1 findMST2.PPI(object, return.MST2only=TRUE) 

## Arguments

 object an object of class igraph representing the PPI network. return.MST2only logical. If TRUE (default), an object of class igraph containing the MST2 is returned. If FALSE, a list of length three containing objects of class igraph is returned. The first and second objects are the first and second MSTs, respectively. The third is the union of the first and second, MST2.

## Details

This function produces the union of the first and second minimum spanning trees (MSTs) as an igraph object (check package igraph for details). It can as well return the first and second minimum spanning trees when return.MST2only is FALSE.

For the graph G(V,E) where V is the set of vertices and E is the set of edges, the first MST is defined as the acyclic subset T_{1} \subseteq E that connects all vertices in V and whose total length ∑_{i,j \in T_{1}} d(v_{i},v_{j}) is minimal (Rahmatallah et. al. 2014). The second MST is defined as the MST of the reduced graph G(V,E-T_{1}). The union of the first and second MSTs is denoted as MST2.

It was shown in Zybailov et. al. 2016 that MST2 can be informative as a graphical visualization tool in deciphering the properties of protein-protein interaction (PPI) networks by highlighting the minimum set of essential interactions among proteins. Most influential proteins with many interactions tend to occupy central position and have relatively high connectivity degree in the MST2 because the shortest paths connecting the vertices of the first and second MSTs tend to pass through the verteces corresponding to these proteins. In contrast, proteins with few interactions most likely occupy non-central positions in the MST2 and have a degree of 2.

## Value

If return.MST2only=TRUE (default), function findMST2.PPI returns an object of class igraph representing the MST2. If return.MST2only=FALSE, function findMST2.PPI returns a list of length 3 with the following components:

 MST2 an object of class igraph containing the union of the first and second MSTs. first.mst an object of class igraph containing the first MST. second.mst an object of class igraph containing the second MST.

## Author(s)

Yasir Rahmatallah and Galina Glazko

## References

Zybailov B., Byrd A., Glazko G., Rahmatallah Y. and Raney K. (2016) Protein-protein interaction analysis for functional characterization of helicases. Methods, 108, 56–64.

GSNCAtest, plotMST2.pathway.
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 ## generate a random undirected graph with power-law ## distribution degree where minimum degree is 4 and ## maximum degree is 100 set.seed(123) degs <- sample(c(4:100), 100, replace=TRUE, prob=c(4:100)^-2) if(floor(sum(degs)/2) != (sum(degs)/2)) degs[1] <- degs[1] + 1 randomGraph <- sample_degseq(degs, method="vl") ## find MST2 of the random graph and highlight vertices ## with degree greater than 10 with red color mst2.ppi <- findMST2.PPI(object=randomGraph, return.MST2only=TRUE) degs <- degree(mst2.ppi) ind <- which(degs > 10) V(mst2.ppi)$color <- "yellow" V(mst2.ppi)$color[ind] <- "red"