Robust Control of Partially Specified Boolean Networks

초안 ===

이 문서는 "부분적으로 명시된 불리언 네트워크의 강건한 제어(Robust Control of Partially Specified Boolean Networks)" 논문에 대한 상세한 기술 요약입니다.

문제 정의

본 논문은 비동기 업데이트(asynchronous updates)를 사용하는 불리언 네트워크(BN)로 모델링된 조절 네트워크(RN)의 제어를 다룹니다. 계산 생물학의 핵심적인 과제는 실험 데이터의 부족이나 내적/외적 관찰 차이로 인해 이러한 네트워크를 지배하는 정확한 불리언 업데이트 함수를 완전히 알 수 없는 경우가 많다는 점입니다. 이는 불리언 네트워크의 일부 업데이트 함수가 해석되지 않은(알 수 없지만 고정된) 기호로 표현되는 **부분적으로 명시된 불리언 네트워크(partially specified Boolean networks)**로 이어집니다.

목표는 **소스-타겟 제어 문제(source-target control problem)**를 해결하는 것입니다. 즉, 특정 변수들을 상수 값으로 고정하는 일련의 섭동(perturbations)을 찾아 네트워크를 소스 상태에서 타겟 어트랙터(안정적인 표현형)로 유도하는 것입니다. 저자들은 이 맥락에서 두 가지 주요 어려움을 식별했습니다:

1. 상태 폭발(State Explosion): 부분적으로 명시된 모델은 완전히 명시된 인스턴스화(instantiation)의 이중 지수적 개수를 나타냅니다. 각 인스턴스화를 명시적으로 분석하는 것은 계산적으로 불가능합니다.
2. 강건성(Robustness): 한 인스턴스에서는 작동하는 섭동이 다른 인스턴스에서는 실패할 수 있습니다. 실행 가능한 제어 전략은 강건해야 하며, 이는 가능한 모든 완전 명시 모델의 상당 부분에 대해 작동함을 의미합니다.
3. 섭동 유형(Perturbation Types): 본 논문은 세 가지 유형의 섭동을 고려합니다:
   • 일회성(One-step): 변수가 한 번 섭동된 후, 시스템이 자유롭게 진화합니다.
   • 영구적(Permanent): 섭동된 변수가 무기한 고정됩니다.
   • 일시적(Temporary): 섭동된 변수가 유한한 단계 동안 고정된 후, 시스템이 자유롭게 진화합니다.

방법론

저자들은 상태 공간 폭발과 부분적으로 명시된 모델의 불확실성을 처리하기 위해 이진 결정 다이어그램(Binary Decision Diagrams, BDD)을 사용하는 **완전 심볼릭 프레임워크(fully symbolic framework)**를 제안합니다.

1. 심볼릭 표현(Symbolic Representation):
모든 인스턴스화를 위해 상태 전이 그래프(STG)를 명시적으로 구축하는 대신, 저자들은 시스템을 심볼릭하게 인코딩합니다. 이들은 확장된 상태 공간 $S = V \times C \times P$를 정의합니다:

• $V$: 네트워크 상태 ($B^n$).
• $C$: 시스템의 미지 부분을 나타내는 입력 값들 ($B^m$).
• $P$: 현재 어떤 변수가 섭동되었는지를 나타내는 비트 집합 ($B^n$).
  이를 통해 단일 BDD 기반 구조 내에서 가능한 모든 모델 인스턴스화와 모든 가능한 섭동을 동시에 표현할 수 있습니다.

2. 알고리즘 접근 방식(Algorithmic Approach):
제어 알고리즘은 확장된 심볼릭 공간에 맞게 조정된 표준 그래프 연산에 의존합니다:

• PRE/POST: 섭동된 변수($p_i=1$)는 업데이트되지 않으면서, 섭동되지 않은 변수는 네트워크 역학에 따라 진화한다는 제약 조건을 준수하는 심볼릭 선행자(predecessor) 및 후속자(successor) 계산입니다.
• BWD (Backward Reachability): 타겟 집합에 도달할 수 있는 상태 집합을 계산합니다.
• TRAP: 특정 집합으로부터 탈출할 수 없는 상태(trap set)를 계산하며, 이는 효과적으로 강력한 끌개 영역(strong basin of attraction)을 식별합니다.
• CANPERTURB: 도달 가능한 상태를 필터링하여, 해당 상태가 유효한 섭동 단계를 통해 특정 소스 상태로부터 도달 가능한지 확인하는 유틸리티 함수입니다(섭동되지 않은 변수가 소스 상태와 일치하도록 보장함).

3. 제어 절차(Control Procedures):
논문은 세 가지 제어 유형에 대한 특정 알고리즘을 정의합니다:

• 영구적 제어(Permanent Control): 섭동된 변수가 고정되어 있다는 가정하에 타겟의 트랩 공간(trap space)을 계산합니다.
• 일회성 제어(One-Step Control): 초기 단계 이후에는 섭동이 없다고 가정하여 타겟의 트랩 공간을 계산한 다음, 어떤 섭동이 소스를 이 영역(basin)으로 연결할 수 있는지 확인합니다.
• 일시적 제어(Temporary Control): 2단계 접근 방식을 사용합니다. 먼저, 섭동되지 않은 시스템에서의 타겟 트랩 공간을 계산합니다. 그 다음, 변수가 고정된 기간을 허용하여 시스템이 자유롭게 진로를 결정하기 전의 트랩 공간을 계산합니다.

4. 강건성 지표(Robustness Metrics):
제어의 품질을 평가하기 위해 저자들은 두 가지 정량적 척도를 도입합니다:

• 최대 강건성 ($\rho_{max}$): 집합 내의 단일 최적 섭동에 의해 제어되는 완전 명시 인스턴스의 비율입니다.
• 합집합 강건성 ($\rho_{union}$): 집합 내의 적어도 하나의 섭동에 의해 제어되는 완전 명시 인스턴스의 비율입니다.

결과

저자들은 다양한 크기(변수 최대 53개)와 부분 명시 정도를 가진 다섯 가지 생물학적 모델(골수 분화, 심장 발달, ERBB 키나아제 과발현, 종양 전이, MAPK 신호 전달)에 대해 방법론을 평가했습니다.

• 확장성(Scalability): 심볼릭 접근 방식은 $2^{53}$개의 상태(MAPK 모델의 53개 변수에 해당)와 다양한 입력 값(colours)의 개수를 성공적으로 처리했습니다. 표 2는 계산 시간이 입력 값의 수에 비해 훨씬 느리게 증가함을 보여줍니다(예: 색상의 수가 128배 증가했을 때 실행 시간은 3~6배만 증가함).
• 준심볼릭 방법과의 비교: 표 3은 완전 심볼릭 접근 방식과 [46]의 준심볼릭(semi-symbolic) 방법을 비교합니다. 완전 심볼릭 접근 방식은 메모리 제약으로 인해 실패한 더 큰 모델(예: MAPK 모델)에서 준심볼릭 방식보다 우수한 성능을 보였습니다. 그러나 많은 색상을 가진 작은 모델의 경우, BDD 순서 지정 휴리스틱 덕분에 준심볼릭 방식이 더 빠를 수 있습니다.
• 제어 유형 및 강건성:
  • 계산 시간: 일회성 제어가 가장 빠릅니다. 일시적 제어는 두 개의 서로 다른 트랩 공간을 계산해야 하므로 가장 많은 계산량을 요구합니다.
  • 강건성: 실험 결과(그림 1 및 2)는 일시적 및 영구적 섭동이 일회성 섭동보다 일반적으로 더 강건하다는 가설을 뒷받침합니다. 많은 경우, 작은 크기(예: 2 또는 3개의 변수)의 일시적 섭동만으로도 모델 인스턴션의 높은 비율(최대 80-90%)을 제어할 수 있었습니다.
  • 심장 모델의 특이점: 심장 모델의 경우, 일시적 제어가 영구적 제어보다 높은 합집합 강건성을 보였는데, 이는 일부 섭동이 영구적으로 적용되면 네트워크 역학을 방해하지만 일시적으로 적용하면 작동할 수 있음을 시사합니다.

의의 및 주장

본 논문은 제안된 심볼릭 방법이 모든 모델 인스턴스화를 열거하는 방식으로는 불가능한, 부분적으로 명시된 불리언 네트워크의 제어 문제를 위한 효율적이고 확장 가능한 솔루션을 제공한다고 주장합니다.

• 효율성: 완전 심볼릭 접근 방식은 높은 불확실성을 가진 상대적으로 큰 BN(20개 이상의 변수)의 분석을 가능하게 하며, 이전의 준심볼릭 방법보다 처리 가능한 최대 모델 크기 측면에서 우수합니다.
• 실용적 적용 가능성: 강건성을 정량화함으로써, 이 프레임워크는 불완전한 지식에도 불구하고 실제 생물학적 시스템에서 작동할 가능성이 높은 제어 전략을 식별하는 데 도움을 줍니다.
• 일시적/영구적 제어의 우월성: 실험 결과는 일시적 및 영구적 섭동이 일회성 섭동보다 더 나은 강건성을 제공함을 시사하며, 이는 정확한 네트워크 역학을 완전히 알 수 없는 세포 리프로그래밍 응용 분야에서 이들이 더 유망할 수 있음을 의미합니다.

저자들은 자신들의 방법이 현재 소스-타겟 제어 및 정적 섭동을 지원하지만, 향로 타겟 제어, 표현형 제어 및 순차적 섭동 전략으로 확장할 수 있는 기초를 마련했다고 결론짓습니다.