बबल सॉर्ट से लेकर जेनेटिक एल्गोरिदम तक

यह लेख आनुवांशिक एल्गोरिदम क्या है, इसका एक संक्षिप्त अवलोकन है। जैव सूचना विज्ञान में एक शुरुआत होने के नाते, मैं उन चीजों से शुरू होता हूं जो तकनीकी विशिष्टताओं में लोगों के करीब और समझने योग्य हैं: एल्गोरिदम को छांटना, फिर मैं आनुवंशिक प्रोग्रामिंग की एक समस्या का वर्णन करने और बायोलॉजिस्ट का अर्थ एल्गोरिदम से करूंगा।

छंटाई

मुझे लगता है कि प्रत्येक प्रोग्रामर का मानना ​​है कि वह इस विषय के बारे में जानता है, यदि सभी नहीं, तो लगभग सब कुछ। हो सकता है कि इस समय ऐसा हो, और इन पंक्तियों के पाठक ने डोनाल्ड नुथ द्वारा "द आर्ट ऑफ़ प्रोग्रामिंग" के तीसरे खंड का अध्ययन किया हो। लेकिन चलो एक प्रयोग करें: अपने पसंदीदा एल्गोरिदम को लें और इसे कागज के एक टुकड़े पर पेंसिल के साथ लागू करने का प्रयास करें। अगर कोई पसंदीदा एल्गोरिथ्म नहीं है, तो मैं बुलबुले द्वारा छँटाई करने का सुझाव देता हूं। यह काम किया? मुझे बार-बार इंटरव्यू में इस कार्य की पेशकश की गई है, लेकिन प्रस्तावित विकल्पों में से कुछ श्रमिक थे, और केवल कुछ "बबल" दिखाई दिए। हाल ही में मैं पायथन पर एक व्याख्यान नोट्स देखने के लिए हुआ, जहां शिक्षक, बुलबुला द्वारा छंटाई की आड़ में, निम्नलिखित कोड देता है:

def bubble_sort(numbers): for first in range(0, len(numbers)-1): for second in range(first+1, len(numbers)): if numbers[first] > numbers[second]: numbers[first], numbers[second] = numbers[second], numbers[first] 

एल्गोरिथ्म काम कर रहा है, इसे क्रमबद्ध किया जाएगा, लेकिन यह स्पष्ट रूप से "बुलबुला" नहीं है। थोड़े खिंचाव के साथ, इसे चयन द्वारा सॉर्टिंग कहा जा सकता है, लेकिन यहां एक दुर्भाग्यपूर्ण निरीक्षण है: चयन द्वारा छंटनी का लाभ प्रतिस्थापन की संख्या को कम करना है, अर्थात, जब हम स्वैप तत्वों को स्वैप करते हैं, तो उस समय की संख्या O (n) तक सीमित होनी चाहिए, जो ऊपर दिए गए कोड में नहीं देखी गई है।

एल्गोरिदम के विषय पर एक बातचीत में, त्वरित छंटाई के सवाल को फ्लिप करना दिलचस्प हो सकता है। एक नियम के रूप में, लोग आसानी से इस सवाल का जवाब देते हैं कि यह कितना अच्छा है: यह औसत पर एक अच्छा एल्गोरिथम जटिलता है, और अतिरिक्त मेमोरी की आवश्यकता की कमी (वे आमतौर पर स्टैक के बारे में भूल जाते हैं)। लेकिन फिर यह पूछना दिलचस्प है कि यह क्यों खराब है, क्योंकि उसके अलावा, कई अन्य एल्गोरिदम हैं? इस सवाल के जवाब बहुत अधिक दुर्लभ और नीरस हैं। और क्या आप त्वरित क्रम के लिए नाम नुकसान कर सकते हैं?

मेरी खुशी के लिए, कभी-कभी विदेशी तरीकों के ज्ञान का प्रदर्शन करने वाले सौंदर्यशास्त्र से मिलना संभव है, उदाहरण के लिए, सूक्ति प्रकार।
निष्कर्ष:
1. यदि आप इंटरव्यू के लिए एस्थेट में उत्तीर्ण होना चाहते हैं, तो थोड़े-थोड़े ज्ञात तरीकों को सीखें;
2. यदि आप स्वयं साक्षात्कार स्वीकार करते हैं, तो एक-दूसरे से अलग-अलग तरीकों को अलग करने में सक्षम हों, अन्यथा आप उम्मीदवार को कभी नहीं जान सकते, निम्नलिखित पैराग्राफ 1 ...

पैनकेक सॉर्ट करें

ऊपर दिए गए सुझावों के बाद, हम एक ऐसे कार्य पर विचार करते हैं जिसका व्यावहारिक अर्थ नहीं है, लेकिन एक सैद्धांतिक दृष्टिकोण से दिलचस्प है: पैनकेक छंटाई। इसकी अव्यवहारिकता इस तथ्य में निहित है कि इस एल्गोरिथ्म में तत्वों की तुलना की संख्या को बिल्कुल भी ध्यान में नहीं रखा गया है (यह माना जाता है कि ये ऑपरेशन बहुत सस्ते और तेज हैं), और एकमात्र ऑपरेशन जिसकी कीमत है वह सॉर्ट किए गए "पेनकेक्स" के ढेर के ऊपर फ्लिप करने के लिए है। बेशक, शुरू में उन्हें यादृच्छिक क्रम में व्यवस्थित किया जाता है, और वांछित परिणाम हनोई का एक प्रकार का टॉवर है, जब बड़े व्यास के पेनकेक्स नीचे झूठ बोलते हैं, और छोटे शीर्ष पर स्थित होते हैं।

इस समस्या के बारे में, मैं दो दिलचस्प तथ्यों पर ध्यान देना चाहूंगा। सबसे पहले, एक पर्याप्त प्रभावी (यद्यपि गैर-इष्टतम) समाधान खोजने का तरीका कुख्यात बिल गेट्स द्वारा एक समय में प्रस्तावित किया गया था, जबकि वह अभी भी एक छात्र था। 1979 में प्रस्तावित यह एल्गोरिदम 2008 तक सबसे अधिक कुशल रहा, जब परिणाम को पार कर लिया गया। दूसरे, जैसा कि बाद में साबित हुआ, इष्टतम समाधान खोजने की समस्या एनपी-पूर्ण वाले वर्ग की है। गेट्स और उनके नेता क्रिस्टोस पापादिमित्रिउ ने समस्या का एक जटिल संस्करण भी प्रस्तावित किया, जिसे जली हुई पैनकेक समस्या के रूप में जाना जाता है।

जले हुए पेनकेक्स की समस्या

समस्या के इस रूप में, प्रत्येक तत्व, आकार के अलावा, एक द्विआधारी विशेषता "दिशा" भी है, अर्थात, प्रत्येक "पैनकेक" के लिए एक तरफ जला दिया जाता है और दूसरा रोसी होता है; समस्या को हल करने का परिणाम आकार के अनुसार एक स्टैक है, लेकिन, इसके अलावा, सभी "पेनकेक्स" नीचे की तरफ जलाए जाते हैं। विवरण में जाने के बिना, हम कहते हैं कि यह समस्या एनपी-पूर्ण है, और यह कि सामान्य मामले में इसके पर्याप्त प्रभावी लेकिन गैर-इष्टतम समाधान ज्ञात हैं। हालांकि, डेटा पर प्रतिबंध हैं, जिसके पूरा होने पर कार्य बहुपद बन जाता है। इस समस्या के लिए, ऐसे डेटा सरल क्रमपरिवर्तन हैं । यह समझने के लिए कि यह क्या है, 1 से 7: 2 6475 13. संख्याओं के क्रमचय पर विचार करें। ध्यान दें कि बोल्ड में अनुक्रम 4 से 7 की संख्याओं का क्रमांकन है (जिसे ब्लॉक कहा जाता है)। सरल क्रमपरिवर्तन वे होते हैं, जहाँ कोई नॉनट्रिविअल ब्लॉक (लंबाई 1 और एन के ब्लॉक) नहीं होते हैं।

समस्या के आलंकारिक सूत्रीकरण के पीछे, जब तत्वों को जले हुए पेनकेक्स द्वारा दर्शाया जाता है, तो इस तथ्य को समझना मुश्किल है कि इसका जैविक महत्व है। हालांकि, एक सामान्य उत्परिवर्तन एक डीएनए अणु में एक फ्लिप है, और यदि आप एक अणु को दूसरे (छोटे बिंदु म्यूटेशन पर विचार किए बिना) में बदलने के लिए आवश्यक फ़्लिप की न्यूनतम संख्या की गणना करते हैं, तो आप मोटे तौर पर जीवों की आत्मीयता का अनुमान लगा सकते हैं। उदाहरण के लिए, मानव और माउस जीनोम को केवल 120 वैश्विक म्यूटेशन द्वारा अलग किया जाता है; मैं मानता हूं, मैं मानता था कि इन प्रकारों के बीच बहुत अधिक अंतर है ...

जले हुए पेनकेक्स की समस्या को हल करने के लिए आनुवंशिक एल्गोरिथ्म

तुलनात्मक जीनोमिक्स में, एल्गोरिथ्म का उपयोग विश्लेषणात्मक रूप से उन उत्परिवर्तन की संख्या को खोजने के लिए किया जाता है जो अलग-अलग जीवों को करते हैं, लेकिन आइए समस्या को एक अलग प्रक्षेपण में देखें। अब हम विश्लेषणात्मक समस्या के समाधान को लक्ष्य के रूप में घोषित करेंगे, और हम जीवित जीवों और उनमें होने वाली प्रक्रियाओं को इसके समाधान के लिए एक उपकरण बनाएंगे।

जैसा कि आप जानते हैं, बैक्टीरिया आबादी की एक घातीय वृद्धि प्रदान करने में सक्षम हैं, यदि उन्हें आवश्यक शर्तों के साथ प्रदान किया जाता है; बेशक, थोड़ी देर बाद बैक्टीरिया कॉलोनियों में पोषक तत्व माध्यम नहीं होगा, अन्य कारक भी दिखाई देंगे जो कॉलोनी के विकास को प्रभावित करते हैं, लेकिन इसमें समय लगता है। प्रयोगात्मक रूप से, हम किसी दिए गए प्रजाति के बैक्टीरिया को डीएनए के एक हिस्से के व्युत्क्रम से जुड़े वैश्विक उत्परिवर्तन में प्रकट होने में लगने वाले औसत समय का पता लगा सकते हैं।

अब बैक्टीरिया के लिए कार्य निर्धारित करते हैं। हम आनुवंशिक रूप से उनमें से एक को संशोधित करते हैं (जीवविज्ञानी ऐसे प्रयोगों में एस्चेरिचिया कोलाई का उपयोग करना पसंद करते हैं), जहां हम एंटीबायोटिक प्रतिरोध जीन को कई भागों में विभाजित करते हैं और उन्हें एक साथ मिलाते हैं, न केवल क्रम बदलते हैं, बल्कि कुछ टुकड़ों की दिशा भी बदलते हैं। इस प्रकार, हमारे मामले में जीन का प्रत्येक उल्टा और पुनर्व्यवस्थित टुकड़ा "जला हुआ पैनकेक" होगा।

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

क्या एक पैनकेक फ्लिप एक समस्या को हल करने के लिए पर्याप्त है? हम खतरनाक माहौल में कॉलोनी का हिस्सा रखकर आसानी से इसे सत्यापित कर सकते हैं। एंटीबायोटिक में लगाए गए बैक्टीरिया जीवित नहीं थे, और हम शेष लोगों की निगरानी करना जारी रखते हैं। दो या तीन और अवधि बीतेंगी, और अंत में, एंटीबायोटिक में रखे बैक्टीरिया के समूह में, वे जीवित रहेंगे। "सामूहिक मन" कार्य के साथ मुकाबला किया!

परिणाम

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