Recent achievements in biological experiment methods allow us to deal with a genomescale biological data. In many cases, these large-scale biological data from high-throughput experimental methods can be represented as graphs. The goal of an emerging field in biology, or systems biology, is to analyze, to extract knowledge for and to get an insight about biological systems from the analyses of these high-throughput experimental data.
An example of such data can be found in case of protein interaction networks, whose nodes denote proteins and edges denote protein interactions. Since protein interactions are closely related to involved biological processes of the proteins, several biological problems on proteins, such as the protein function annotation problem, have successfully been addressed with respect to protein interaction networks. It is expected that more detailed investigations on these networks will help us to understand biological systems better.
One of the methods that extract key features from a large-scale network is the recently proposed network motif analysis. Here we get a set of subgraphs which appear more frequently in the real network than in randomized networks. These subgraphs retain the characteristics of the original network. It was proven to be useful in analyzing biological networks such as protein interaction networks or gene regulation networks. However, it has been applied only to an unlabeled graph. In this thesis, we extend the idea of network motif to a labeled graph which works as a more powerful and informative representation than an unlabeled graph. In this extension, what is important is the randomized network model: If we use a degree invariant model for labeled graphs directly, node characteristics may vary and hence undesirable results can be obtained. We overcome this problem by generalizing the degree invariant model to a label specific degree invariant model.
The proposed network motif analysis method for labeled graphs is then applied to a protein and domain interaction network for the analysis of protein complexes. By integrating interaction information from the protein layer and the domain layer, we have built a Protein and Domain Interaction Network (PaDIN) based on a layered graph model. The advantages of the model is that we can easily observe domain aspects of protein interactions. The model has been applied to human and yeast protein interaction networks separately to see the patterns of protein complex architecture. For the analysis, we searched for network motifs corresponding to protein complex architectures using a subgraph mining algorithm based on a connectivity constraint. The related statistics shows that important characteristics of the complex architecture are conserved across species.
In a PaDIN, we can observe structural characteristics of interacting proteins since their domain information is represented as edges between a protein and a domain. This leads us to address another biological problem which is known as the protein interaction map alignment problem. The goal of protein interaction map alignment is to find conserved features from protein interaction maps of different species. It is known that a biological function often involves a set of interacting proteins and a function conserved across species usually involves structurally similar proteins. Therefore, the hypothesis is that if there is a functional feature conserved across species, it will appear in the protein interaction maps in the form of interactions of structurally similar proteins.
In the thesis, we present a protein interaction map alignment algorithm to find pairs of interacting protein sets of structurally similar proteins from different species. The proposed method has the following two advantages compared with previous methods. 1) It is based on domain information so that it only considers highly conserved sequences of proteins and 2) it finds conserved functional modules that have various topological structures in protein interaction networks. The algorithm has been applied to protein protein interaction networks to show that it can find functional modules conserved across species by investigating the functional similarity between aligned protein interaction maps. In particular, when we explore a new or less known species and we have domain assignment information and protein interaction data, we can find functional features of the species that are similar to those of the well-known species by aligning its protein interaction map with the known one. It is also shown that the proposed method can be used in either a functional annotation problem or a protein interaction prediction problem.
최근 대단위 실험기법의 개발로 우리는 하나의 생명체 내에 존재하는 생물학적 단위 전체에 대한 실험결과를 가질 수 있게 되었다. 최근 각광받는 생물학 분야인 시스템 생물학에서는 이러한 대단위 실험데이터를 분석하고 그로부터 유용한 정보를 뽑아내고 생명 시스템 전체에 대한 이해를 돕는 것을 그 목적으로 한다.
이러한 실험데이터들은 많은 경우에 있어 그래프 형태로 나타내어진다. 이렇게 나타내어진 대단위 그래프를 분석하는 방법론중 대표적인 것으로 최근 제안된 네트워크 모티프 분석 방법이 있다. 여기서 우리는 무작위 네트워크에서보다 실제 네트워크에서 더 많이 존재하는 부그래프들을 찾는다. 이 부그래프들은 원래 그래프의 구조적인 특징을 나타낼 수 있다. 이러한 방법은 단백질 상호작용 네트워크나 유전자 조절 네트워크등 여러가지 생물학적 네트워크를 분석하는데에 유용하다고 알려져 있다. 그러나 현재까지 이러한 방법론은 레이블 없는 그래프에만 적용되어 왔다. 본 논문에서는 이러한 네트워크 모티프의 개념을 레이블 있는 그래프로 확장한다. 이 확장에서 문제가 되는 것은 기존의 무작위 네트워크 모델을 사용하면 바람직하지 않은 결과가 나올 수 있다는 것이다. 우리는 이 문제를 기존의 무작위 네트워크 모델을 일반화함으로써 해결한다.
네트워크 모티프를 찾는 문제는 일종의 부그래프 발견 문제인데, 이 문제는 최근 몇년간 많은 관심을 받고 있다. 이 문제는 입력 그래프의 형태와 찾고자 하는 부그래프의 형태에 따라 여러 가지 분류로 나뉘어지는데 네트워크 모티프를 찾는 문제에 있어서는 트리구조에는 그다지 중요한 정보가 들어있지 않을 가능성이 크다는 것이 알려져 있다. 본 논문에서는 이 부분에 착안하여 부그래프 분석을 하는 데 있어서 트리구조는 고려하지 않음으로써 속도를 향상시키는 알고리즘을 제안한다.
제안된 레이블 있는 그래프에서의 네트워크 모티프 분석방법을 단백질과 도메인 상호작용 네트워크에 적용함으로써 단백질 복합물들의 특징을 분석한다. 단백질 상호작용 정보와 도메인 상호작용 정보를 계층 그래프를 이용하여 하나로 병합하여 단백질과 도메인 상호작용 네트워크를 만든다. 제안된 모델은 단백질 복합물의 도메인 조성 구조를 쉽게 알아볼 수 있다는 장점을 가지고 있다. 제안된 모델은 사람과 효모의 단백질 상호작용 네트워크에 각각 적용되었고 그 결과 우리는 단백질 복합물에 대응하는 네트워크 모티프들을 찾을 수 있었다. 통계적 분석을 통하여 서로 다른 종 간에서도 단백질 복합물의 성격은 많이 변하지 않음을 확인하였다.
또한 단백질과 도메인 상호작용 네트워크에 존재하는 도메인 정보를 이용해서 서로 다른 두 개의 단백질 상호작용 네트워크로부터 공통된 기능을 가질 것으로 생각되는 부분을 추출하는 방법을 제안하였다. 제안된 방법에 의해 추출된 단백질 상호작용 네트워크는 서로 유사한 기능을 가지고 있음을 확인하였다.
