Түсті кодтау - Color-coding

Жылы Информатика және графтар теориясы, термин түстерді кодтау сілтеме жасайды алгоритмдік техника ашуда пайдалы желілік мотивтер. Мысалы, оны анықтау үшін қолдануға болады қарапайым жол ұзындығы $к$ берілген график. Дәстүрлі түстерді кодтау алгоритмі болып табылады ықтималдық, бірақ болуы мүмкін дерандомизацияланған жұмыс уақытында көп шығынсыз.

Түсті кодтау анықтауға да қолданылады циклдар берілген ұзындыққа, және, әдетте, ол субографиялық изоморфизм мәселесі (ан NP аяқталды мәселе), ол қай жерде өнім береді уақыттың көпмүшелік алгоритмдері ол анықтауға тырысқан субографиялық сызба шектелген кезде кеңдік.

Түстерді кодтау әдісі 1994 жылы ұсынылған және талданған Нога Алон, Рафаэль Юстер, және Ури Цвик.^[1]^[2]

Нәтижелер

Түсті кодтау әдісі арқылы келесі нәтижелерді алуға болады:

Әрбір тұрақты үшін к, егер график болса G = (V, E) мөлшерінің қарапайым циклын қамтиды к, онда мұндай циклды мына жерден табуға болады:
- ${ displaystyle O (V ^ { omega})}$ күтілетін уақыт, немесе
- ${ displaystyle O (V ^ { omega} log V)}$ ең нашар уақыт, қайда $ω$ көрсеткіші болып табылады матрицаны көбейту.^[3]
Әрбір тұрақты үшін кжәне әрбір график G = (V, E) бұл кез-келген нейтривиалды емес кішігірім тұйықталған графтар отбасы (мысалы, а жазықтық график ), егер G мөлшерінің қарапайым циклын қамтиды к, онда мұндай циклды мына жерден табуға болады:
- $O (V)$ күтілетін уақыт, немесе
- $O (V журнал V)$ ең жаман уақыт.
Егер график болса $G = (V, E)$ шектелген изоморфты субографияны қамтиды кеңдік бар график $O (журнал V)$ шыңдар, онда мұндай подографияны табуға болады көпмүшелік уақыт.

Әдіс

Субографияны табу мәселесін шешу ${ displaystyle H = (V_ {H}, E_ {H})}$ берілген графикте $G = (V, E)$ , қайда $H$ жол, цикл немесе кез келген шектелген болуы мүмкін кеңдік график қайда ${ displaystyle | V_ {H} | = O ( log V)}$ , түстерді кодтау әдісі кездейсоқ түске боялудан басталады $G$ бірге ${ displaystyle k = | V_ {H} |}$ түсті, содан кейін оның түрлі-түсті көшірмесін табуға тырысады $H$ түрлі-түсті $G$ . Мұндағы график түрлі-түсті, егер ондағы әрбір шың ерекше түспен боялған болса. Бұл әдіс графиканы (1) кездейсоқ бояуды қайталау және (2) мақсатты субографияның түрлі-түсті көшірмесін табу арқылы жұмыс істейді, сайып келгенде, мақсатты субографияны табуға болады, егер процесс жеткілікті рет қайталанса.

Көшірмесін алайық $H$ жылы $G$ нөлге тең емес ықтималдылықпен түрлі-түсті болады $б$ . Егер кездейсоқ бояу қайталанса, бірден пайда болады $1 / б$ Бұл көшірме бір рет түрлі-түсті болады деп күтілуде. Бірақ, дегенмен $б$ кішкентай болса, онда көрсетілген ${ displaystyle | V_ {H} | = O ( log V)}$ , $б$ тек көпмүшелік кіші. Тағы бір алгоритм бар, мысалы, график берілген делік $G$ және әр шыңын бейнелейтін бояу $G$ біреуіне $к$ түстер, ол түрлі-түсті көшірмесін табады $H$ , егер ол бар болса, біраз уақыт ішінде $O (р)$ . Содан кейін оның көшірмесін табуға күтілетін уақыт $H$ жылы $G$ , егер бар болса, болады ${ displaystyle O ({ tfrac {r} {p}})}$ .

Кейде боялудың шектеулі нұсқасын қолданған жөн. Мысалы, циклдарды табу контекстінде жазықтық графиктер, түрлі-түсті циклдарды табатын алгоритм жасауға болады. Мұнда цикл жақсы боялған, егер оның төбелері дәйекті түстермен боялған болса.

Мысал

Мысал ретінде ұзындықтың қарапайым циклын табуға болады $к$ графикте $G = (V, E)$ .

Кездейсоқ бояу әдісін қолдану арқылы әрбір қарапайым циклдың ықтималдығы бар ${ displaystyle k! / k ^ {k}> e ^ {- k}}$ бар болғандықтан, түрлі-түсті болу үшін ${ displaystyle k ^ {k}}$ бояу тәсілдері $к$ циклдегі төбелер, олардың арасында бар ${ displaystyle k!}$ түрлі-түсті құбылыстар. Содан кейін кездейсоқ түсті графикада түрлі-түсті циклдарды табу үшін (келесіде сипатталған) алгоритмді қолдануға болады $G$ уақытында ${ displaystyle O (V ^ { omega})}$ , қайда ${ displaystyle omega}$ көбейтудің матрицалық константасы. Сондықтан, бұл қажет ${ displaystyle e ^ {k} cdot O (V ^ { omega})}$ ұзындықтың қарапайым циклын табуға жалпы уақыт $к$ жылы $G$ .

Циклдарды іздеудің түрлі-түсті алгоритмі алдымен барлық жұптық шыңдарды табу арқылы жұмыс істейді $V$ қарапайым ұзындық жолымен байланысқан $к - 1$ , содан кейін әр жұптағы екі шыңның байланыстырылғандығын тексеру. Бояу функциясы берілген $c : V \to {1, ..., к}$ түсті графикаға $G$ , түстер жиынтығының барлық бөлімдерін санау ${1, ..., к}$ екі ішкі жиынға $C 1, C 2$ өлшемі ${ displaystyle k / 2}$ әрқайсысы. Ескертіп қой $V$ деп бөлуге болады $V 1$ және $V 2$ сәйкесінше және рұқсат етіңіз $G 1$ және $G 2$ арқылы келтірілген ішкі графиктерді белгілеңіз $V 1$ және $V 2$ сәйкесінше. Содан кейін рекурсивті түрде ұзындықтың түрлі-түсті жолдарын табыңыз ${ displaystyle k / 2-1}$ әрқайсысында $G 1$ және $G 2$ . Буль матрицасын алайық $A 1$ және $A 2$ әрбір жұптың қосылуын білдіреді $G 1$ және $G 2$ сәйкесінше түрлі-түсті жолмен және рұқсат етіңіз $B$ шыңдары арасындағы көршілестік қатынастарды сипаттайтын матрица болыңыз $V 1$ және солар $V 2$ , логикалық өнім ${ displaystyle A_ {1} BA_ {2}}$ барлық жұп шыңдарды береді $V$ ұзындықтың түрлі-түсті жолымен байланысты $к - 1$ . Сонымен, матрицалық көбейтудің рекурсивті қатынасы мынада ${ displaystyle t (k) leq 2 ^ {k} cdot t (k / 2)}$ , ол жұмыс уақытын береді ${ displaystyle 2 ^ {O (k)} cdot V ^ { omega} = O (V ^ { omega})}$ . Бұл алгоритм түрлі-түсті жолдың тек соңғы нүктелерін тапқанымен, Алон мен Наордың тағы бір алгоритмі^[4] оған түрлі-түсті жолдарды табуға болады.

Дерандомизация

The дерандомизация түстерді кодтау графтың мүмкін бояуларын санауды қамтиды $G$ , бояудың кездейсоқтығы $G$ енді қажет емес. Мақсатты ішкі графика үшін $H$ жылы $G$ табу үшін, санау кем дегенде бір дананы қамтуы керек, онда $H$ түрлі-түсті. Бұған жету үшін а $к$ - кемелді отбасы $F$ хэш функцияларының ${1, ..., | V |}$ дейін ${1, ..., к}$ жеткілікті. Анықтама бойынша $F$ болып табылады $к$ -әрбір ішкі жиынға арналған болса $S$ туралы ${1, ..., | V |}$ қайда ${ displaystyle | S | = k}$ , хэш функциясы бар $сағ$ жылы $F$ осындай $сағ : S \to {1, ..., к}$ болып табылады мінсіз. Басқаша айтқанда, хэш функциясы болуы керек $F$ бұл кез-келген түсті бояйды $к$ шыңдары $к$ айқын түстер.

Мұндай а-ны салудың бірнеше тәсілдері бар $к$ - мінсіз хэш отбасы:

Үздік айқын құрылыс - бұл Мони Наор, Леонард Дж. Шульман, және Аравинд Сринивасан,^[5] мұнда үлкен отбасы ${ displaystyle e ^ {k} k ^ {O ( log k)} log | V |}$ алуға болады. Бұл конструкция мақсатты подографтың түпнұсқалық іздеу проблемасында болуын талап етпейді.
Тағы бір нақты құрылыс Жанетт П.Шмидт және Алан Сигель^[6] үлкен отбасын береді ${ displaystyle 2 ^ {O (k)} log ^ {2} | V |}$ .
Бастапқы қағазда пайда болатын тағы бір құрылыс Нога Алон т.б.^[2] бірінші салу арқылы алуға болады а $к$ -карталар жасайтын керемет отбасы ${1, ..., | V |}$ дейін ${1, ..., к 2},$ артынан тағы біреуін салады $к$ -карталар жасайтын керемет отбасы ${1, ..., к 2}$ дейін ${1, ..., к}.$ Бірінші қадамда осындай отбасын құруға болады $2 n журнал к$ дерлік кездейсоқ биттер $2лог к$ - тәуелсіз,^[7]^[8] және сол кездейсоқ биттерді жасауға қажет үлгінің кеңістігі аз болуы мүмкін ${ displaystyle k ^ {O (1)} log | V |}$ . Екінші кезеңде оны Жанетт П.Шмидт пен Алан Зигель көрсетті^[6] мұндай мөлшері $к$ - кемелді отбасы болуы мүмкін ${ displaystyle 2 ^ {O (k)}}$ . Демек, $к$ - екі сатыдан шыққан кемелді отбасылар, а $к$ - үлкен отбасылар ${ displaystyle 2 ^ {O (k)} log | V |}$ бұл карталар ${1, ..., | V |}$ дейін ${1, ..., к}$ алуға болады.

Жақсы бояуды рандомизациялау жағдайында, онда подграфта әр шың қатарынан боялған жағдайда, а $к$ -ден бастап хэш-функциялардың керемет отбасы ${1, ..., | V |}$ дейін ${1, ..., к!}$ қажет. Жеткілікті $к$ -картадан шыққан керемет отбасы ${1, ..., | V |}$ дейін ${1, ..., к к}$ жоғарыдағы 3-тәсілге ұқсас етіп салынуы мүмкін (бірінші қадам). Атап айтқанда, оны қолдану арқылы жүзеге асырылады $nk журнал к$ дерлік кездейсоқ биттер $к журнал к$ тәуелсіз және алынған өлшем $к$ - кемелді отбасы болады ${ displaystyle k ^ {O (k)} log | V |}$ .

Түстерді кодтау әдісін дерамандизациялау оңай параллельденуі мүмкін, тиімділік береді NC алгоритмдер.

Қолданбалар

Жақында түстерді кодтау биоинформатика саласында көп көңіл аударды. Бір мысалы - анықтау сигнал беру жолдары жылы ақуыз-ақуыздың өзара әрекеттесуі (PPI) желілері. Тағы бір мысал - санын табу және санау мотивтер PPI желілерінде. Екеуін де зерттеу сигнал беру жолдары және мотивтер организмдер арасындағы көптеген биологиялық функциялардың, процестердің және құрылымдардың ұқсастықтары мен айырмашылықтарын тереңірек түсінуге мүмкіндік береді.

Жинақталатын гендік деректердің үлкен мөлшеріне байланысты жолдарды немесе мотивтерді іздеу ұзақ уақытты қажет етеді. Алайда, түстерді кодтау әдісін қолдана отырып, мотивтер немесе сигнал беру жолдары ${ displaystyle k = O ( log n)}$ желідегі шыңдар $G$ бірге $n$ шыңдарды көпмүшелік уақытта өте тиімді табуға болады. Осылайша, бұл бізге PPI желілеріндегі неғұрлым күрделі немесе үлкен құрылымдарды зерттеуге мүмкіндік береді.

Әрі қарай оқу

Алон, Н .; Дао, П .; Хаджирасулиха, мен .; Хормоздиари, Ф .; Sahinalp, S. C. (2008). «Биомолекулалық желі мотивтерін санау және түстерді кодтау арқылы табу». Биоинформатика. 24 (13): i241 – i249. дои:10.1093 / биоинформатика / btn163. PMC 2718641. PMID 18586721.
Хюфнер, Ф .; Вернике, С .; Зихнер, Т. (2008). «Сигнал жолын анықтауға арналған қосымшалармен түстерді кодтау алгоритмін құру». Алгоритмика. 52 (2): 114–132. CiteSeerX 10.1.1.68.9469. дои:10.1007 / s00453-007-9008-7.

Әдебиеттер тізімі

^ Алон, Н., Юстер, Р. және Цвик, У. 1994. Түстерді кодтау: қарапайым сызбаларды, циклдарды және басқа да кіші графиктерді үлкен графиктерде табудың жаңа әдісі. Есептеулер теориясының жиырма алтыншы ACM симпозиумының материалдарында (Монреаль, Квебек, Канада, 23-25 мамыр, 1994). STOC '94. ACM, Нью-Йорк, Нью-Йорк, 326-335. DOI = http://doi.acm.org/10.1145/195058.195179
^ ^а ^б Алон, Н., Юстер, Р. және Цвик, У. 1995. Түстерді кодтау. J. ACM 42, 4 (1995 ж. Шілде), 844–856. DOI = http://doi.acm.org/10.1145/210332.210337
^ Мысшы – Виноград алгоритмі
^ Alon, N. and Naor, M. 1994 Derandomization, Буль матрицасын көбейту және мінсіз хэш функцияларын құру куәгерлері. Техникалық есеп. UMI Тапсырыс нөмірі: CS94-11., Weizmann Science Press of Israel.
^ Naor, M., Schulman, L. J., and Srinivasan, A. 1995. Сплиттерлер және оңтайлы дерандомизация. Информатика негіздері бойынша 36-шы жыл сайынғы симпозиум материалдар жинағында (1995 ж. - 23 - 25 қазан). ТОҚТАНДЫРУ. IEEE Computer Society, Вашингтон, Колумбия, 182.
^ ^а ^б Шмидт, Дж. П .; Зигель, А. (1990). «K-зондының хэш функциясының кеңістіктегі күрделілігі». SIAM J. Comput. 19 (5): 775–786. дои:10.1137/0219054.
^ Naor, J. and Naor, M. 1990. Ықтималдықтың кішігірім кеңістіктері: тиімді құрылымдар және қолдану. Есептеулер теориясының жиырма екінші жылдық ACM симпозиумының материалдарында (Балтимор, Мэриленд, Америка Құрама Штаттары, 1990 ж. - 13-17 мамыр). Х.Ортис, Ред. STOC '90. ACM, Нью-Йорк, Нью-Йорк, 213-223. DOI = http://doi.acm.org/10.1145/100216.100244
^ Алон, Н., Голдрейх, О., Хастад, Дж. Және Пералта, Р. 1990. К-дерлік тәуелсіз кездейсоқ шамалардың қарапайым құрылысы. Информатика негіздері бойынша 31-ші жыл сайынғы симпозиум материалдар жинағында (1990 ж. 22-24 қазан). SFCS. IEEE Computer Society, Вашингтон, Колумбия, 544-553 т.2. дои:10.1109 / FSCS.1990.89575

[1] Алон, Н., Юстер, Р. және Цвик, У. 1994. Түстерді кодтау: қарапайым сызбаларды, циклдарды және басқа да кіші графиктерді үлкен графиктерде табудың жаңа әдісі. Есептеулер теориясының жиырма алтыншы ACM симпозиумының материалдарында (Монреаль, Квебек, Канада, 23-25 мамыр, 1994). STOC '94. ACM, Нью-Йорк, Нью-Йорк, 326-335. DOI = http://doi.acm.org/10.1145/195058.195179

[orig-2] а ^б Алон, Н., Юстер, Р. және Цвик, У. 1995. Түстерді кодтау. J. ACM 42, 4 (1995 ж. Шілде), 844–856. DOI = http://doi.acm.org/10.1145/210332.210337

[3] Мысшы – Виноград алгоритмі

[4] Alon, N. and Naor, M. 1994 Derandomization, Буль матрицасын көбейту және мінсіз хэш функцияларын құру куәгерлері. Техникалық есеп. UMI Тапсырыс нөмірі: CS94-11., Weizmann Science Press of Israel.

[5] Naor, M., Schulman, L. J., and Srinivasan, A. 1995. Сплиттерлер және оңтайлы дерандомизация. Информатика негіздері бойынша 36-шы жыл сайынғы симпозиум материалдар жинағында (1995 ж. - 23 - 25 қазан). ТОҚТАНДЫРУ. IEEE Computer Society, Вашингтон, Колумбия, 182.

[SS90-6] а ^б Шмидт, Дж. П .; Зигель, А. (1990). «K-зондының хэш функциясының кеңістіктегі күрделілігі». SIAM J. Comput. 19 (5): 775–786. дои:10.1137/0219054.

[7] Naor, J. and Naor, M. 1990. Ықтималдықтың кішігірім кеңістіктері: тиімді құрылымдар және қолдану. Есептеулер теориясының жиырма екінші жылдық ACM симпозиумының материалдарында (Балтимор, Мэриленд, Америка Құрама Штаттары, 1990 ж. - 13-17 мамыр). Х.Ортис, Ред. STOC '90. ACM, Нью-Йорк, Нью-Йорк, 213-223. DOI = http://doi.acm.org/10.1145/100216.100244

[8] Алон, Н., Голдрейх, О., Хастад, Дж. Және Пералта, Р. 1990. К-дерлік тәуелсіз кездейсоқ шамалардың қарапайым құрылысы. Информатика негіздері бойынша 31-ші жыл сайынғы симпозиум материалдар жинағында (1990 ж. 22-24 қазан). SFCS. IEEE Computer Society, Вашингтон, Колумбия, 544-553 т.2. дои:10.1109 / FSCS.1990.89575

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]