컬러 코딩

컴퓨터 과학과 그래프 이론에서 컬러 코딩이라는 용어는 네트워크 모티브의 발견에 유용한 알고리즘 기법을 가리킨다. 예를 들어 특정 그래프에서 길이 k의 단순한 경로를 검출하는 데 사용할 수 있다. 전통적인 컬러 코딩 알고리즘은 확률론적이지만 러닝타임에 큰 오버헤드 없이 디랜덤화될 수 있다.

색상 코딩은 주어진 길이의 사이클 검출에도 적용되며, 보다 일반적으로 탐지하려는 서브그래프 패턴이 경계 트리폭을 가질 때 다항 시간 알고리즘을 산출하는 서브그래프 이형성 문제(NP-완전성 문제)에도 적용된다.

컬러 코딩 방식은 1994년 노가 알론, 라파엘 유스터, 우리 즈윅 등이 제안해 분석했다.^[1][2]

결과.

색상 코딩 방법을 통해 다음과 같은 결과를 얻을 수 있다.

• 모든 고정 상수 k에 대해 그래프 G = (V, E)에 k 크기의 단순한 주기가 포함된 경우, 그러한 주기는 다음에서 찾을 수 있다.
  • ${\displaystyle O}$( ${\displaystyle {}^{}}$ ${\displaystyle {\Omega }^{}}$) ${\displaystyle O(V^{\omega }})$ 예상$$ 시간 또는
  • ${\displaystyle O({}^{}}$ ${\displaystyle {\Omega }^{}}$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ ${\displaystyle V}$) ${\displaystyle O(V^{\omega }\log V)}$ 최악의$$ 경우, 여기서 Ω은 행렬 곱셈의 지수다.^[3]
• 모든 고정 상수 k와 비교 부 폐쇄 그래프 계열(예: 평면 그래프)에 있는 모든 그래프 G = (V, E)에 대해 G가 단순한 크기 k 사이클을 포함하는 경우, 다음에서 그러한 사이클을 찾을 수 있다.
  • O(V) 예상 시간 또는
  • O(V 로그 V) 최악의 경우.
• 그래프 G = (V, E)에 O(log V) 정점이 있는 경계 트리 너비 그래프에 대해 이형성이 있는 하위 그래프가 포함된 경우 다항 시간에서 이러한 하위 그래프를 찾을 수 있다.

방법

To solve the problem of finding a subgraph ${\displaystyle H=(V_{H},E_{H})}$ in a given graph G = (V, E), where H can be a path, a cycle, or any bounded treewidth graph where ${\displaystyle V_{H} =O(\log V)}$, the method of color-coding begins by randomly coloring each vertex of G($k{\displaystyle )}$ = ${\displaystyle V_{}}$ H $displaystyle k= V_{H}}$ 컬러를$$ 가진 다음 컬러 G에서 화려한 색상의 H 카피를 찾으려고 한다. 여기서, 그 안에 있는 모든 꼭지점이 뚜렷한 색으로 색칠되면 그래프가 다채롭다. 이 방법은 (1) 무작위로 그래프를 색칠하고 (2) 대상 서브그래프의 화려한 사본을 찾아내는 것을 반복하는 방식으로 작동하며, 결국 그 과정을 충분히 반복하면 대상 서브그래프를 찾을 수 있다.

G에서 H의 복사본이 0이 아닌 확률 p와 함께 다채로워진다고 가정하자. 그것은 즉시는 만일 가장 임의에 색을 내는 것 반복되.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.m 따른다.W-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}1/p번, 이 복사본 한 때 다채롭게 될 것으로 예상된다. p는 작지만, ${\displaystyle V_{}{}_{}}$H = ${\displaystyle O(\log v}$ V${\displaystyle }$)$${\$displaystyle V_{H}$ =$O(\log$ V$)\}$ , p는 다항식적으로 작을 뿐임을 알 수 있다. G의 각 꼭지점을 K 색상 중 하나에 매핑하는 그래프 G와 색상이 주어진 경우, 어떤 런타임 O(r) 내에서 화려한 H의 복사본을 찾는 알고리즘이 존재한다고 가정하자. 그런 다음 G에서 H 사본을 찾을 것으로 예상되는 $시간$은 O${\displaystyle }$( ${\displaystyle \frac{r}{}}$p )$${\$displaystyle O({\tfrac {r}{p}})}$ 입니다$.$

때로는 좀 더 제한된 버전의 화려함을 사용하는 것도 바람직하다. 예를 들어 평면 그래프의 사이클을 찾는 맥락에서 양호한 색상의 사이클을 찾는 알고리즘을 개발할 수 있다. 여기서, 주기는 그것의 정점이 연속된 색으로 색칠되면 잘 색칠된다.

예

그래프 G = (V, E)에서 길이 k의 단순한 주기를 찾는 것이 그 예일 것이다.

무작위 색소법을 적용하면 각 단순주기는 / > - ${\$ $k$$!/k^{$$k}}}}$$주기$에 k$$정점을 색칠하는 $방법$이 있고, 그 중에는 $k{\displaystyle !}$ ${\displaysty k^!}$의 색소 발생이 있기 때문에 k$!$ / k > e - k > e - displaysty sty colornow. 그런 다음 알고리즘(다음 설명)을 사용하여 시간 $O{\displaystyle ({}^{}}$ ${\displaystyle {\Omega }^{}}$) ${\displaystyle O(V^{\omega$ $\}\})$의 랜덤 색상 그래프 G에서 다채로운 주기를 찾을 수 있으며, 여기서 $\Omega {\displaystyle }$ ${\displaystyle$ \$omega }$은 행렬 곱셈 상수다. 따라서 G에서 길이 k의 단순한 주기를 찾으려면 전체$$ 시간 $동안{\displaystyle {}^{}}$ ${\displaystyle e^{}}$ k${\displaystyle {}^{}}$o O${\displaystyle (V^{}}$ Ω ${\displaystyle {}^{}}${\$displaystyle e^{k}\cdot$ O$(V^{\omega })$가 소요된다.

컬러풀한 사이클 탐색 알고리즘은 먼저 길이 k - 1의 단순한 경로로 연결된 V의 모든 꼭지점 쌍을 찾아 각 쌍의 두 꼭지점이 연결되어 있는지 확인하는 방식으로 작동한다. 컬러 그래프 G에 색상 함수 c → {1, ..., k}을(를) 지정하면 색상 집합 {1, ..., k}의 모든 파티션을 각각 k/${\displaystyle 2\mathrm{}}$ $크기$의 C₂, 2 ${\displaystyle k/2$}의$$두 하위 집합으로₁ 열거하십시오${\displaystyle .}$ 이에 따라 V는 V와₁ V로₂ 나눌 수 있으며, G와₁₂ G는 각각₁ V와₂ V가 유도하는 서브그래프를 나타내도록 한다. 그런₁ 다음 $G$와 G₂ ${\displaystyle 각각}$에서 ${\displaystyle \mathrm{길이}}$k$$/ 2 ${\displaystyle -}$ 1의 $다채로운 경로$를 재귀적으로 찾는다$.$ 부울 행렬 A와₁ A가₂ 각각 다채로운 경로에 의해₁ G와 G의₂ 각 꼭지점 쌍의 연결을 나타내며, B를₁ V의 꼭지점과 V의₂ 꼭지점 사이의 인접 관계를 설명하는 행렬로 가정하자, 부울 제품 $A{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ B ${\displaystyle {A\mathrm{}}_{}}$ 2 ${\$$BA_{2}}:$ V의 모든 꼭지점 쌍은 길이 k - 1의 화려한 경로로 연결된다$$. Thus, the recursive relation of matrix multiplications is ${\displaystyle t(k)\leq 2^{k}\cdot t(k/2)}$, which yields a runtime of ${\displaystyle 2^{O(k)}\cdot V^{\omega }=O(V^{\omega })}$. Although this algorithm finds only the end points of the colorful path, a알론과 나오르가^[4] 직접 다채로운 경로를 찾아내는 노처 알고리즘이 그 안에 통합될 수 있다.

디랜도믹스

색상 코딩의 디랜도믹스는 더 이상 색상 G의 무작위성이 필요하지 않도록 그래프 G의 가능한 색상을 열거하는 것을 포함한다. G의 대상 서브그래프 H를 발견할 수 있으려면, 열거에 H가 다채로운 경우를 적어도 하나 이상 포함해야 한다. 이를 위해서는 {1, ..., V }에서 {1, ..., k}까지의 해시함수의 k-퍼펙트 패밀리 F를 열거하면 충분하다. 정의에 따르면, {1, ..., V }의 모든 부분 집합 S에 ${\displaystyle 대해}$, S =${\displaystyle }$k =$$ {\$displaystyle$S =$k$ F에 h : S → {1, ..., k}이(가) 완벽하다는 해시함수 h가 존재한다면 F는 k-완벽하다. 즉, 주어진 k 정점에 k 구별되는 색상으로 색칠하는 해시함수가 F에 존재해야 한다.

이러한 k-퍼펙트 해시 패밀리를 구성하기 위한 몇 가지 접근법이 있다.

1. 최고의 명시적 구성은 모니나오르, 레너드 J. 슐만, 아라빈드 스리니바산(Aravind Srinivasan)에 의해 이루어지며,^[5] 여기서 크기 ${\displaystyle {}^{}{}^{}}$ ${\displaystyle {O(\mathrm{로그}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$) ${\displaystyle \mathrm{로그}}$ $displaystyle e^{k}k^{O(\log k)}\log$ V$}$를 얻을 수 있다$$. 이 구조는 원래 서브그래프 문제점에 대상 서브그래프가 존재할 필요가 없다.
2. 지넷 P의 또 다른 노골적인 건축. 슈미트와 앨런 시겔은^[6] 크기가 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle O^{}}$(${\displaystyle k^{}}$ ) ${\displaystyle {로그\mathrm{}}^{}}$ 2${\displaystyle {}^{}v}$ V $displaystyle 2^{O(k)}\log ^{2$} $V$}인 패밀리를 산출한다$.$
3. 노가 알론 외 ^[2]원지에 등장하는 또 다른 구조는 먼저 {1, ..., V }을(를) {1, ..., ..., k²}을(를) 맵핑하는 k-퍼펙트 패밀리를 구축한 다음 {1, ..., k²}을(를) 맵핑하는 또 다른 k-퍼펙트 패밀리를 구축함으로써 얻을 수 있다. 첫 번째 단계에서는 거의 2log k-wise 독립된 2nlog k 랜덤 비트를 가진 그러한 패밀리를 구성할 수 있으며,^[7][8] 그러한 랜덤 비트를 생성하는 데 필요한 샘플 공간은 k${\displaystyle {\mathrm{O}(}^{}}$1 ) ${\displaystyle 로그}$ V $displaystyle$ k$^{O(1)}\log$ V $}$만큼 작을 수 있다$.$ 두 번째 단계에서는 제넷 P가 보여주었다. Schmidt and Alan Siegel^[6] that the size of such k-perfect family can be ${\displaystyle 2^{O(k)}}$. Consequently, by composing the k-perfect families from both steps, a k-perfect family of size ${\displaystyle 2^{O(k)}\log V }$ that maps from {1, ..., V } to {1, ..., k} can be obtained.

서브그래프의 각 꼭지점이 연속적으로 색칠되는 웰컬러링의 경우, {1, ..., V }부터 {1, ..., k!}까지의 k-완벽한 해시함수 계열이 필요하다. {1, ..., V }에서 {1, ..., k^k}까지 매핑되는 충분한 k-퍼펙트 패밀리는 위의 접근 3(첫 번째 단계)과 유사한 방법으로 구성할 수 있다. 특히 klog k에 거의 독립적인 nklog k 랜덤비트를 사용하여 수행되며, 결과 k-perfect 패밀리의 $크기$는 k ${\displaystyle {O(}^{}}$k ) 로그${\displaystyle \log }$ ${\displaystyle V}${\$displaystyle k^{O(k)}\log$ V$$}가 된다$.$

컬러 코딩 방식의 디랜도메이션을 쉽게 병렬화할 수 있어 효율적인 NC 알고리즘이 가능하다.

적용들

최근 생물정보학 분야에서 컬러 코딩이 많은 관심을 끌고 있다. 단백질-단백질 상호작용(PPI) 네트워크에서 신호 경로 검출이 한 예다. 또 다른 예는 PPI 네트워크에서 모티브의 수를 발견하고 세는 것이다. 신호 경로와 모티프를 모두 연구하면 유기체들 사이의 많은 생물학적 기능, 과정, 구조들의 유사점과 차이점을 더 깊이 이해할 수 있다.

수집할 수 있는 유전자 데이터의 양이 많기 때문에 경로나 모티브를 찾는 데 많은 시간이 소요될 수 있다. 단, 컬러 코딩 방법을 활용함으로써, $정점$이 n인 네트워크 G에서 k${\displaystyle }$= O${\displaystyle (\mathrm{로그}}$ ${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle k=O(\log n)}$ 정점을$$ 가진 모티브나 신호 경로를 다항식 시간대에 매우 효율적으로 찾을 수 있다. 그러므로, 이것은 PPI 네트워크에서 더 복잡하거나 더 큰 구조를 탐구할 수 있게 해준다.

추가 읽기

• Alon, N.; Dao, P.; Hajirasouliha, I.; Hormozdiari, F.; Sahinalp, S. C. (2008). "Biomolecular network motif counting and discovery by color coding". Bioinformatics. 24 (13): i241–i249. doi:10.1093/bioinformatics/btn163. PMC 2718641. PMID 18586721.
• Hüffner, F.; Wernicke, S.; Zichner, T. (2008). "Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection". Algorithmica. 52 (2): 114–132. CiteSeerX 10.1.1.68.9469. doi:10.1007/s00453-007-9008-7.

참조