Date of Award

Spring 5-2013

Degree Type

Masters Thesis

Degree Name

Master of Science (MS)

Department

Computing

Committee Chair

Jonathan Sun

Committee Chair Department

Computing

Committee Member 2

Chaoyang Zhang

Committee Member 2 Department

Computing

Committee Member 3

Shaoen Wu

Committee Member 3 Department

Computing

Abstract

A large number of experimental biological network data of different types are becoming available due to advanced experimental techniques. Network alignment is considered to be one of the most common methods to analyze and compare biological networks to understand evolution, biological mechanisms, and the complexity of diseases. Kuchaiev, Milenkovic, Memisevic, Hayes, & Przulj (2010) recently proposed a topological method of network alignment based on graphlet degree signatures, called GRAAL, which can be used to align any kind of networks not just biological ones. Several global network alignment algorithms also have been designed based on GRAAL, such as MI-GRAAL, H-GRAAL, and C-GRAAL. However, the alignment of large networks necessitates the improvement of GRAAL algorithm in terms of both accuracy and computational efficiency.

In this paper, I present three kinds of modifications based on GRAAL, including modification on P value, modification on graphlet selection and modification on vector calculation. I applied the three modifications on several biological datasets. The results have shown that these modifications perform comparable to GRAAL, and the algorithm efficiency can be improved up to 90% without losing much accuracy.

Download

Share

COinS