Recently, efficient search methods are increasingly required for finding large network structures in various applications. Especially in the field of computational biology, several approaches have been studied to infer the relationships between biological entities via network-shaped models such as Bayesian networks. However, the number of considered entities is very large in general. Such large number of entities, i.e., the number of nodes in network models, make it difficult to find target network structures because the search space is super exponential to the number of nodes.
To handle such large problems, there have been several approaches to restrict the search space by restricting local network structures around each node. However, such local structure restriction approaches have limitation on their scalability.
In this research, a new approach is proposed to restrict the search space of learning Bayesian network structures. We assume that the target network structure has a characteristic of ‘the network of sub-networks’. By clustering variables, which correspond to the nodes in networks, and estimating directionality of edges between those clusters, we restrict the global structure of target Bayesian networks. Through this global structure restriction approach, target Bayesian networks can be learned in much more reduced time without significant loss of accuracy.
An application of using the proposed method is also presented for high-throughput biological data. In the field of computational biology, relationships have been inferred between biological entities using the Bayesian network model with high-throughput data from biological systems. However, most previous approaches limit the number of target entities or use additional knowledge to handle genome-scale problems. The proposed method can efficiently handle such large scale problems without limiting target entities or using additional knowledge.
베이지안 망은 확률변수들 사이의 조건부 화률적 의존성을 표현하기 위한 망 형태의 모델이다. 이러한 베이지안 망은 그 기반 연구가 수학적으로 충분히 이루어져 있으며, 확률적 모델을 표현하는 데에 적합한 이유로 생물학과 같은 분야에서 최근 널리 사용되어지고 있다. 그러나 대부분의 생물학 분야의 문제는 다루고자 하는 문제의 크기가 매우 큰 관계로 기존의 일반적인 베이지안 망 학습 방법을 적용하기에 어려운 점이 있다. 이 점을 극복하기 위해, 본 연구에서는 보다 효율적으로 대규모의 베이지안 망을 학습하기 위한 탐색 공간의 제한 기법을 제안하였다.
제안된 방법은 베이지안 구조에 해당하는 망 구조의 고려 대상 수를 줄이기 위해, 노드를 클러스터링하고 클러스터들 사이에서의 edge의 방향성을 제한하는 방법을 사용한다. 클러스터링에서는 그래프 분할 방법을 이용한 클러스터링을 수행하며, 클러스터 사이에서의 edge 방향성 결정은 각 클러스터 쌍에서 서로 가장 가까운 두 노드를 사용한 베이지안 구조 학습 방법을 통해 결정한다. 이러한 방법을 통해, cycle이 고려되는 그래프 구조 탐색 공간을 전체 노드 수에 대한 오더에서 최대 클러스터 크기에 대한 오더로 줄이는 것이 가능하다.
제안된 방법의 평가를 위하여, 기존의 sparse candidate 방법과의 비교를 여러 개의 평가용 베이지안 망을 이용하여 수행하였다. 비교 실험 결과, 제안된 방법은 기존의 방법에 비해 훨씬 짧은 시간 이내에 유사한 만족도를 보이는 결과를 학습하는 것이 가능함을 알 수 있다. 또한 제안된 방법을, 기존의 방법으로 베이지안 망 분석이 불가능하였던 수천 개 유전자 실험 데이터에 대해 적용하였으며, 그 결과 기존의 방법으로는 찾을 수 없었던 유의미한 결과를 얻을 수 있음을 발견하였다.
