Closest string
তাত্ত্বিক কম্পিউটার বিজ্ঞানে, নিকটতম স্ট্রিং হল একটি এনপি-হার্ড গণনামূলক সমস্যা, যা ইনপুট স্ট্রিংয়ের একটি সেটের জ্যামিতিক কেন্দ্র খুঁজে বের করার চেষ্টা করে। "কেন্দ্র" শব্দটি বোঝার জন্য দুটি স্ট্রিংয়ের মধ্যে দূরত্ব নির্ধারণ করা প্রয়োজন। সাধারণত, এই সমস্যাটি হ্যামিং দূরত্বের কথা মাথায় রেখে অধ্যয়ন করা হয়। আনুষ্ঠানিক সংজ্ঞা আরও আনুষ্ঠানিকভাবে, n দৈর্ঘ্য-m স্ট্রিং s1, s2,., sn দেওয়া হলে, নিকটতম স্ট্রিং সমস্যাটি একটি নতুন দৈর্ঘ্য-m স্ট্রিং s চায় যেমন সমস্ত i এর জন্য d (s, si) ≤ k, যেখানে d হ্যামিং দূরত্বকে বোঝায় এবং যেখানে k যতটা সম্ভব ছোট। নিকটতম স্ট্রিং সমস্যার একটি সিদ্ধান্ত সমস্যা সংস্করণ, যা এনপি-সম্পূর্ণ, পরিবর্তে k কে অন্য ইনপুট হিসাবে নেয় এবং সমস্ত ইনপুট স্ট্রিংয়ের হ্যামিং দূরত্ব k এর মধ্যে একটি স্ট্রিং আছে কিনা তা নিয়ে প্রশ্ন করে। নিকটতম স্ট্রিং সমস্যাটিকে সাধারণ 1-কেন্দ্র সমস্যার একটি বিশেষ ক্ষেত্রে দেখা যেতে পারে যেখানে উপাদানগুলির মধ্যে দূরত্ব হ্যামিং দূরত্ব ব্যবহার করে পরিমাপ করা হয়। বায়োইনফরমেটিক্সে, নিকটতম স্ট্রিং সমস্যা হল ডি. এন. এ-তে সংকেত খুঁজে পাওয়ার সমস্যার একটি নিবিড়ভাবে অধ্যয়ন করা দিক। সরলীকরণ এবং তথ্য হ্রাস নিকটতম স্ট্রিংয়ের উদাহরণগুলিতে এমন তথ্য থাকতে পারে যা সমস্যার জন্য প্রয়োজনীয় নয়। কিছু অর্থে, নিকটতম স্ট্রিংয়ের স্বাভাবিক ইনপুটটিতে তথ্য থাকে, যা সমস্যার কঠোরতায় অবদান রাখে না। উদাহরণস্বরূপ, যদি কিছু স্ট্রিং-এ a অক্ষর থাকে, কিন্তু কোনটিতেই z অক্ষর না থাকে, তবে zs-এর মতো সমস্তকে প্রতিস্থাপন করলে মূলত সমতুল্য উদাহরণ পাওয়া যাবে, অর্থাৎঃ পরিবর্তিত দৃষ্টান্তের সমাধান থেকে, মূল সমাধানটি পুনরুদ্ধার করা যেতে পারে এবং তদ্বিপরীত। ইনপুটকে স্বাভাবিক করা যখন একই দৈর্ঘ্যের সমস্ত ইনপুট স্ট্রিং একে অপরের উপরে লেখা হয়, তখন তারা একটি ম্যাট্রিক্স গঠন করে। কিছু নির্দিষ্ট সারির প্রকারের সমাধানের ক্ষেত্রে মূলত একই প্রভাব রয়েছে। উদাহরণস্বরূপ, একটি কলামকে এন্ট্রি (a, a, b) দিয়ে অন্য কলাম (x, x, y) দিয়ে প্রতিস্থাপন করলে একটি ভিন্ন সমাধান স্ট্রিং হতে পারে, তবে সমাধানযোগ্যতা প্রভাবিত করতে পারে না, কারণ উভয় কলাম একই কাঠামো প্রকাশ করে, যেমন। প্রথম দুটি এন্ট্রি সমান, তবে তৃতীয়টির থেকে আলাদা। একটি ইনপুট দৃষ্টান্ত প্রতিস্থাপন করে স্বাভাবিক করা যেতে পারে, প্রতিটি কলামে, যে অক্ষরটি প্রায়শই a দিয়ে ঘটে, যে অক্ষরটি দ্বিতীয়টি প্রায়শই b দিয়ে ঘটে, এবং আরও অনেক কিছু। স্বাভাবিক উদাহরণের একটি সমাধান দেওয়া হলে, প্রতিটি কলামে সমাধানের অক্ষরগুলিকে তার মূল সংস্করণে পুনরায় ম্যাপ করে মূল উদাহরণটি পাওয়া যেতে পারে। কলামগুলির ক্রম সমস্যার কঠোরতায় অবদান রাখে না। অর্থাৎ, যদি আমরা একটি নির্দিষ্ট বিন্যাস π অনুসারে সমস্ত ইনপুট স্ট্রিংকে বিন্যস্ত করি এবং সেই পরিবর্তিত দৃষ্টান্তের একটি সমাধান স্ট্রিং s পাই, তাহলে π−1 (s) মূল দৃষ্টান্তের একটি সমাধান হবে। উদাহরণ তিনটি ইনপুট স্ট্রিং uvwx, xuwv এবং xvwu সহ একটি উদাহরণ দেওয়া হয়েছে। এটি এইভাবে একটি ম্যাট্রিক্স হিসাবে লেখা যেতে পারেঃ প্রথম কলামে মান রয়েছে (u, x, x)। যেহেতু x হল সেই অক্ষর যা প্রায়শই প্রদর্শিত হয়, তাই আমরা এটিকে a দ্বারা প্রতিস্থাপন করি, এবং আমরা নতুন প্রথম কলাম (b, a, a) অর্জন করে b দ্বারা দ্বিতীয় সর্বাধিক অক্ষর u প্রতিস্থাপন করি। দ্বিতীয় কলামে মান রয়েছে (v, u, v)। প্রথম কলামের ক্ষেত্রে, v কে a দ্বারা প্রতিস্থাপিত করা হয় এবং u কে b দ্বারা প্রতিস্থাপিত করা হয়, যা নতুন দ্বিতীয় কলাম (a, b, a) অর্জন করে। সমস্ত কলামের সাথে একই কাজ করা স্বাভাবিককরণ থেকে প্রাপ্ত ডেটা হ্রাসকে স্বাভাবিককরণ দেয় ইনপুটকে স্বাভাবিককরণ বর্ণমালার আকারকে সর্বাধিক ইনপুট স্ট্রিংয়ের সংখ্যায় হ্রাস করে। এটি অ্যালগরিদমগুলির জন্য দরকারী হতে পারে যার চলমান সময় বর্ণমালার আকারের উপর নির্ভর করে। আনুমানিকতা লি এবং অন্যান্য। একটি বহুপদী-সময় আনুমানিক পরিকল্পনা বিকশিত হয়েছে যা বড় লুকানো ধ্রুবকের কারণে কার্যত অকেজো। স্থির-পরামিতি ট্র্যাক্টেবিলিটি ঘনিষ্ঠ স্ট্রিং সমাধান করা যেতে পারে, যেখানে k হল ইনপুট স্ট্রিংয়ের সংখ্যা, L হল সমস্ত স্ট্রিংয়ের দৈর্ঘ্য এবং d হল সমাধান স্ট্রিং থেকে যে কোনও ইনপুট স্ট্রিং পর্যন্ত কাঙ্ক্ষিত সর্বোচ্চ দূরত্ব। অন্যান্য সমস্যার সাথে সম্পর্ক ঘনিষ্ঠ স্ট্রিং আরও সাধারণ নিকটতম সাবস্ট্রিং সমস্যার একটি বিশেষ ক্ষেত্রে, যা কঠোরভাবে আরও কঠিন। যদিও নিকটতম স্ট্রিংটি বেশ কয়েকটি উপায়ে স্থির-পরামিতি ট্র্যাক্টেবল বলে প্রমাণিত হয়, এই পরামিতিগুলির ক্ষেত্রে নিকটতম সাবস্ট্রিংটি ডাব্লু [1]-হার্ড। রেফারেন্স এন. পি-হার্ড সমস্যা আনুষ্ঠানিক ভাষা