RWR algoirthm #

개요 #

RWR (random walk with restart) algorithm은 이미지 분할을 위한 알고리즘이다. 초기 알고리즘은 이미지 분할을 위한 대화식 방법으로 처음 컨퍼런스에 소개되었다. 하지만 데이터 충실도 조건 (ex. 강도 우선)이 주어지면 완전 자동 알고리즘으로 이미지 분할이 아닌 다른 응용 프로그램으로도 확장될 수 있다. 이미지 색상화, 의료 영상 분할, 분할 편집, 그림자 제거, 이미지 융합 등으로 컴퓨터 visualization 및 그래픽의 여러 분야에 응용될 수 있다. 이러한 이미지 관련된 분야가 아닌 생물정보학 분야에서도 이 알고리즘은 응용될 수 있는데, PPIs (protein-protein interactions), DTIs (Durg-target interactions) 등의 분석에 사용될 수 있다.

Mathematics #

RWR (random walk with restart) algorithm은 classic 한 순위 알고리즘이다. 하나 이상의 seed node(P0)로부터 random walking을 시작으로 시뮬레이션한다. 알고리즘의 시작인 초기화 벡터인 P0에서 그다음 노드인 P1, P1에서 P2, P2에서 P3 방식으로 값이 update 된다.

RWR algorithm은 다음과 같은 식을 따른다. $${ P }_{ i+1 }=(1-r)A^T{ P }_{ i }+r{ P }_{ 0 }$$

식에 대해 설명을 하자면,

• A는 열 방향의 정규화 행렬로 각 노드 간의 근접성에 대한 값을 가진 행렬
• r은 각 노드가 시작 노드인 P0로 돌아갈 확률

식이 계속 진행이 되면서 (i의 값이 점점 커질수록) 하나의 값에 수렴되거나 혹은 지정한 값에 도달할 때 RWR 알고리즘은 중단된다.

RWR 알고리즘은 네트워크를 통해 잠재적인 epigenetic factor를 추출한다. 이러한 특성을 통해 PPIs나 DTIs와 같은 분석을 할 수가 있는데, 이 알고리즘을 통해 나온 인자들이 모두 실제 인자가 아닐 수도 있다. 따라서 false positive를 제거하여 가장 주요한 candidate facotr를 선택하기 위해서는 filtering 과정이 필요하다.

Applications #

PPIs (protein-protein interactions) #

인간뿐만 아니라 모든 생명체의 생물학적으로 활성을 가지는 단백질은 홀로 작용하는 경우가 거의 없다. 단백질은 다른 단백질 또는 complex 등과의 상호작용을 통해 대사나 다른 활성을 조절한다. 따라서 단백질 간의 상호작용에 대한 정보는 여러 PPIs 관련 분석에 유용하다. 이러한 PPIs 정보를 이용한 분석을 통해 질병과 관련 있는 새로운 유전자를 확인과 아직 알려지지 않은 단백질의 기능도 예측할 수 있다.

DTIs (Drug-target interactions) #

DTIs는 drug discovery에서 주요한 역할을 한다. 대부분 약물은 target과 직접적으로 결합하여 target의 biological function을 활성화 혹은 비활성화시킨다. 하지만 약물들은 하나의 target이 아닌 여러 개의 target을 가지고 있으며, 이들을 실험적인 방법으로 찾으면 비용과 시간이 많이 들 뿐만 아니라 위험들이 따라오게 된다. 그러므로 DTI와 같은 컴퓨터적인 계산 방법을 통해 비용과 시간 및 위험을 줄일 수 있다.

RWR algorithm을 DTIs 분야에 응용한 한 논문에서는 PPI (protein-protein interaction), DDI (drug-drug interaction), DTI (drug-target interaction) 세 단계로 나누어 약물의 target을 예측하였다.

참고문헌 #

• Random walker algorithm: Wikipedia 1
• Identification of drug-target interaction by a random walk with restart method on an interactome network: Lee, Ingoo, and Hojung Nam: BMC bioinformatics 2
• A network-based method using a random walk with restart algorithm and screening tests to identify novel genes associated with Meniere's disease: Li, Lin, et al.: PloS one3
• A computational method using the random walk with restart algorithm for identifying novel epigenetic factors: Li, JiaRui, et al: Molecular Genetics and Genomics4
• RecRWR: a recursive random walk method for improved identification of diseases: Perdiz Arrais, Joel, and José Luís Oliveira.: BioMed research international 5