Boolean modeling has been widely used to model biological systems lacking detailed kinetic information. Despite their simplicity, Boolean models can still capture some important features of biological systems such as steady states (i.e., attractors) and basins of attraction (i.e., basins). Thus, finding attractors and their basins are important problem in systems biology research. In Boolean modeling, an attractor is a set of states where state transitions converge, and basins to an attractor are a set of states that eventually converge to the attractor. Thus, in order to find attractors and basins, Boolean simulation must go through several state transitions. In the middle of simulation, however, a search space explosion may occur, and this greatly degrades the performance of simulation.
There are three main causes for a search space explosion: 1) explosively increasing state transitions with the number of initial states, 2) explosively increasing state transitions with the number of successor states and the length of state transitions, 3) explosively increasing duplicated searches of states in the middle of simulation. To tackle such a search space explosion, many approaches have been proposed in the past decade, but there is no generic method that can efficiently find every attractor and basin for large Boolean models so far. Recently, partition-based methods have been received wide attention since they can be orthogonally applied to other approaches. We thus concentrate on improving partition-based methods in this dissertation. Particularly, this dissertation addresses the major research question of partition-based methods: what is the best partition for minimizing explosive state transitions to efficiently detect attractors and basins?
In this dissertation, we claim that in order to alleviate explosive state transitions occurred in the middle of identifying attractors and basins of a Boolean model, total state transitions must be partitioned to minimize 1) the number of initial states, 2) the length of state transitions, and 3) duplicated searches of states. We propose partition-based algorithms for finding attractors and basins of a Boolean model. To analyze attractors for Boolean models with a single successor, we propose a novel scheme that partitions original network to several subnetworks so as subnetworks to have smaller number of initial states than the total initial states. In Boolean models with several successors, state transitions exponentially increase as a length of state transitions to an attractor increases. Thus, we divide long state transitions to a series of short state transitions. For basin analysis, we partition total search space based on attractors in a way to minimize duplicated searches of states. We show that the proposed partition-based approaches for finding attractors and basins mitigate a search space explosion by pruning a large amount of state transitions.
이진 모델링은 동역학 정보가 아직 상세하게 밝혀지지 않은 생체시스템을 모델링하는데 유용한 기법이다. 이 기법은 복잡한 생체시스템을 간단하게 모델링함에도 불구하고 시스템의 정상상태(끌개), 정상상태로 수렴하는 영역(끌개의 수렴공간) 등과 같은 생체시스템의 중요한 특성 등을 반영할 수 있다. 그러므로 이진 모델의 끌개와 끌개의 수렴공간을 분석하는 것은 시스템 생물학 연구에서 매우 중요한 문제이다. 이진 모델링에서 끌개와 끌개의 수렴공간은 각각 상태전이가 최종적으로 수렴하는 상태와 해당 끌개로 수렴하는 모든 초기상태의 집합으로 정의된다. 따라서 이진 모델의 끌개와 끌개의 수렴공간을 분석하기 위해 이진 시뮬레이션에서는 여러 번의 상태전이가 요구된다. 하지만 시뮬레이션 과정에서 상태전이의 수가 폭발적으로 증가할 수 있으며, 이는 시뮬레이션의 성능을 크게 저하시킨다.
상태전이 폭발 문제의 주 요인은 크게 세가지로 분류할 수 있다: 1) 초기상태의 수에 따라 폭발적으로 증가하는 상태전이, 2) 후임상태의 개수와 상태전이 길이에 따라 폭발적으로 증가하는 상태전이, 3) 시뮬레이션 과정에서 폭발적으로 증가하는 중복된 상태탐색. 이러한 상태전이 폭발 문제를 해결하기 위해 지난 십수년간 많은 기법들이 제안되어 왔지만, 아직 이 문제를 근본적으로 해결한 기법은 없는 상황이다. 최근 들어 파티션 기반의 방법이 주목을 받고 있는데, 왜냐하면 이 방법은 다른 기법들에 독립적으로 적용될 수 있기 때문이다. 따라서 우리는 이 논문에서 파티션 기반 방법의 성능을 높이는 데 주력한다. 특히, 이 논문은 파티션 기반 방법의 근본적인 질문에 해답을 제시한다. 질문은 다음과 같다: 끌개와 끌개의 수렴공간을 가장 효율적으로 분석하기 위한 상태전이 폭발을 최소화하는 최적의 파티션은 무엇인가?
이 논문에서 우리는 끌개와 끌개의 수렴공간을 찾는 과정에서 발생하는 상태전이 폭발 문제를 해결하기 위해 전체 상태전이 공간은 1) 초기상태의 수, 2) 상태전이의 길이, 3) 중복된 상태탐색을 최소화하는 것을 목표로 파티션 되어야 한다고 주장한다. 하나의 후임상태를 갖는 이진 모델에서 끌개를 효율적으로 분석하기 위해 우리는 이진 모델을 다수의 하위 모델로 나누는 방법을 제안한다. 이 때 각 하위 모델에는 전체 초기상태의 수에 비해 작은 수의 초기상태를 할당한다. 다수의 후임상태를 갖는 이진 모델의 경우 상태전이의 길이에 따라 상태전이의 수가 기하급수적으로 증가한다. 따라서 우리는 긴 상태전이를 다수의 짧은 상태전이로 파티션한다. 끌개의 수렴공간 분석을 위해 우리는 중복된 상태탐색을 최소화하는 것을 목표로 전체 상태탐색 공간을 파티션한다. 시뮬레이션 결과를 통해 우리는 끌개와 끌개의 수렴공간을 분석하는데 있어 이 논문에서 제안하는 파티션 기반의 방법들이 다수의 상태전이를 생략하여 상태전이 폭발 문제를 해결할 수 있음을 보인다.
