نمایش مبدأ برای مدل پنهان مارکف مشخصات

{{ادغام با|مدل پنهان مارکوف}}
[[پرونده:Hmmer_coreProfileHMM.png|جایگزین=|بندانگشتی|330x330پیکسل|در گراف گره‌های تطبیق (M)، درج (I) و حذف (D) دیده می‌شود. احتمال انتشار هر نوکلئوتید در گره درج برابر ۰٫۲۵ است.]]مدل پنهان مارکف مشخصات (یا Profile-HMM) یکی از روش‌های حل مسائل [[هم تراز کردن توالی|هم‌تراز کردن توالی]] (Sequence Alignment) است که به کمک [[مدل پنهان مارکف]] به حل آن می‌پردازد. یکی از دسته مسئله‌های هم‌تراز کردن توالی که به کمک این روش حل می‌شود [[هم‌ترازسازی چند توالی]] (Multiple Sequence Alignment) یا به اختصار MSA است.<ref>{{یادکرد وب|نویسنده=Sudipta Mulia, DebahutiMishr, Tanushree Jena|کد زبان=|تاریخ=|وبگاه=|نشانی=https://reader.elsevier.com/reader/sd/pii/S1877705812021315?token=51DF1D97BA1BF4ADC16CF779424F384E8A0AB6A46FA53A60D6F9CA5DC68945618F27378EED6893D95963B765D133B7C9|عنوان=Profile HMM based Multiple Sequence Alignment for DNA Sequences}}</ref> این مدل به وسیله احتمال پرش، تطابق و عدم تطابق ایجاد می‌شود که این احتمال‌ها را می‌توان از جدول شاخصه رشته‌های توالی یافته (Profile) بدست آورد. در MSA هم ترازی بین چند توالی بیولوژیکی بررسی می‌شود به همین دلیل الگوریتم‌های استفاده شده در آن به مراتب پیچیده‌تر اند. یکی از مزیت‌های استفاده از مدل‌ها در حل این دسته از مسائل نسبت به دیگر الگوریتم‌ها استفاده از فاکتور احتمال است که در دیگر الگوریتم‌ها معمولاً نادیده گرفته می‌شود.

== ساختار مدل ==
[[پرونده:RPLP0_90_ClustalW_aln.gif|جایگزین=|بندانگشتی|329x329پیکسل|در شکل روبرو جدول توالی‌های هم تراز شده از پروتئین‌ها مشاهده می‌شود. با توجه به این توالی‌ها ستون‌هایی که درصد پرش در آنها از یک مقدار مشخصی کمتر باشد به عنوان گره‌های تطبیق در گراف مدل در نظر گرفته می‌شوند که احتمال انتشار هر نوکلئوتید در تطبیق بر اساس ستون متناظر با آن بدست می‌آید.]]
در گراف این مدل هر گره نشان دهنده یک تطبیق، حذف یا درج است همچنین در دو طرف گراف گره‌هایی برای نشان دادن شروع و پایان هم ترازی وجود دارد. تعداد و مقادیر موجود در گره‌ها بر اساس جدول مشخصه بدست می‌آید به اینگونه که برای گره‌های تطبیق در جدول ستون‌هایی که احتمال پرش در آنها از یک مقدار از قبل تعیین شده کمتر باشد در نظر گرفته می‌شوند. به ازای هر گره تطبیق دو گره درج و حذف نیز وجود دارد که گره حذف نشان دهنده این است که در هم ترازی به جای تطبیق حذف انجام شده و گره درج نشان دهنده درج در توالی در عملیات هم ترازی است که این درج‌ها بین دو تطبیق در گراف رخ می‌دهند و ممکن است بین دو تطبیق بیش از یک درج وجود داشته باشد.

در گراف برای گره تطابق انتقال به گره‌های تطبیق و حذف در لایه بعدی یا گره درج در همان لایه انجام می‌شود. در گره درج انتقال به خود گره یا گره تطابق لایه بعدی صورت می‌گیرد. همچنین برای گره‌های حذف انتقال به گره‌های تطبیق و حذف لایه بعدی انجام می‌شود.<ref>{{یادکرد وب|نویسنده=Byung-Jun Yoon|کد زبان=|تاریخ=|وبگاه=|نشانی=https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2766791/|عنوان=Hidden Markov Models and their Applications in Biological Sequence Analysis}}</ref>

== هم‌تراز کردن توالی ==
برای هم‌تراز کردن یک توالی از گره شروع آغاز می‌کنیم و مسیری با بیشترین امتیاز را تا گره پایان می‌یابیم. برای اینکار به کمک [[الگوریتم ویتربی]] این مسیر را میابیم. در این الگوریتم اگر در مرحله <math>i</math>در حالت <math>k</math>باشیم مسیری از گره شروع تا این گره با بیشترین امتیاز از رابطه زیر پیدا می‌شود:<math display="block">s(k,i) = max_{l}\{s(l,i-1)\times w_{l,k}\}</math>که <math>s(k,i)</math>امتیاز آن گره می‌باشد و <math>w_{l,k}</math>وزن یال بین گره مربوط به حالت <math>l</math>در مرحله <math>i-1</math>و گره حالت <math>k</math>در مرحله <math>i</math>است که احتمال انتقال را نشان می‌دهد. با توجه به اینکه مقادیر وزن‌های کمتر از یک است پس اگر اندازه گراف بزرگ باشد مقادیر امتیاز به تدریج کوچک‌تر می‌شود تا جایی که از لحاظ کامپیوتری قادر به انجام محاسبات نیستیم در این صورت به جای خود امتیاز از لگاریتم آن استفاده می‌شود. در صورت استفاده از لگاریتم رابطه به شکل زیر می‌شود:<ref>{{یادکرد وب|نویسنده=Johannes Söding|کد زبان=|تاریخ=|وبگاه=|نشانی=https://academic.oup.com/bioinformatics/article/21/7/951/268976|عنوان=Protein homology detection by HMM–HMM comparison}}</ref><math display="block">\log (s(k,i)) = max_{l}\{\log (s(l,i-1)) + \log (w_{l,k})\}</math>

== مقدار دهی پارامترها ==
پس از ساخت گراف و مدل برای مقدار دهی به وزن یال‌ها و احتمالات از توالی‌های هم‌تراز شده موجود در جدول استفاده می‌کنیم. ابتدا مسیر توالی‌ها در گراف پیدا کردهه و از طریق این مسیرها مقدار احتمال انتقال‌ها را می‌یابیم. برای مثال اگر بخواهیم احتمال انتقال از حالت <math>k</math>به حالت <math>l</math>را بیابیم در هر مسیر تعداد دفعات انتقال از <math>k</math>به <math>l</math>را بر تعداد دفعات انتقال از حالت <math>k</math> به هر حالت دیگری تقسیم می‌کنیم. به این ترتیب می‌توان وزن یال‌ها را بدست آورد. همچنین مشابه همین روش می‌توان احتمال انتشار را در هر حالت بدست آورد.<ref>{{یادکرد وب|نویسنده=|کد زبان=|تاریخ=|وبگاه=|نشانی=https://www.cs.princeton.edu/~mona/Lecture/HMM1.pdf|عنوان=Topics in Computational Molecular Biology}}</ref> یک روش دیگر برای مقدار دهی استفاده از [[یادگیری ویتربی]] است. در این روش ابتدا پارامترها را به صورت رندم مقدار دهی می‌کنیم و بر اساس آن مسیر یک توالی را بدست می‌آوریم سپس به کمک مسیر بدست آمده و خود توالی مقادیر جدیدی برای پارامترها بدست می‌آوریم و به کمک این مقادیر و توالی دیگر مسیر جدیدی بدست آورده می‌شود. همین روند چندین بار تکرار می‌شود تا زمانی که پارامترها به یک مقدار همگرا شوند.<ref>{{یادکرد وب|نویسنده=Tin Y Lam and Irmtraud M Meyer|کد زبان=|تاریخ=|وبگاه=|نشانی=https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3019189/|عنوان=Efficient algorithms for training the parameters of hidden Markov models using stochastic expectation maximization (EM) training and Viterbi training}}</ref>

=== الگوریتم باوم-ولچ ===
یکی دیگر از روش های بدست آوردن مقادیر استفاده از [[الگوریتم باوم-ولچ]] است. در یادگیری ویتربی چون در این روش از همان الگوریتم ویتربی استفاده می‌شود خروجی نهایی به صورت قطعی است و یک جواب احتمالاتی به ما نمی‌دهد برای بدست آوردن یک درجه‌ای از قطعیت در  جواب نهایی می توان از الگوریتم باوم-ولچ استفاده کرد. این الگوریتم در واقع همانند الگوریتم یادگیری ویتربی است اما برای یادگیری از احتمالات بهره می‌برد. در این الگوریتم دو مقدار <math>\Pi^*</math>و <math>\Pi^{**}</math>را به شکل زیر تعریف می‌کنیم:

<math display="block">\Pi^*_{k,i} = Pr(\pi_i = k | x)</math><math display="block">\Pi^{**}_{l,k,i} = Pr(\pi_{i-1}= l, \pi_i = k|x)</math>

که <math>\Pi^*</math>احتمال بودن در حالت <math>k</math>در مرحله <math>i</math>به شرط دانستن توالی است که در اینجا <math>x</math> همان توالی است و <math>\Pi^{**}</math>در واقع همان احتمال انتقال از حالت <math>k</math> به حالت <math>l</math>است. همانند ویتربی این الگوریتم نیز ابتدا یک مقادیر رندم برای هر کدام از پارامتر ها در نظر می گیرد سپس با استفاده از آنها هر یک از <math>\Pi^*</math>و <math>\Pi^{**}</math> متناسب با توالی را می یابد. سپس با استفاده از <math>\Pi^*</math> و <math>\Pi^{**}</math> بدست آمده پارامتر های جدید بدست آمده و دوباره به کمک آنها <math>\Pi^*</math>و <math>\Pi^{**}</math>جدید بدست می‌آید. این رویه تا زمانی تکرار می‌شود که پارامتر ها به یک مقدار مشخص همگرا شوند<ref>{{یادکرد وب|نویسنده=Xiaolin Li , Marc Parizeau , Réjean Plamondon|کد زبان=|تاریخ=|وبگاه=|نشانی=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.335.1457&rep=rep1&type=pdf|عنوان=Training Hidden Markov Models with Multiple Observations – A Combinatorial Method}}</ref>.

== برنامه‌ها ==
[[HAMMER|HMMER]] یا همر به مجموعه برنامه‌هایی می‌گویند که به وسیله این روش هم ترازی توالی ها را انجام می‌دهد. از برنامه هایی که از این بسته استفاده می‌کنند می توان بهHmmerBuild  HmmerCalibrate ،HmmerConvert '''،'''HmmerIndex ،HmmerFetch، HmmerSearch، HmmerPfam، HmmerAlign و  HmmerEmit اشاره کرد. برای مثال در HmmerBuild به کمک توالی‌های از پیش تراز شده مدل می‌شود و می‌توان به پایگاه داده آن اضافه کرد<ref>{{یادکرد وب|نویسنده=|کد زبان=|تاریخ=|وبگاه=|نشانی=http://www.biology.wustl.edu/gcg/hmmanalysis.html|عنوان=Profile Hidden Markov Model Analysis|accessdate=26 ژوئیه 2019|archiveurl=https://web.archive.org/web/20190724174527/http://www.biology.wustl.edu/gcg/hmmanalysis.html|archivedate=24 ژوئیه 2019|dead-url=yes}}</ref>'''.'''  

== منابع ==
{{پانویس}}

[[رده:مدل‌های پنهان مارکف]]