Clustering-coefficient- artificial intelligence, Computer Engineering

Assignment Help:

This programming assignment is about computing topological properties of Protein-Protein Interaction (PPI) networks. Recall that a PPI network is represented by a graph G=(V,E) where  nodes of V represent  proteins and an edge of E connecting  two nodes represents interacting proteins (either physically or functionally).  The properties include clustering coefficient and node centrality.  A detailed description of these properties  follows:

 Clustering coefficient

In many networks, if node u is connected to v, and v is connected to w, then it is highly probable that u also has a direct link to w. This phenomenon can be quantified using the clustering coefficient

Cu = 2nu/ ku  (ku  -1)

where nu is the number of edges connecting the ku  neighbors of node u to each other. In other words, Cu gives the number of 'triangles' that go through node i, whereas ku(ku -1)/2 is the total number of triangles that could pass through node u, should all of node u's neighbors be connected to each other.

The average clustering coefficient,<C>, characterizes the overall tendency of nodes to form clusters or groups. An important measure of the network's structure is the function C(h),which is defined as the average clustering coefficient of all nodes of degree h, i.e. with h adjacent vertices.

Closeness centrality of a node

Closeness-centrality is a measure of node centrality and uses information about the length of the shortest paths within a network; it uses the sum of the shortest distances of a node to all other nodes. The closeness-centrality of node u is defined as the reciprocal of this sum:

Cclo(u) = 1/(Σv∈V dist (u , v)).

Implementation

Write 5 subroutines:

1.    Clustering-Coefficient

2.    All-Pairs-Shortest-Paths

3.    Create-Adjacency-Matrix

4.    Node-Centrality

5.    Get-Shortest-Paths 

The subroutine Clutering-Coefficient outputs 1) the average clustering coefficient <C>, 2) C(H), for all H values, and 3) the top 5 nodes (proteins) with highest cluster coefficient. The protein ids should be those used in the .sif file.

The procedure Create-Adjacency-Matrix takes as input argument the .sif representation of a graph and generates the adjacency matrix representation of the graph. It uses hashes (as defined in perl)  to map the protein ids into indexes of the adjacency matrix. 

The procedure All-Pairs-Shortest-Paths has as input argument the adjacency matrix representation of a graph. The subroutine returns a two-dimensional matrix, A, with A[i,j]  giving the length of the shortest path between nodes i and j.

 The subroutine Node-Centrality outputs the top 5 nodes according to the centrality measure, that is the 5 proteins that are most central. The protein ids should be those used in the .sif file.

 The subroutine Get-Shortest-Path takes in input a pair of nodes and the adjacency matrix representation of a graph and returns a shortest path  between the two nodes.  Call this subroutine from the main using as input parameters the two nodes with highest value of node-centrality.

 Data

In this assignment you analyze the Protein-Protein Interaction (PPI) graph of the herpes Kaposi virus. The file kshv.cys (available at t-square, Resources) contains such a graph in cytoscape format.

You select the subgraph of this network consisting of the nodes with degree equal or less than k,(k=7).

This will be the input to your perl program Properties-PPI-Networks.pl that calls the subroutines described above.

Electronically submit the following:

a.     the file Properties-PPI-Networks.pl containing the main program and all subroutines. 

b.    A document where you state the time complexity of each subroutine  as a function of the number of nodes and/or edges and explain how you obtained it.

 


Related Discussions:- Clustering-coefficient- artificial intelligence

Example on sorting using combinational circuit, Q. Example on Sorting using...

Q. Example on Sorting using Combinational Circuit? Example: Think about a unsorted list having element values like given below {3,9,8,5,10,12,14,20,90,95,60,40,23,35,18,0}

What are the steps in executing the program, What are the steps in executin...

What are the steps in executing the program? 1.Fetch 2.Decode 3.Execute 4.Store

Advantage to depth first search, Advantage to depth first search: It j...

Advantage to depth first search: It just looks like it will be a long period it finds 'DAN' until. This highlights an important drawback for depth first search. It can regular

Stencil duplicating, Stencil Duplicating Equipment Required Stenci...

Stencil Duplicating Equipment Required Stencil Duplicator Thermal copier (optional) Electronic stencil cutter Materials Stencil COPY paper Ink Clean

What is a shell, What is a shell? A shell is an interactive user interf...

What is a shell? A shell is an interactive user interface to an operating system services that permits an user to enter commands as character strings or by a graphical user int

What is difference between cgi and java, CGI and JAVA are fundamentally dis...

CGI and JAVA are fundamentally dissimilar, and for most applications are NOT interchangable. CGI is a protocol for running programs on a WWW server. Whilst JAVA can also be us

Is the data bus is bi-directional, The data bus is Bi-directional because t...

The data bus is Bi-directional because the similar bus is used for transfer of data among Micro Processor and memory or input / output devices in both the direction.

Learning algorithm for multi-layered networks, Learning algorithm for multi...

Learning algorithm for multi-layered networks: Furthermore details we see that  if S is too high, the contribution from w i * x i is reduced. It means that t(E) - o(E) is mu

Define the edge-triggered flip-flops, Define the Edge-Triggered Flip-flops?...

Define the Edge-Triggered Flip-flops? An edge-triggered flip-flop changes states either at the negative edge (falling edge) or at the positive edge (rising edge) of the clock p

Define cache memory, Define cache memory? A special very high speed mem...

Define cache memory? A special very high speed memory known as a cache is sometimes used to increase the speed of processing by making current programs and data available to th

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd