Ranglarni kodlash - Color-coding

Yilda Kompyuter fanlari va grafik nazariyasi, atama ranglarni kodlash ga ishora qiladi algoritmik texnika bu kashfiyotda foydalidir tarmoq motivlari. Masalan, uni aniqlash uchun ishlatilishi mumkin oddiy yo'l uzunlik k berilgan birida grafik. An'anaviy ranglarni kodlash algoritmi ehtimoliy, lekin bo'lishi mumkin derandomizatsiya qilingan ish vaqtida juda ko'p xarajatlarsiz.

Ranglarni kodlash shuningdek aniqlashga tegishli tsikllar berilgan uzunlikka ega va umuman olganda u subgraf izomorfizm muammosi (an To'liq emas muammo), u qaerda hosil beradi polinom vaqt algoritmlari u aniqlamoqchi bo'lgan subgraf naqshlari chegaralangan bo'lsa kenglik.

Ranglarni kodlash usuli 1994 yilda taklif qilingan va tahlil qilingan Noga Alon, Rafael Yuster va Uri Tsvik.^[1][2]

Natijalar

Ranglarni kodlash usuli yordamida quyidagi natijalarga erishish mumkin:

• Har bir doimiy uchun k, agar grafik G = (V, E) o'lchamning oddiy tsiklini o'z ichiga oladi k, keyin bunday tsiklni topish mumkin:
  • ${ displaystyle O (V ^ { omega})}$ kutilgan vaqt yoki
  • ${ displaystyle O (V ^ { omega} log V)}$ eng yomon vaqt, qaerda ω ning ko'rsatkichidir matritsani ko'paytirish.^[3]
• Har bir doimiy uchun kva har bir grafik G = (V, E) bu har qanday noan'anaviy narsada kichik-yopiq graflar oilasi (masalan, a planar grafik ), agar G o'lchamning oddiy tsiklini o'z ichiga oladi k, keyin bunday tsiklni topish mumkin:
  • O(V) kutilgan vaqt yoki
  • O(V jurnal V) eng yomon vaqt.
• Agar grafik G = (V, E) chegaralangan izomorfik subgrafni o'z ichiga oladi kenglik ega bo'lgan grafik O(log V) vertices, keyin bunday subgrafani topish mumkin polinom vaqti.

Usul

Subgrafni topish masalasini hal qilish uchun ${ displaystyle H = (V_ {H}, E_ {H})}$ berilgan grafikada G = (V, E), qayerda H yo'l, tsikl yoki har qanday chegaralangan bo'lishi mumkin kenglik grafik qaerda ${ displaystyle | V_ {H} | = O ( log V)}$, ranglarni kodlash usuli tasodifiy har bir vertikalni bo'yash bilan boshlanadi G bilan ${ displaystyle k = | V_ {H} |}$ ranglar, so'ngra rang-barang nusxasini topishga harakat qiladi H rangli G. Bu erda grafik har bir tepalik alohida rang bilan bo'yalgan bo'lsa rang-barang rangga ega. Ushbu usul (1) grafikani tasodifiy bo'yashni takrorlash va (2) maqsadli subgrafaning rang-barang nusxasini topish orqali ishlaydi va natijada maqsad subgrafni jarayon etarli darajada takrorlanganda topish mumkin.

Ning nusxasini aytaylik H yilda G nolga teng bo'lmagan ehtimollik bilan rang-barang bo'ladi p. Darhol, agar tasodifiy rang takrorlangan bo'lsa 1/p marta, keyin bu nusxa bir marta rang-barang bo'lishi kutilmoqda. Shunga qaramay, e'tibor bering p kichik bo'lsa, agar ko'rsatilgan bo'lsa ${ displaystyle | V_ {H} | = O ( log V)}$, p faqat polinomial kichikdir. Grafik berilgan holda yana algoritm mavjud deylik G va har bir tepalikni xaritada aks ettiruvchi rang G biriga k ranglar, rang-barang nusxasini topadi H, agar mavjud bo'lsa, ba'zi bir ish vaqtida O(r). Keyin uning nusxasini topish uchun kutilgan vaqt H yilda G, agar mavjud bo'lsa, mavjud ${ displaystyle O ({ tfrac {r} {p}})}$.

Ba'zida rang-baranglikning cheklangan versiyasidan foydalanish maqsadga muvofiqdir. Masalan, tsikllarni topish kontekstida planar grafikalar, yaxshi rangli tsikllarni topadigan algoritmni ishlab chiqish mumkin. Bu erda tsikl yaxshi rangga ega, agar uning tepalari ketma-ket ranglar bilan ranglangan bo'lsa.

Misol

Masalan, uzunlikning oddiy tsiklini topish mumkin k grafada G = (V, E).

Tasodifiy rang berish usulini qo'llagan holda, har bir oddiy tsiklning ehtimoli bor ${ displaystyle k! / k ^ {k}> e ^ {- k}}$ rang-barang bo'lish, chunki bor ${ displaystyle k ^ {k}}$ rang berish usullari k tsikldagi tepaliklar, ular orasida bor ${ displaystyle k!}$ rang-barang hodisalar. Keyin tasodifiy rangli grafikada rangli tsikllarni topish uchun algoritm (keyingi tavsif) ishlatilishi mumkin G o'z vaqtida ${ displaystyle O (V ^ { omega})}$, qayerda ${ displaystyle omega}$ matritsani ko'paytirish doimiysi. Shuning uchun, bu kerak ${ displaystyle e ^ {k} cdot O (V ^ { omega})}$ uzunlikning oddiy tsiklini topish uchun umumiy vaqt k yilda G.

Rangli tsikllarni qidirish algoritmi avval barcha juft tepaliklarni topish orqali ishlaydi V oddiy uzunlik yo'li bilan bog'langan k − 1va keyin har bir juftlikdagi ikkita tepaning bir-biriga bog'langanligini tekshiring. Bo'yash funktsiyasi berilgan v : V → {1, ..., k} rangli grafikaga G, ranglar to'plamining barcha bo'limlarini sanab o'ting {1, ..., k} ikkita kichik guruhga C₁, C₂ hajmi ${ displaystyle k / 2}$ har biri. Yozib oling V ga bo'lish mumkin V₁ va V₂ shunga ko'ra, va ruxsat bering G₁ va G₂ tomonidan induktsiya qilingan subgrafalarni belgilang V₁ va V₂ navbati bilan. Keyin, rekursiv ravishda uzunlikning rang-barang yo'llarini toping ${ displaystyle k / 2-1}$ har birida G₁ va G₂. Mantiqiy matritsa deylik A₁ va A₂ har bir tepalik juftligining bog'lanishini ifodalaydi G₁ va G₂ navbati bilan rangli yo'l bilan va ruxsat bering B ning tepalari orasidagi qo'shni munosabatlarni tavsiflovchi matritsa bo'ling V₁ va ular V₂, boolean mahsulot ${ displaystyle A_ {1} BA_ {2}}$ barcha juft tepaliklarni beradi V uzunlikdagi rangli yo'l bilan bog'langan k − 1. Shunday qilib, matritsani ko'paytirishning rekursiv munosabati quyidagicha ${ displaystyle t (k) leq 2 ^ {k} cdot t (k / 2)}$, bu ish vaqtini beradi ${ displaystyle 2 ^ {O (k)} cdot V ^ { omega} = O (V ^ { omega})}$. Garchi bu algoritm rangli yo'lning faqat so'nggi nuqtalarini topsa-da, Alon va Naorning yana bir algoritmi^[4] unga rang-barang yo'llarni topadigan narsa kiritilishi mumkin.

Derandomizatsiya

The derandomizatsiya ranglarni kodlash grafikaning mumkin bo'lgan ranglarini sanab o'tishni o'z ichiga oladi G, shunday qilib rang berishning tasodifiyligi G endi talab qilinmaydi. Maqsadli subgraf uchun H yilda G kashf etilishi uchun, ro'yxatga olishda kamida bitta misol bo'lishi kerak H rang-barang. Bunga erishish uchun, a k- mukammal oila F xash funktsiyalarining {1, ..., |V|} ga {1, ..., k} etarli. Ta'rifga ko'ra, F bu k- har bir kichik guruh uchun mukammal bo'lsa S ning {1, ..., |V|} qayerda ${ displaystyle | S | = k}$, xash funktsiyasi mavjud h yilda F shu kabi h : S → {1, ..., k} bu mukammal. Boshqacha qilib aytganda, ichida xash funktsiyasi mavjud bo'lishi kerak F har qanday berilgan rangni k tepaliklar k aniq ranglar.

Bunday a ni tuzishda bir nechta yondashuvlar mavjud k- mukammal xash oilasi:

1. Eng yaxshi aniq qurilish Moni Naor, Leonard J. Shulman va Aravind Srinivasan,^[5] bu erda katta oila ${ displaystyle e ^ {k} k ^ {O ( log k)} log | V |}$ olinishi mumkin. Ushbu qurilish maqsadli subgrafning asl subgrafni topish muammosida mavjud bo'lishini talab qilmaydi.
2. Tomonidan yana bir aniq qurilish Jeanette P. Shmidt va Alan Sigel^[6] katta oilani beradi ${ displaystyle 2 ^ {O (k)} log ^ {2} | V |}$.
3. Ning asl qog'ozida paydo bo'lgan yana bir qurilish Noga Alon va boshq.^[2] birinchi qurish orqali olinishi mumkin a k- xaritalarni mukammal tasvirlaydigan oila {1, ..., |V|} ga {1, ..., k²}, keyin boshqasini qurish k- xaritalarni mukammal tasvirlaydigan oila {1, ..., k²} ga {1, ..., k}. Birinchi qadamda bunday oilani qurish mumkin 2njurnal k deyarli tasodifiy bitlar 2log k- mustaqil ravishda,^[7][8] va bu tasodifiy bitlarni yaratish uchun zarur bo'lgan namunaviy maydon juda kichik bo'lishi mumkin ${ displaystyle k ^ {O (1)} log | V |}$. Ikkinchi bosqichda uni Janette P. Shmidt va Alan Sigel ko'rsatdilar^[6] bunday kattaligi k- mukammal oila bo'lishi mumkin ${ displaystyle 2 ^ {O (k)}}$. Binobarin, k- har ikki qadamdan mukammal oilalar, a k- katta oilalar ${ displaystyle 2 ^ {O (k)} log | V |}$ bu xaritalar {1, ..., |V|} ga {1, ..., k} olinishi mumkin.

Subgrafadagi har bir tepalik ketma-ket ranglangan yaxshi ranglarni derandomizatsiyalash holatida, a k- dan hash funktsiyalarining mukammal oilasi {1, ..., |V|} ga {1, ..., k!} kerak. Etarli k- mukammal xarita qaysi xaritadan {1, ..., |V|} ga {1, ..., k^k} yuqoridagi 3-yondashuvga o'xshash tarzda qurilishi mumkin (birinchi qadam). Xususan, u foydalanish orqali amalga oshiriladi nkjurnal k deyarli tasodifiy bitlar kjurnal k mustaqil va natijada olingan hajm k- mukammal oila bo'ladi ${ displaystyle k ^ {O (k)} log | V |}$.

Ranglarni kodlash usulini derandomizatsiya qilish osonlikcha parallel bo'lib, natijada samarali bo'ladi Bosimining ko'tarilishi algoritmlar.

Ilovalar

So'nggi paytlarda ranglarni kodlash bioinformatika sohasida katta e'tiborni tortdi. Masalan, aniqlash signalizatsiya yo'llari yilda oqsil-oqsilning o'zaro ta'siri (PPI) tarmoqlari. Yana bir misol - ni kashf qilish va hisoblash motiflar PPI tarmoqlarida. Ikkalasini ham o'rganish signalizatsiya yo'llari va motiflar organizmlar orasidagi ko'plab biologik funktsiyalar, jarayonlar va tuzilmalarning o'xshashligi va farqlarini chuqurroq anglashga imkon beradi.

To'planishi mumkin bo'lgan juda ko'p miqdordagi gen ma'lumotlari tufayli yo'llar yoki motiflarni qidirish juda ko'p vaqt talab qilishi mumkin. Biroq, ranglarni kodlash usulidan foydalangan holda, motiflar yoki signalizatsiya yo'llari ${ displaystyle k = O ( log n)}$ tarmoqdagi tepaliklar G bilan n tepaliklarni polinom vaqtida juda samarali topish mumkin. Shunday qilib, bu bizga PPI tarmoqlarida yanada murakkab yoki kattaroq tuzilmalarni o'rganishga imkon beradi.

Qo'shimcha o'qish

• Alon, N .; Dao, P .; Hajirasouliha, men.; Xormozdiari, F.; Sahinalp, S. C. (2008). "Ranglarni kodlash orqali biomolekulyar tarmoq motiflarini hisoblash va kashf etish". Bioinformatika. 24 (13): i241 – i249. doi:10.1093 / bioinformatika / btn163. PMC  2718641. PMID  18586721.
• Xyufner, F.; Vernik, S.; Zichner, T. (2008). "Yo'lni aniqlash signalizatsiya dasturlari bilan ranglarni kodlash algoritmi muhandisligi". Algoritmika. 52 (2): 114–132. CiteSeerX  10.1.1.68.9469. doi:10.1007 / s00453-007-9008-7.

Adabiyotlar