الترميز اللوني

في علوم الحاسوب ونظرية الرسوم البيانية ، يشير مصطلح "الترميز اللوني" إلى تقنية خوارزمية مفيدة في اكتشاف أنماط الشبكات . على سبيل المثال، يمكن استخدامه للكشف عن مسار بسيط بطول k في رسم بياني مُعطى . خوارزمية الترميز اللوني التقليدية احتمالية ، ولكن يمكن إزالة العشوائية منها دون زيادة كبيرة في وقت التشغيل.

ينطبق الترميز اللوني أيضًا على اكتشاف الدورات ذات الطول المحدد، وبشكل عام ينطبق على مشكلة تماثل الرسم البياني الفرعي (وهي مشكلة كاملة من نوع NP )، حيث ينتج عنها خوارزميات ذات وقت متعدد الحدود عندما يكون لنمط الرسم البياني الفرعي الذي يحاول اكتشافه عرض شجرة محدود .

تم اقتراح طريقة الترميز اللوني وتحليلها في عام 1994 من قبل نوغا ألون ، ورافائيل يوستر ، وأوري زويك . ^{[ 1 ] [ 2 ]}

يمكن الحصول على النتائج التالية من خلال طريقة الترميز اللوني:

• لكل ثابت k ، إذا كان الرسم البياني G = ( V , E ) يحتوي على دورة بسيطة بحجم k ، فإنه يمكن إيجاد مثل هذه الدورة في:
  • ${\displaystyle O(|V|^{\أوميغا })}$الوقت المتوقع، أو
  • ${\displaystyle O(|V|^{\أوميغا }\log |V|)}$أسوأ حالة زمنية، حيث ω هو أس ضرب المصفوفات . ^{[ 3 ]}
• لكل ثابت k ، ولكل رسم بياني G = ( V , E ) ينتمي إلى أي عائلة رسوم بيانية مغلقة جزئياً غير تافهة (مثل الرسم البياني المستوي )، إذا كان G يحتوي على دورة بسيطة بحجم k ، فإنه يمكن العثور على هذه الدورة في:
  • الوقت المتوقع O ( V ) ، أو
  • O ( V log V ) أسوأ وقت في الحالة.
• إذا كان الرسم البياني G = ( V , E ) يحتوي على رسم بياني فرعي متماثل مع رسم بياني محدود العرض الشجري يحتوي على O (log 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 أصبحت ملونة باحتمالية غير صفرية p . يترتب على ذلك مباشرةً أنه إذا تكرر التلوين العشوائي 1 / p مرة ، فمن المتوقع أن تصبح هذه النسخة ملونة مرة واحدة. لاحظ أنه على الرغم من أن p صغيرة، فقد ثبت أنه إذا${\displaystyle |V_{H}|=O(\log |V|)}$، و p صغيرة جدًا. لنفترض مجددًا وجود خوارزمية، إذا أعطيت رسمًا بيانيًا G وتلوينًا يربط كل رأس من رؤوس G بأحد الألوان k ، فإنها تجد نسخة من H الملونة ، إن وجدت، خلال زمن تشغيل O ( r ) . عندئذٍ، يكون الزمن المتوقع لإيجاد نسخة من H في G ، إن وجدت، هو${\displaystyle O({\tfrac {r}{p}})}$.

أحيانًا يكون من المستحسن استخدام نسخة أكثر تقييدًا من التلوين. على سبيل المثال، في سياق إيجاد الدورات في الرسوم البيانية المستوية ، يمكن تطوير خوارزمية لإيجاد الدورات ذات التلوين الجيد. هنا، تُعتبر الدورة ذات تلوين جيد إذا كانت رؤوسها ملونة بألوان متتالية.

تتضمن عملية إزالة العشوائية من ترميز الألوان حصر التلوينات الممكنة للرسم البياني G ، بحيث لا تكون عشوائية تلوين G مطلوبة. ولكي يكون الرسم البياني الفرعي H في G قابلاً للاكتشاف، يجب أن يتضمن الحصر حالة واحدة على الأقل يكون فيها H ملونًا. ولتحقيق ذلك، يكفي حصر عائلة F من دوال التجزئة المثالية من الرتبة k من المجموعة {1، ...، | V |} إلى المجموعة {1، ...، k } . وبحسب التعريف، تكون F مثالية من الرتبة k إذا كان لكل مجموعة جزئية S من المجموعة {1، ...، | V |} حيث${\displaystyle |S|=k}$يوجد دالة تجزئة h في F بحيث تكون h  : S → {1, ..., k } مثالية . بعبارة أخرى، يجب أن توجد دالة تجزئة في F تُلوّن أي k رأسًا مُعطى بـ k لونًا مختلفًا.

توجد عدة طرق لإنشاء عائلة تجزئة مثالية من النوع k :

1. أفضل بناء صريح هو من تأليف موني ناور ، وليونارد ج. شولمان ، وأرافيند سرينيفاسان ، ^{[ 5 ]} حيث عائلة من الحجم${\displaystyle e^{k}k^{O(\log k)}\log |V|}$يمكن الحصول عليها. لا يتطلب هذا البناء وجود الرسم البياني الفرعي المستهدف في مسألة إيجاد الرسم البياني الفرعي الأصلية.
2. يُنتج بناء صريح آخر من قِبل جانيت ب. شميدت وآلان سيجل ^{[ 6 ]} عائلة من الحجم${\displaystyle 2^{O(k)}\log ^{2}|V|}$.
3. يمكن الحصول على بنية أخرى وردت في الورقة الأصلية لنوجا ألون وآخرون ^{[ 2 ]} من خلال بناء عائلة مثالية من الرتبة k تربط المجموعة ^{ 1 ، ...، | V |} بالمجموعة {1، ...، k2 }، ثم بناء عائلة مثالية أخرى من الرتبة k تربط المجموعة {1، ...، ^k2 } بالمجموعة { 1، ...، k }. في الخطوة الأولى، من الممكن بناء هذه العائلة باستخدام 2n log k بت عشوائية مستقلة تقريبًا بمقدار 2log k بت، ^{[ 7 ] [ 8 ]} ويمكن أن تكون مساحة العينة اللازمة لتوليد هذه البتات العشوائية صغيرة جدًا .${\displaystyle k^{O(1)}\log |V|}$في الخطوة الثانية، أوضحت جانيت ب. شميدت وآلان سيجل ^{[ 6 ]} أن حجم هذه العائلة المثالية من الرتبة k يمكن أن يكون${\displaystyle 2^{O(k)}}$وبالتالي، من خلال تجميع العائلات المثالية من الدرجة k من كلا الخطوتين، نحصل على عائلة مثالية من الدرجة k بحجم${\displaystyle 2^{O(k)}\log |V|}$يمكن الحصول على الخرائط من {1، ...، | V |} إلى {1، ...، k } .

في حالة إزالة العشوائية من التلوين الجيد، حيث يتم تلوين كل رأس في الرسم البياني الفرعي بالتتابع، يلزم وجود عائلة مثالية من دوال التجزئة من النوع k من المجموعة {1، ...، | V |} إلى المجموعة {1، ...، k !} . يمكن إنشاء عائلة مثالية كافية من النوع k تربط من المجموعة {1، ...، | V |} إلى المجموعة {1، ...، k ^! } بطريقة مشابهة للنهج 3 أعلاه (الخطوة الأولى). على وجه الخصوص، يتم ذلك باستخدام nk log k بت عشوائي مستقلة تقريبًا بمقدار k log k ، وسيكون حجم العائلة المثالية الناتجة من النوع k هو${\displaystyle k^{O(k)}\log |V|}$.

يمكن بسهولة موازاة عملية إزالة العشوائية من طريقة ترميز الألوان، مما ينتج عنه خوارزميات NC فعالة.

حظي الترميز اللوني باهتمام كبير مؤخرًا في مجال المعلوماتية الحيوية . ومن الأمثلة على ذلك الكشف عن مسارات الإشارات في شبكات تفاعل البروتين-بروتين . ومثال آخر هو اكتشاف عدد الأنماط في هذه الشبكات وحسابها. وتتيح دراسة كل من مسارات الإشارات والأنماط فهمًا أعمق لأوجه التشابه والاختلاف بين العديد من الوظائف والعمليات والبنى البيولوجية في الكائنات الحية.

نظراً للكم الهائل من بيانات الجينات التي يمكن جمعها، فإن البحث عن المسارات أو الأنماط قد يستغرق وقتاً طويلاً. ومع ذلك، من خلال استغلال طريقة الترميز اللوني، يمكن تحديد الأنماط أو مسارات الإشارات ذات${\displaystyle k=O(\log n)}$يمكن إيجاد رؤوس الشبكة G التي تحتوي على n رأسًا بكفاءة عالية في وقت متعدد الحدود. وهذا يُمكّننا من استكشاف هياكل أكثر تعقيدًا أو أكبر حجمًا في شبكات تفاعل البروتين-بروتين.

• ألون، ن.؛ داو، ب.؛ حاجيراسوليها، إ.؛ هرمزدياري، ف.؛ شاهينالب، س. س. (2008). " عدّ واكتشاف أنماط الشبكة الجزيئية الحيوية باستخدام الترميز اللوني" . المعلوماتية الحيوية . 24 (13): i241– i249. doi : 10.1093/bioinformatics/btn163 . PMC 2718641. PMID 18586721 .  
• هوفنر، ف.؛ فيرنيكه، س.؛ زيشنر، ت. (2008). "هندسة الخوارزميات لترميز الألوان مع تطبيقات في الكشف عن مسارات الإشارات". Algorithmica . 52 (2): 114-132 . CiteSeerX 10.1.1.68.9469 . doi : 10.1007/s00453-007-9008-7 . S2CID 81069 .