एन के मॉडल

एनके (NK) मॉडल एक गणितीय मॉडल है जिसे इसके प्राथमिक आविष्कारक स्टुअर्ट कॉफ़मैन ने एक ''ट्यूनेबली रुग्गड़'' फिटनेस परिदृश्य के रूप में वर्णित किया है। ''ट्यूनेबल रुग्गड़नेस'' ट्यून करने योग्य असभ्यता इस अंतर्ज्ञान को पकड़ती है कि परिदृश्य के समग्र आकार और इसकी स्थानीय ''पहाड़ियों और घाटियों'' की संख्या दोनों को इसके दो मापदंडों में परिवर्तन के माध्यम से समायोजित किया जा सकता है, $N$ और $K$, साथ $N$ विकास की एक श्रृंखला की लंबाई होने के नाते और $K$ भूदृश्य की असभ्यता के स्तर का निर्धारण है।

एनके मॉडल ने विभिन्न प्रकार के क्षेत्रों में आवेदन पाया है, जिसमें विकासवादी जीव विज्ञान, इम्मुनोलोगि, संयुक्त अनुकूलन, तकनीकी विकास और जटिल प्रणालियों का सैद्धांतिक अध्ययन सम्मिलित है। मॉडल को संगठनात्मक सिद्धांत में भी अपनाया गया था, जहां इसका उपयोग यह वर्णन करने के लिए किया जाता है कि कैसे एक एजेंट-आधारित मॉडल स्वयं की विभिन्न विशेषताओं में हेरफेर करके एक परिदृश्य की खोज कर सकता है। उदाहरण के लिए, एक एजेंट एक संगठन हो सकता है, पहाड़ियाँ और घाटियाँ लाभ (अर्थशास्त्र) (या उसमें परिवर्तन) का प्रतिनिधित्व करती हैं, और परिदृश्य पर आंदोलन के लिए संगठनात्मक निर्णयों की आवश्यकता होती है (जैसे कि उत्पाद लाइनें जोड़ना या संगठनात्मक संरचना में बदलाव करना), जो परस्पर क्रिया (इंटरैक्ट) करते हैं एक दूसरे के साथ और जटिल तरीके से लाभ को प्रभावित करते हैं।

मॉडल का प्रारंभिक संस्करण, जिसे केवल सबसे सहज माना जाता था ($K=0$) और सबसे  रुग्गड़ (ऊबड़-खाबड़) ($K=N-1$) परिदृश्य, कॉफ़मैन और लेविन (1987) में प्रस्तुत किया गया था। जिस मॉडल को वर्तमान में जाना जाता है वह पहली बार कॉफ़मैन और वेनबर्गर (1989) में दिखाई दिया।

मॉडल ने कॉम्बिनेटरियल ऑप्टिमाइज़ेशन में व्यापक ध्यान आकर्षित किया है, इसका एक कारण यह है कि यह तथाकथित एनपी-पूर्ण समस्या का एक विशेष रूप से सरल उदाहरण है। जिसका अर्थ है कि वैश्विक ऑप्टिमा खोजना कठिन है। हाल ही में, यह दिखाया गया कि K > 1 के लिए NK मॉडल भी पीएलएस (जटिलता)| पीएलएस-पूर्ण है जिसका मतलब है कि, सामान्य तौर पर, स्थानीय फिटनेस ऑप्टिमा भी ढूंढना कठिन है। ओपन-एंडेड विकास के अध्ययन के लिए इसके परिणाम हैं।

प्रोटोटाइपिक उदाहरण: प्लाज्मिड फिटनेस

प्लास्मिड कुछ कोशिकाओं के अंदर डीएनए का एक छोटा चक्र है जो अपने मेजबान कोशिकाओं से स्वतंत्र रूप से दोहरा सकता है। मान लीजिए हम प्लास्मिड की उपयुक्तता का अध्ययन करना चाहते हैं।

सरलता के लिए, हम एक प्लास्मिड को हमेशा एक ही क्रम में N संभावित जीन की अंगूठी के रूप में मॉडल करते हैं, और प्रत्येक में दो संभावित अवस्थाएं हो सकती हैं (सक्रिय या निष्क्रिय, प्रकार X या प्रकार Y, आदि...)। फिर प्लास्मिड को लंबाई N के साथ एक बाइनरी कोड स्ट्रिंग द्वारा मॉडल किया जाता है, और इसी तरह फिटनेस फ़ंक्शन होता है $F:\{0,1\}^{N}\to \mathbb {R}$.

सबसे सरल मॉडल में जीन एक-दूसरे के साथ परस्पर क्रिया (इंटरैक्ट) नहीं करते, और इसलिए हम प्राप्त करते हैं

$$F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1})+f_{2}(S_{2})+\cdots +f_{N}(S_{N})$$

जहां प्रत्येक $f_{i}(S_{i})$ जीन की फिटनेस में योगदान को दर्शाता है $S_{i}$ स्थान पर $i$.

एपिस्टासिस को मॉडल करने के लिए, हम एक अन्य कारक K का परिचय देते हैं, अन्य जीनों की संख्या जिनके साथ एक जीन इंटरैक्ट करता है। यह मानना ​​उचित है कि एक प्लास्मिड पर, दो जीन इंटरैक्ट करते हैं यदि वे आसन्न हों, इस प्रकार देते हैं

$$F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1},S_{2})+f_{2}(S_{2},S_{3})+\cdots +f_{N-1}(S_{N-1},S_{N})+f_{N}(S_{N},S_{1})$$

उदाहरण के लिए, जब K = 1, और N = 5,

$F(00101)=f_{1}(0,0)+f_{2}(0,1)+f_{3}(1,0)+f_{4}(0,1)+f_{5}(1,0)$

एनके मॉडल स्वेच्छाचारी से परिमित K, N की अनुमति देकर, साथ ही जीन की आसन्नता की स्वेच्छाचारी परिभाषा की अनुमति देकर इसे सामान्य बनाता है (जीन आवश्यक रूप से एक वृत्त या रेखा खंड पर स्थित नहीं होते हैं)।

गणितीय परिभाषा

एनके मॉडल एक सांयोगिक चरण स्थान को परिभाषित करता है, जिसमें लंबाई की प्रत्येक स्ट्रिंग (किसी दिए गए वर्णमाला से चुनी गई) सम्मिलित होती है $N$l इस खोज स्थान में प्रत्येक स्ट्रिंग के लिए, एक अदिश (गणित) मान (जिसे फिटनेस कार्य कहा जाता है) परिभाषित किया गया है। यदि स्ट्रिंग के बीच एक दूरी मीट्रिक (गणित) परिभाषित की जाती है, तो परिणामी संरचना एक परिदृश्य है।

फिटनेस मूल्यों को मॉडल के विशिष्ट अवतारण के अनुसार परिभाषित किया गया है, लेकिन एनके मॉडल की मुख्य विशेषता यह है कि किसी दिए गए स्ट्रिंग की फिटनेस $S$ प्रत्येक स्थान से योगदान का योग है $f_{i}(S)$ स्ट्रिंग में:

$F(S)=\sum _{i}{\tilde {f}}_{i}(S),$

और सामान्यतः प्रत्येक लोकस का योगदान उसकी स्थिति और स्थिति पर निर्भर करता है $K$ अन्य लोकी,:

${\tilde {f}}_{i}(S)=f_{i}(S_{i},S_{k_{i1}},\dots ,S_{k_{iK}}),$

जहाँ $k_{ij}$ का सूचकांक है $j$ लोकस का निकटवर्ती $i$.

इसलिए, फिटनेस फ़ंक्शन $f_{i}$ लंबाई K + 1 और स्केलर के स्ट्रिंग के बीच एक मानचित्र (गणित) है, जिसे वेनबर्गर का बाद का काम फिटनेस योगदान कहता है। ऐसे फिटनेस योगदानों को प्रायः कुछ निर्दिष्ट संभाव्यता वितरण से यादृच्छिक रूप से चुना जाता है।

एनके फिटनेस परिदृश्य के दो आयामों का दृश्य। तीर विभिन्न उत्परिवर्तन पथों का प्रतिनिधित्व करते हैं जिनका जनसंख्या फिटनेस परिदृश्य पर विकास करते समय अनुसरण कर सकती है

उदाहरण: स्पिन ग्लास मॉडल

स्पिन ग्लास (प्रचक्रण ग्लास) का 1D आइसिंग मॉडल सामान्यतः इस प्रकार लिखा जाता है

$$H=-\sum _{i=1}^{N}J_{i,i+1}S_{i}S_{i+1}-\mu \sum _{i=1}^{N}h_{i}S_{i}$$

जहाँ $H$ हैमिल्टनियन है, जिसे ऊर्जा के रूप में सोचा जा सकता है। हम इसे K=1 के साथ एनके मॉडल के एक विशेष स्थिति के रूप में दोबारा तैयार कर सकते हैं:

$$H=F(S)=\sum _{i,j}f_{i,j}(S_{i},S_{j})$$

परिभाषित करके

$$f_{i}(S_{i},S_{i+1})=-J_{ij}S_{i}S_{i}-\mu h_{i}S_{i}$$

सामान्य तौर पर, एक वर्गाकार ग्रिड पर m-आयामी आइसिंग मॉडल $\{1,2,...,n\}^{m}$ के साथ एक एनके मॉडल है $N=n^{m},K=m$.

चूँकि K मोटे तौर पर फिटनेस परिदृश्य की ''रुग्गड़नेस'' को मापता है (नीचे देखें), हम देखते हैं कि जैसे-जैसे आइसिंग मॉडल का आयाम बढ़ता है, इसकी असभ्यता भी बढ़ती है।

जब $\mu =0$, यह एडवर्ड्स-एंडरसन मॉडल है, जो बिल्कुल हल करने योग्य है।

शेरिंगटन-किर्कपैट्रिक मॉडल स्पिन के सभी संभावित जोड़े को इंटरैक्ट करने की इजाजत देकर आइसिंग मॉडल को सामान्यीकृत करता है (ग्रिड ग्राफ के बजाय, पूर्ण ग्राफ का उपयोग करें), इस प्रकार यह एक एनके मॉडल भी है $K=N-1$.

केवल जोड़ों के बजाय, स्पिन के सभी संभावित अनुक्रमों को इंटरैक्ट करने की अनुमति देकर, हम अनंत-श्रेणी मॉडल प्राप्त करते हैं, जो एक एनके मॉडल भी है $K=N-1$.

ट्यूनेबल (ट्यून करने योग्य) टोपोलॉजी

एनके मॉडल में ट्यून करने योग्य टोपोलॉजी का चित्रण। नोड्स व्यक्तिगत बाइनरी स्ट्रिंग हैं, किनारे बिल्कुल एक की हैमिंग दूरी के साथ स्ट्रिंग को जोड़ते हैं। (बाएं) एन = 5, के = 0. (केंद्र में) एन = 5, के = 1. (दाएं) एन = 5, के = 2. एक नोड का रंग इसकी फिटनेस को दर्शाता है, लाल मानों में उच्च फिटनेस होती है। हाइपरक्यूब का एम्बेडिंग इसलिए चुना जाता है ताकि फिटनेस अधिकतम केंद्र में हो। ध्यान दें कि K = 0 परिदृश्य उच्च-K मामलों की तुलना में अधिक सहज दिखाई देता है।

K का मान एनके मॉडल में एपिस्टासिस की डिग्री को नियंत्रित करता है, या अन्य लोकी किसी दिए गए लोकस के फिटनेस योगदान को कितना प्रभावित करते हैं। K = 0 के साथ, किसी दिए गए स्ट्रिंग की फिटनेस लोकी के व्यक्तिगत योगदान का एक सरल योग है: गैर-साधारण फिटनेस कार्यों के लिए, एक सार्वत्रिक इष्टतम उपस्थित है और इसका पता लगाना आसान है (यदि f(0) > f(1) तो सभी 0 का जीनोम ), या सभी 1 यदि f(1) > f(0)). गैर-शून्य K के लिए, एक स्ट्रिंग की फिटनेस सबस्ट्रिंग की फिटनेस का योग है, जो सिस्टम की जोमेट्रिकल फ्रसट्रेशन के साथ इंटरैक्ट कर सकती है (ऊपर के उदाहरण में इष्टतम फिटनेस कैसे प्राप्त करें, इस पर विचार करें)। इस प्रकार K बढ़ने से फिटनेस परिदृश्य की रुग्गड़नेस (कठोरता) बढ़ जाती है।

तटस्थ स्थानों के साथ भिन्नताएं

अनावृत एनके मॉडल तटस्थ स्थान की घटना का समर्थन नहीं करता है - अर्थात, एकल उत्परिवर्तन द्वारा जुड़े जीनोम के सेट जिनका फिटनेस मूल्य समान है। आणविक विकास के इस तटस्थ सिद्धांत को सम्मिलित करने के लिए दो अनुकूलन प्रस्तावित किए गए हैं। एनकेपी मॉडल एक पैरामीटर पेश करता है $P$: एक अनुपात $P$ की $2^{K}$ फिटनेस योगदान शून्य पर सेट है, जिससे कई आनुवंशिक रूपांकनों का योगदान ख़राब हो जाता हैl एनकेक्यू मॉडल एक पैरामीटर पेश करता है $Q$ और संभावित फिटनेस योगदान मूल्यों पर विवेकाधिकार लागू करता है ताकि प्रत्येक योगदान में से एक हो $Q$ संभावित मूल्य, फिर से कुछ आनुवंशिक रूपांकनों के योगदान में गिरावट का परिचय देते हैंl अनावृत एनके मॉडल से मेल खाता है $P=0$ और $Q=\infty$ इन मापदंडों के तहत स्थिति हैl

ज्ञात परिणाम

1991 में, वेनबर्गर ने एक विस्तृत विश्लेषण प्रकाशित किया जिस स्थिति में $1<<k\leq N$ और फिटनेस योगदान को यादृच्छिक रूप से चुना जाता है। स्थानीय ऑप्टिमा की संख्या का उनका विश्लेषणात्मक अनुमान बाद में त्रुटिपूर्ण पाया गयाl हालाँकि, वेनबर्गर के विश्लेषण में सम्मिलित संख्यात्मक प्रयोग उनके विश्लेषणात्मक परिणाम का समर्थन करते हैं कि एक स्ट्रिंग की अपेक्षित फिटनेस सामान्यतः लगभग माध्य के साथ वितरित की जाती है

$\mu +\sigma {\sqrt {{2\ln(k+1)} \over {k+1}}}$

और लगभग का एक भिन्नता

${{(k+1)\sigma ^{2}} \over {N[k+1+2(k+2)\ln(k+1)]}}$.

अनुप्रयोग

एनके मॉडल को कई क्षेत्रों में उपयोग मिला है, जिसमें स्पिन ग्लासेज (प्रचक्रण ग्लास) का अध्ययन, सामूहिक समस्या समाधान, विकासवादी जीव विज्ञान में एपिस्टासिस और प्लियोट्रॉपी, और कॉम्बिनेटरियल अनुकूलन है।