검정력 그래프 분석

계산 생물학에서 파워 그래프 분석은 복잡한 네트워크의 분석과 표현을 위한 방법이다.전력 그래프 분석은 그래프(네트워크)에서 출력 그래프의 계산, 분석 및 시각적 표현이다.

파워 그래프 분석은 그래프의 무손실 압축 알고리즘으로 생각할 수 있다.^[1]그것은 그래프 구문을 clique, biclique, 별의 표현으로 확장한다.복잡한 생물학적 네트워크에 대해 최대 95%의 압축 수준이 확보되었다.

하이퍼그래프는 에지가 단순히 노드의 커플이 아니라 임의의 n-tuple인 그래프를 일반화한 것이다.검정력 그래프는 그래프의 또 다른 일반화가 아니라, "노드와 에지" 언어에서 클릭, 바이클릭, 별을 원시 양으로 사용하여 하나의 언어로의 전환을 제안하는 그래프를 참신한 표현이다.

검정력 그래프

그래픽 표현

그래프는 가장자리를 나타내는 노드의 쌍을 연결하는 노드와 선을 나타내는 원이나 점으로 그려진다.파워 그래프는 노드나 다른 전원 노드를 감싸는 원으로 그려지는 전원 노드와 전원 노드 사이의 선인 전원 에지(power edge)를 포함한 그래프의 구문을 확장한다.

빅키(biclique)는 한 세트의 모든 멤버와 다른 세트의 모든 멤버 사이에 에지가 있는 두 세트의 노드들이다.전력 그래프에서, 바이클릭은 두 전력 노드 사이의 에지로 표현된다.

클릭은 모든 노드 쌍 사이에 에지가 있는 노드 집합이다.파워 그래프에서 클라이크는 루프가 있는 파워 노드에 의해 표현된다.

별은 집합의 모든 멤버와 집합 외부의 단일 노드 사이에 에지가 있는 노드 집합이다.검정력 그래프에서 항성은 정규 노드와 파워 노드 사이의 검정력 에지로 표현된다.

형식 정의

Given a graph ${\displaystyle G={\bigl (}{V,E}{\bigr )}}$ where ${\displaystyle V={\bigl \{}v_{0},\dots ,v_{n}{\bigr \}}}$ is the set of nodes and ${\displaystyle E\subseteq V\times V}$ is the set of edges, a power graph ${\displaystyle G^{\prime }=(V^{\prime },E^{\prime })}$${\displaystyle G'={{V',E'}{\bigr )}}}$은(는) 전원 가장자리에 의해 서로 연결된 전원 노드의 $V{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle \subseteq }$ ${\displaystyle P}$( $){\$ V$'\subseteq {\p}{\bigl (}V{\bigr )}}}$에 정의된 그래프$$:${\displaystyle E^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle \subseteq }$ ${\displaystyle {}^{}}$ ${\displaystyle \times }$ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ E$'\subseteq$ V$'\times V$ 따라서 $출력$ 그래프는 노드의 전원 $집합$과 그래프 G {\displaystyle $G}$의 가장자리 전원 집합에 정의된다$.$

전원 그래프의 의미론은 다음과 같다: 두 개의 전원 노드가 전원 에지로 연결되어 있다면, 이는 첫 번째 전원 노드의 모든 노드가 두 번째 전원 노드의 모든 노드에 연결됨을 의미한다.마찬가지로 전원 노드가 전원 에지에 의해 자체로 연결되어 있다면 이는 전원 노드의 모든 노드가 에지에 의해 서로 연결되어 있음을 의미한다.

다음과 같은 두 가지 조건이 필요하다.

• 전원 노드 계층 조건:두 개의 전원 노드는 분리되거나 다른 노드에 포함된다.
• 파워 에지 분리 상태:원본 그래프의 가장자리에서 전원 가장자리로의 온보드 매핑이 있다.^{[citation needed]}

푸리에 분석과 유사함

함수의 푸리에 분석은 t${\displaystyle }t{\displaystyle }$ ${\displaystyle x}$ ${\displaystyle t\mapsto x}$ 쌍$$ 대신 조화함수의 관점에서 함수를 다시 쓰는 것으로 볼 수 있다.이러한 변환은 시간 영역에서 주파수 영역으로 관점을 변경하고 신호 분석, 데이터 압축 및 필터링에서 많은 흥미로운 애플리케이션을 가능하게 한다.마찬가지로, 전력 그래프 분석은 (푸리에 분석을 위한 고조파 함수와 마찬가지로) 원시 요소로서 빅키, 클릭 및 별을 사용하여 네트워크를 다시 쓰거나 분해하는 것이다.네트워크를 분석, 압축 및 필터링하는 데 사용할 수 있다.그러나 몇 가지 주요 차이점이 있다.첫째, 푸리에 분석에서 두 공간(시간 및 주파수 영역)은 동일한 함수 공간이지만 엄밀한 감각에서는 검정력 그래프가 그래프가 아니다.둘째, 주어진 그래프를 나타내는 고유한 검정력 그래프가 없다.그러나 매우 흥미로운 등급의 검정력 그래프는 주어진 그래프를 나타내기 위해 필요한 검정력 가장자리와 검정력 노드가 가장 적은 최소 검정력 그래프다.

최소 검정력 그래프

일반적으로 주어진 그래프에 대해 고유한 최소 검정력 그래프가 없다.이 예(오른쪽)에서 4개의 노드와 5개의 가장자리의 그래프는 각각 2개의 가장자리의 최소 전력 그래프를 허용한다.이 두 최소 전력 그래프 사이의 주요 차이점은 두 번째 전력 그래프의 높은 내포 수준과 기본 그래프에 대한 대칭성의 손실이다.복잡한 네트워크는 애초에 그러한 대칭을 거의 나타내지 않기 때문에 대칭성의 상실은 작은 장난감 예에서 문제일 뿐이다.또한 둥지 수준을 최소화할 수 있지만, 일반적으로 최소 둥지 수준의 고유한 최소 전력 그래프는 없다.

파워 그래프 탐욕 알고리즘

전력 그래프 탐욕 알고리즘은 분해 수행을 위해 두 가지 간단한 단계에 의존한다.

첫 번째 단계는 인접 노드의 유사성에 기초하여 네트워크에서 노드의 계층적 클러스터링을 통해 후보 전원 노드를 식별한다.이웃 두 세트의 유사성은 두 세트의 자카드 지수로 간주된다.

두 번째 단계는 후보 전원 노드 사이의 가능한 전원 에지를 탐욕스럽게 검색한다.원래 네트워크에서 가장 많은 가장자리를 추상화하는 전원 가장자리가 먼저 전원 그래프에 추가된다.따라서 나머지 모든 단일 가장자리도 추가될 때까지 biclique, clique 및 별은 점진적으로 전력 가장자리로 대체된다.전원 에지의 끝점이 아닌 후보 전원 노드는 무시된다.

모듈식 분해

모듈식 분해는 모듈식 분해의 강력한 모듈을 사용하여 파워 그래프를 계산하는 데 사용될 수 있다.모듈식 분해 모듈들은 동일한 이웃을 가진 그래프 안의 노드 그룹이다.스트롱 모듈은 다른 모듈과 겹치지 않는 모듈이다.그러나 복잡한 네트워크에서는 강력한 모듈이 규칙보다 더 예외적이다.따라서 모듈식 분해를 통해 얻은 검정력 그래프는 최소성과 거리가 멀다.모듈화 분해와 전력 그래프 분석의 주요 차이점은 노드 모듈뿐만 아니라 에지 모듈(크리크, bicliques)을 사용하여 그래프를 분해할 때 전력 그래프 분석을 강조하는 것이다.실제로, 전력 그래프 분석은 노드와 에지의 손실 없는 동시 클러스터링으로 볼 수 있다.

적용들

생물학적 네트워크

전력 그래프 분석은 단백질-단백질 상호작용 네트워크,^[2] 도메인-펩타이드 결합 모티브, Gene 규제 네트워크^[3], Homology/Paralogy 네트워크와 같은 여러 유형의 생물학적 네트워크를 분석하는 데 유용한 것으로 나타났다.또한 최근 Power Graphs로 주요 질병-트래프트 쌍의^[4] 네트워크가 시각화 및 분석되었다.

파워그래프에서 도출된 새로운 조치인 네트워크 압축은 단백질 상호작용 네트워크의 품질 측정으로 제안되었다.^[5]

약물 위치 조정

파워 그래프는 약물 위치 조정을 위한 약물 표적-질병 네트워크^[6] 분석에도 적용되었다.

소셜 네트워크

파워 그래프는 소셜 네트워크의 대규모 데이터, 커뮤니티 마이닝^[7] 또는 작성자 유형 모델링에 적용되었다.^[8]

참고 항목

• 계산생물학
• 네트워크/그래프
• 복잡한 네트워크
• 모듈식 분해

참조

외부 링크

• [1] Power Graph Analysis 도구(CyOog v2.8.2) 및 예제 애플리케이션
• [2] CyOog v2.6을 사용한 검정력 그래프 분석