Tree alignment
গণনামূলক ফাইলোজেনেটিক্সে, বৃক্ষ বিন্যাস একটি গণনামূলক সমস্যা যা একাধিক ক্রম বিন্যাস, বা ডিএনএ, আরএনএ বা প্রোটিনের তিন বা ততোধিক ক্রমের বিন্যাস তৈরির সাথে সম্পর্কিত। ক্রমগুলি একটি ফাইলোজেনেটিক গাছে সাজানো হয়, যা প্রজাতি বা ট্যাক্সার মধ্যে বিবর্তনীয় সম্পর্কের মডেলিং করে। প্রতিটি গাছের অভ্যন্তরীণ শীর্ষের জন্য ক্রমগুলির মধ্যে সম্পাদনা দূরত্ব গণনা করা হয়, যাতে গাছের মধ্যে সমস্ত সম্পাদনা দূরত্বের যোগফল ন্যূনতম হয়। গাছের বিন্যাসটি পরিচালনাযোগ্য গাছের আকার এবং গণনামূলক প্রচেষ্টার মধ্যে বিভিন্ন বিনিময় সহ বেশ কয়েকটি অ্যালগরিদমের মধ্যে একটি ব্যবহার করে সম্পন্ন করা যেতে পারে। সংজ্ঞা ইনপুটঃ সিকোয়েন্সের একটি সেট, একটি ফাইলোজেনেটিক ট্রি লিফ-লেবেল এবং সিকোয়েন্সের মধ্যে একটি সম্পাদনা দূরত্ব ফাংশন। আউটপুটঃ এমন অভ্যন্তরীণ শীর্ষগুলির একটি লেবেলিং যা ন্যূনতম করা হয়, যেখানে এর শেষ পয়েন্টগুলির মধ্যে সম্পাদনা দূরত্ব হয়। কাজটি এনপি-হার্ড। ব্যাকগ্রাউন্ড সিকোয়েন্স অ্যালাইনমেন্ট বায়োইনফরমেটিক্সে, তথ্য প্রক্রিয়াকরণের মৌলিক পদ্ধতি হল সিকোয়েন্স ডেটার বৈপরীত্য করা। জীববিজ্ঞানীরা জৈবিক ক্রমের কার্যকারিতা, কাঠামো এবং বিবর্তনীয় তথ্য আবিষ্কার করতে এটি ব্যবহার করেন। নিম্নলিখিত বিশ্লেষণগুলি ক্রম সমাবেশের উপর ভিত্তি করেঃ ফাইলোজেনেটিক বিশ্লেষণ, হ্যাপ্লোটাইপ তুলনা এবং আর. এন. এ কাঠামোর পূর্বাভাস। অতএব, ক্রম বিন্যাসের দক্ষতা এই সমস্যাগুলি সমাধানের কার্যকারিতাকে সরাসরি প্রভাবিত করবে। একটি যুক্তিসঙ্গত এবং দক্ষ ক্রম বিন্যাস নকশা করার জন্য, অ্যালগরিদম ডেরিভেশন বায়োইনফরমেটিক্সের ক্ষেত্রে গবেষণার একটি গুরুত্বপূর্ণ শাখায় পরিণত হয়। সাধারণত, ক্রম বিন্যাসের অর্থ হল অক্ষর যোগ করে, অক্ষর মুছে দিয়ে বা প্রতিটি স্ট্রিংয়ের জন্য একটি স্থান যোগ করে সর্বাধিক সাদৃশ্য সহ দুটি বা ততোধিক প্রদত্ত স্ট্রিং থেকে একটি স্ট্রিং তৈরি করা। মাল্টিপল সিকোয়েন্স অ্যালাইনমেন্ট সমস্যা সাধারণত পেয়ারওয়াইজ সিকোয়েন্স অ্যালাইনমেন্টের উপর ভিত্তি করে এবং বর্তমানে, পেয়ারওয়াইজ সিকোয়েন্স অ্যালাইনমেন্ট সমস্যার জন্য, জীববিজ্ঞানীরা এর সর্বোত্তম সমাধান পেতে একটি গতিশীল প্রোগ্রামিং পদ্ধতি ব্যবহার করতে পারেন। যাইহোক, একাধিক ক্রম সারিবদ্ধকরণ সমস্যা এখনও জৈব তথ্যবিজ্ঞানের আরও চ্যালেঞ্জিং সমস্যাগুলির মধ্যে একটি। এর কারণ হল একাধিক ক্রম বিন্যাসের জন্য সর্বোত্তম সমাধান খুঁজে পাওয়া একটি এনপি-সম্পূর্ণ সমস্যা হিসাবে প্রমাণিত হয়েছে এবং শুধুমাত্র একটি আনুমানিক সর্বোত্তম সমাধান পাওয়া যেতে পারে। দূরত্ব ম্যাট্রিক্স পদ্ধতি দূরত্ব পদ্ধতিটি অক্ষর সন্নিবেশ, মুছে ফেলা এবং প্রতিস্থাপনের ন্যূনতম ক্রিয়াকলাপের সংখ্যা পরিমাপ করে যা এক জোড়া স্ট্রিংয়ের উপর পরিচালিত হওয়ার সময় একটি ক্রম u কে অন্য ক্রম v এ রূপান্তর করতে প্রয়োজন। সম্পাদনা দূরত্বের গণনা গতিশীল প্রোগ্রামিংয়ের উপর ভিত্তি করে হতে পারে এবং সমীকরণটি O (|u। × |v।) সময়ে হয়, যেখানে |u। এবং |v। হল u এবং v-এর দৈর্ঘ্য। সম্পাদনা দূরত্বের দক্ষ অনুমান অপরিহার্য কারণ দূরত্ব পদ্ধতি গণনামূলক জীববিজ্ঞানের একটি মৌলিক নীতি বংশগত বৈশিষ্ট্যের জন্য "প্রতিসাম্য" ব্যবহার করা যেতে পারে। সম্পাদনা দূরত্ব গণনা করতে একাধিক ফাংশন ব্যবহার করার কারণে, বিভিন্ন ফাংশনের ফলে বিভিন্ন ফলাফল হতে পারে। গাছের সারিবদ্ধকরণ সমস্যার জন্য একটি সর্বোত্তম সম্পাদনা দূরত্ব ফাংশন খুঁজে বের করা অপরিহার্য। গাছের সারিবদ্ধকরণের সমস্যার ফলে একটি এন. পি-হার্ড সমস্যা দেখা দেয়, যেখানে স্কোরিং মোড এবং বর্ণমালার আকার সীমাবদ্ধ থাকে। এটি একটি অ্যালগরিদম হিসাবে পাওয়া যেতে পারে, যা অপ্টিমাইজড সমাধান খুঁজে বের করতে ব্যবহৃত হয়। যাইহোক, এর দক্ষতা এবং সংখ্যা ক্রমের মধ্যে একটি সূচকীয় সম্পর্ক রয়েছে, যার অর্থ হল যখন ক্রমের দৈর্ঘ্য খুব বেশি হয়, ফলাফল পাওয়ার জন্য প্রয়োজনীয় গণনার সময় অত্যন্ত দীর্ঘ হয়। আনুমানিক অপ্টিমাইজড সমাধান পেতে স্টার প্রান্তিককরণ ব্যবহার করা গাছের প্রান্তিককরণ ব্যবহারের চেয়ে দ্রুত। যাইহোক, একাধিক-অনুক্রমের সাদৃশ্যের মাত্রা যাই হোক না কেন, তারা সারিবদ্ধকরণের সময় জটিলতার ক্রম সংখ্যার বর্গ এবং ক্রমের গড় দৈর্ঘ্যের বর্গের সাথে আনুপাতিক সম্পর্ক রয়েছে। বরাবরের মতো, এম. এস. এ-তে ক্রমটি এত দীর্ঘ যে এটি অকার্যকর বা এমনকি অগ্রহণযোগ্য। অতএব, সময়ের জটিলতা রৈখিক পর্যায়ে হ্রাস করার চ্যালেঞ্জ হল গাছের সারিবদ্ধকরণের অন্যতম প্রধান সমস্যা। কম্বিনেটোরিয়াল অপ্টিমাইজেশন কৌশল কম্বিনেটোরিয়াল অপ্টিমাইজেশন হল এম. এস. এ সমস্যা সমাধানের জন্য একটি ভাল কৌশল। কম্বিনেটোরিয়াল অপ্টিমাইজেশান কৌশলের ধারণা হল এই সমস্যা সমাধানের জন্য একাধিক ক্রম বিন্যাসকে জোড়া ক্রম বিন্যাসে রূপান্তর করা। এর রূপান্তর কৌশলের উপর নির্ভর করে, সমন্বিত অপ্টিমাইজেশান কৌশলটিকে ট্রি অ্যালাইনমেন্ট অ্যালগরিদম এবং স্টার অ্যালাইনমেন্ট অ্যালগরিদম-এ ভাগ করা যেতে পারে। একটি প্রদত্ত মাল্টি-সিকোয়েন্স সেট = {,.,}-এর জন্য, একটি বিবর্তনীয় গাছ খুঁজে বের করুন যার n পাতার নোড রয়েছে এবং এই বিবর্তনীয় গাছ এবং সেটের মধ্যে এক থেকে এক সম্পর্ক স্থাপন করে। বিবর্তনীয় গাছের অভ্যন্তরীণ নোডগুলিতে ক্রম নির্ধারণ করে, আমরা প্রতিটি প্রান্তের মোট স্কোর গণনা করি এবং সমস্ত প্রান্তের স্কোরের যোগফল হল বিবর্তনীয় গাছের স্কোর। গাছের সারিবদ্ধকরণের লক্ষ্য হল একটি নির্ধারিত ক্রম খুঁজে বের করা, যা সর্বাধিক স্কোর পেতে পারে এবং বিবর্তনীয় গাছ এবং তার নোডের নির্ধারিত ক্রম থেকে চূড়ান্ত মিল পাওয়া ফলাফল পেতে পারে। তারার সারিবদ্ধকরণকে গাছের সারিবদ্ধকরণের একটি বিশেষ ক্ষেত্রে দেখা যেতে পারে। আমরা যখন স্টার অ্যালাইনমেন্ট ব্যবহার করি, তখন বিবর্তনীয় গাছের শুধুমাত্র একটি অভ্যন্তরীণ নোড এবং এন লিফ নোড থাকে। অভ্যন্তরীণ নোডের জন্য নির্ধারিত ক্রমকে মূল ক্রম বলা হয়। কীওয়ার্ড ট্রি তত্ত্ব এবং অহো-কোরাসিক সার্চ অ্যালগরিদম যখন একাধিক সিকোয়েন্স সারিবদ্ধকরণকে জোড়া সিকোয়েন্স সারিবদ্ধকরণে রূপান্তরিত করার জন্য সমন্বিত অপ্টিমাইজেশন কৌশল ব্যবহার করা হয়, তখন মূল সমস্যাটি "একাধিক সিকোয়েন্স সারিবদ্ধকরণের দক্ষতা কীভাবে উন্নত করা যায়" থেকে "জোড়া-ভিত্তিক সিকোয়েন্স সারিবদ্ধকরণের দক্ষতা কীভাবে উন্নত করা যায়"-তে পরিবর্তিত হয়। কীওয়ার্ড ট্রি থিওরি এবং অহো-কোরাসিক সার্চ অ্যালগরিদম জোড়া-ভিত্তিক ক্রম সারিবদ্ধকরণ সমস্যা সমাধানের জন্য একটি কার্যকর পদ্ধতি। কীওয়ার্ড ট্রি তত্ত্ব এবং অহো-কোরাসিক সার্চ অ্যালগরিদমের সংমিশ্রণের লক্ষ্য হল এই ধরনের সমস্যা সমাধান করাঃ একটি প্রদত্ত দীর্ঘ স্ট্রিং এবং ছোট স্ট্রিং = {,,.,} (z bul N, z> 1)-এর একটি সেটের জন্য, সবকিছুর অবস্থান খুঁজে বের করুন। সেট দ্বারা উৎপাদিত কীওয়ার্ড ট্রি ব্যবহার করা হয়, এবং তারপর অহো-কোরাসিক সার্চ অ্যালগরিদমের মাধ্যমে এই কীওয়ার্ড ট্রি দিয়ে অনুসন্ধান করা হয়। টি-তে সমস্ত কিছুর অবস্থান খুঁজে বের করার জন্য এই পদ্ধতিটি ব্যবহার করার মোট সময় জটিলতা হল ও (+ +), যেখানে =।। (দৈর্ঘ্য), = এস।। (সমস্ত কিছুর দৈর্ঘ্যের যোগফল) এবং এর অর্থ হল সমস্ত কিছুর জন্য ঘটনার যোগফল। কীওয়ার্ড ট্রি তত্ত্ব সেটের কীওয়ার্ড ট্রি = {,,.,} (z bul N, z> 1) একটি শিকড়যুক্ত গাছ, যার মূল কে দ্বারা চিহ্নিত করা হয় এবং এই কীওয়ার্ড ট্রিটি সন্তুষ্ট করেঃ (1): প্রতিটি প্রান্ত স্পষ্টভাবে একটি অক্ষরকে চিহ্নিত করে। (2) একই নোড থেকে পৃথক যে কোনও দুটি প্রান্তকে বিভিন্ন অক্ষরের সাথে সামঞ্জস্যপূর্ণ হতে হবে। (3) প্রতিটি প্যাটার্ন (i = 1,2,., z) একটি নোডের সাথে মিলে যায় এবং মূল K থেকে নোড পর্যন্ত পথটি স্ট্রিংটি সঠিকভাবে বানান করতে পারে। এই কে গাছের প্রতিটি পাতার নোডের জন্য, এটি সেটের নির্দিষ্ট নিদর্শনগুলির মধ্যে একটির সাথে মিলে যায়। মূল নোড থেকে নোডের সাথে সংযুক্ত স্ট্রিংকে উপস্থাপন করতে ব্যবহৃত হয়। তারপর দীর্ঘতম প্রত্যয়ের দৈর্ঘ্য উপস্থাপন করতে ব্যবহার করা হবে (এছাড়াও, এই প্রত্যয়টি সেটের নিদর্শনগুলির মধ্যে একটির উপসর্গ)। কীওয়ার্ড ট্রি-র মূল নোড থেকে এই উপসর্গটি অনুসন্ধান করা হচ্ছে এবং অনুসন্ধান শেষ হওয়ার সময় দ্বারা চিহ্নিত শেষ নোডটি। উদাহরণস্বরূপ, সেট = {আলু, ট্যাটু, থিয়েটার, অন্যান্য}, এবং কীওয়ার্ড ট্রি ডানদিকে দেখানো হয়েছে। সেই উদাহরণে, যদি = পটাট, তাহলে = |tat। = 3, এবং নোডের ব্যর্থতা লিঙ্কটি সেই চিত্রে দেখানো হয়েছে। একটি ব্যর্থতা সংযোগ স্থাপন অহো-কোরাসিক অ্যালগরিদমের সময় জটিলতা উন্নত করার মূল চাবিকাঠি। এটি অনুসন্ধানের জন্য মূল বহুপদী সময়কে রৈখিক সময়ে হ্রাস করতে ব্যবহার করা যেতে পারে। অতএব, কীওয়ার্ড ট্রি তত্ত্বের মূল বিষয় হল রৈখিক সময়ে একটি কীওয়ার্ড ট্রি-র সমস্ত ব্যর্থতা লিঙ্ক (যার অর্থ সমস্ত এস খুঁজে পাওয়া) খুঁজে বের করা। এটি অনুমান করা হয় যে সমস্ত নোডের প্রতিটি, যার মূল নোড থেকে দূরত্ব কম বা সমান, পাওয়া যেতে পারে। যে নোডের মূল নোড থেকে দূরত্ব + 1, তার সন্ধান করা যেতে পারে। এর মূল নোড হল, এবং নোড এবং দ্বারা প্রতিনিধিত্ব করা অক্ষরটি হল। (1): যদি নোডের পরবর্তী অক্ষরটি হয়, তবে এই প্রান্তের অন্য নোডটি, এবং = হিসাবে সেট করা যেতে পারে। (2): যদি সমস্ত অক্ষর এবং তার চাইল্ড নোডের মধ্যে সমস্ত প্রান্ত অনুসন্ধান করে না হয়, তবে এটি যোগফলের প্রত্যয়। যেহেতু এই প্রত্যয়টি মূল নোড (উপসর্গের অনুরূপ) দিয়ে শুরু হওয়া স্ট্রিংয়ের সাথে মেলে, তাই পরেরটি সনাক্ত করা যায় কি না। যদি তা না হয়, তবে এই প্রক্রিয়াটি রুট নোড না পাওয়া পর্যন্ত চলতে পারে। অহো-কোরাসিক সার্চ অ্যালগরিদম কীওয়ার্ড ট্রি-তে সমস্ত ব্যর্থতার লিঙ্ক স্থাপন করার পরে, অহো-কোরাসিক সার্চ অ্যালগরিদম রৈখিক সময়ে সকলের (i = 1,2,., z) অবস্থান খুঁজে বের করতে ব্যবহৃত হয়। এই ধাপে, সময় জটিলতা হল ও (এম + কে)। অন্যান্য কৌশলগুলি এম. এস. এ, ডি. এন. এ, আর. এন. এ এবং প্রোটিনে, ক্রমগুলি সাধারণত তৈরি করা হয় এবং তাদের একটি বিবর্তনীয় সম্পর্ক রয়েছে বলে ধরে নেওয়া হয়। আর. এন. এ, ডি. এন. এ-র উৎপাদিত মানচিত্র এবং বিবর্তনীয় পরিবারগুলির ক্রমের তুলনা করে, মানুষ প্রোটিন সংরক্ষণের মূল্যায়ন করতে পারে এবং বিবর্তনীয় ক্রমের মধ্যে পার্থক্যের তুলনা করে কার্যকরী জিন ক্ষেত্র খুঁজে পেতে পারে। সাধারণত, একাধিক ক্রম সারিবদ্ধকরণ সমস্যা সমাধানের জন্য হিউরিস্টিক অ্যালগরিদম এবং ট্রি সারিবদ্ধকরণ গ্রাফও গ্রহণ করা হয়। হিউরিস্টিক অ্যালগরিদম সাধারণত, হিউরিস্টিক অ্যালগরিদমগুলি পুনরাবৃত্তিমূলক কৌশলের উপর নির্ভর করে, যা একটি তুলনা পদ্ধতির উপর ভিত্তি করে, পুনরাবৃত্তিমূলক প্রক্রিয়া দ্বারা একাধিক ক্রম সারিবদ্ধকরণের ফলাফলকে অনুকূল করে। ডেভি এম একাধিক ক্রম সারিবদ্ধকরণ সমস্যা সমাধানের জন্য কণা ঝাঁক অপ্টিমাইজেশন অ্যালগরিদম ব্যবহার করার প্রস্তাব করেছিলেন; ইকেদা তাকাহিরো একটি হিউরিস্টিক অ্যালগরিদম প্রস্তাব করেছিলেন যা এ * অনুসন্ধান অ্যালগরিদমের উপর ভিত্তি করে; ই বার্নি প্রথম একাধিক ক্রম সারিবদ্ধকরণ সমস্যা সমাধানের জন্য লুকানো মার্কভ মডেল ব্যবহার করার প্রস্তাব করেছিলেন; এবং অন্যান্য অনেক জীববিজ্ঞানী এটি সমাধানের জন্য জেনেটিক অ্যালগরিদম ব্যবহার করেন। এই সমস্ত অ্যালগরিদমগুলি সাধারণত ক্রমের সংখ্যার প্রতি শক্তিশালী এবং সংবেদনশীল নয়, তবে তাদের ত্রুটিও রয়েছে। উদাহরণস্বরূপ, কণা ঝাঁক অপ্টিমাইজেশান অ্যালগরিদমের ফলাফলগুলি অস্থির এবং এর গুণাবলী র্যান্ডম সংখ্যা নির্বাচনের উপর নির্ভর করে, এ * অনুসন্ধান অ্যালগরিদমের রানটাইম খুব দীর্ঘ, এবং জেনেটিক অ্যালগরিদম স্থানীয় উৎকর্ষের মধ্যে পড়ে যাওয়া সহজ। বৃক্ষ বিন্যাস গ্রাফ মোটামুটিভাবে, বৃক্ষ বিন্যাস গ্রাফের লক্ষ্য হল গাছগুলিকে একটি গ্রাফে সারিবদ্ধ করা এবং পরিশেষে পরিসংখ্যান বিকাশের জন্য সেগুলিকে সংশ্লেষিত করা। জীববিজ্ঞানে, ট্রি অ্যালাইনমেন্ট গ্রাফ (টিএজি) গাছের সেট থেকে বিবর্তনীয় দ্বন্দ্ব বা ওভারল্যাপিং ট্যাক্সা অপসারণ করতে ব্যবহৃত হয় এবং তারপরে অনিশ্চয়তা এবং দ্বন্দ্ব অন্বেষণ করার জন্য জিজ্ঞাসা করা যেতে পারে। সারিবদ্ধকরণ, সংশ্লেষণ এবং বিশ্লেষণের পদ্ধতিগুলিকে একীভূত করে, টিএজি-র লক্ষ্য হল দ্বন্দ্বমূলক সম্পর্ক এবং বিস্তৃত ক্রম থেকে প্রাপ্ত আংশিক ওভারল্যাপিং ট্যাক্সন সেটগুলি সমাধান করা। এছাড়াও, গাছের সারিবদ্ধকরণ গ্রাফ সুপারট্রি এবং গ্রাফ্টিং অনুশীলনের জন্য একটি মৌলিক পদ্ধতি হিসাবে কাজ করে, যা বেরি দ্বারা সুপারট্রি নির্মাণের জন্য সফলভাবে পরীক্ষা করা হয়েছে। যেহেতু গাছ থেকে গ্রাফে রূপান্তর তাদের উৎস গাছ থেকে অনুরূপ নোড এবং প্রান্ত ধারণ করে, তাই টিএজি আরও বিশ্লেষণের জন্য মূল উৎস গাছগুলির নিষ্কাশনও প্রদান করতে পারে। টিএজি হল সারিবদ্ধ গাছের একটি সংমিশ্রণ। এটি পরস্পরবিরোধী অনুমানের বিবর্তনীয় সম্পর্ক সংরক্ষণ করতে পারে এবং বিবর্তনীয় অনুমান বিকাশের জন্য উৎস গাছগুলিকে সংশ্লেষিত করতে পারে। অতএব, এটি অন্যান্য প্রান্তিককরণ সমস্যা সমাধানের একটি মৌলিক পদ্ধতি। আরও দেখুন সাধারণ বৃক্ষ বিন্যাস রেফারেন্স গণনামূলক ফাইলোজেনেটিক্স