Payamvdn/NorthPersian_fa_wiki huggingface dataset:
: اگر در آرایهٔ پسوندی پسوندهای هر عدد را به صورت عمودی زیر آن بنویسیم بدین شکل خواهد بود: برای مثال،formula_15 برابر است با ۴ و نشان دهندهٔ ۴ امین پسوند در ترتیب الفبایی بین پسوندهای رشتهٔ formula_6 است که می شود codice_2 . ارتباط به درخت پسوندی. آرایهٔ پسوندی ارتباط نزدیکی با درخت پسوندی دارند: و همچنین نشان داده شده است که هر الگوریتم درخت پسوندی را می توان با یک الگوریتم که از آرایهٔ پسوندی تغییر یافته (برای مثال با استفاده از آرایهٔ LCP) استفاده کند جایگزین کرد به طوری که همان مسئله را در همان پیچیدگی زمانی حل کند. بهینگی حافظه. آرایهٔ پسوندی برای پیشرفت در بهینگی حافظه نسبت به درخت پسوندی معرفی شد: آرایه های پسوندی formula_17 عدد صحیح ذخیره می کنند و اگر فرض کنیم برای ذخیرهٔ هر عدد صحیح به formula_18 بایت نیاز داریم، یک آرایهٔ پسوندید در کل به formula_19 بایت حافظه نیاز خواهد داشت، که بسیار کمتر از formula_20ای است که برای ذخیرهٔ درخت پسوندی نیاز است. با این حال در بعضی از کاربردها میزان حافظهٔ مورد نیاز برای آرایهٔ پسوندی می تواند هزینه بر باشد. درحالت کلی آرایهٔ پسوندی به formula_21 بیت حافظه نیاز دار
د، در حالی که متن اصلی با الفبای formula_22 حرفی فقط به formula_23 بیت حافظه نیاز دارد. برای مثال در ژنوم انسان که formula_24 و formula_25 آرایهٔ پسوندی ژنوم به حافظه ای نزدیک به formula_26 برابر حافظهٔ مورد نیاز برای خود ژنوم نیاز دارد. الگوریتم ساخت. یک درخت پسوندی را می توان در formula_27 ساخت و با اجرای یک جستجو اول عمق در formula_27 به آرایهٔ پسوندی تبدیل کرد. پس الگوریتم هایی وجود دارند که می توانند آرایهٔ پسوندی را در زمان formula_27 بسازند. راه حل سادهٔ ساخت آرایه های پسوندی استفاده از الگوریتم های مرتب سازی مقایسه ای است، این الگوریتم ها به formula_21 مقایسه نیاز دارد و با توجه به این که هر مقایسهٔ رشته ای به formula_27 زمان نیاز دارد، کل الگوریتم ساخت آرایهٔ پسوندی با این روش به formula_32 زمان نیاز خواهد داشت. و الگوریتم های پیشرفته تر با استفاده از این موضوع که رشته هایی که باید مرتب شوند، رشته های دلخواهی نیستند و به هم ارتباط دارند روش هایی با زمان formula_33 معرفی می کنند. کاربردها. از آرایهٔ پسوندی می توان برای پیدا کردن سریع همهٔ تکرارهای یک رشتهٔ formula_34 درون رشتهٔ formula_6 استفاده کرد.
پیدا کردن همهٔ تکرارهای یک رشته formula_34 هم ارز است با پیدا کردن همهٔ پسوندهایی که با formula_34 شروع می شوند. با توجه به ترتیب الفبایی پسوندها در آرایهٔ پسوندی این پسوندها پشت سر هم قرار گرفته اند و می توان آن ها را به راحتی با استفاده از ۲ بار اجرای جستجوی دودویی پیدا کرد. جستجوی اول نقطهٔ شروع بازه را پیدا می کند و جستجوی دوم نقطهٔ پایانی را مشخص می کند: def search(P): l = 0; r = n while l &lt; r: mid = (l+r) / 2 if P &gt; suffixAt(A[mid]): l = mid + 1 else: r = mid s = l; r = n while l &lt; r: mid = (l+r) / 2 if P &lt; suffixAt(A[mid]): r = mid else: l = mid + 1 return (s, r) با توجه به این که هر پسوند نیاز به مقایسهٔ formula_38 کارکتر دارد، پیدا کردن زیررشتهٔ formula_34 به طول formula_38 در رشتهٔ formula_6 به طول formula_17 در زمان formula_43 انجام می شود. و این الگوریتم را می توان با استفاده از به formula_44 بهبود بخشید.
قضیهٔ کُوسامبی-کارهونِن-لُواِو ()، یا تبدیل کُوسامبی-کارهونِن-لُواِو، یک فرایند تصادفی در یک بازهٔ کران دار را با ترکیب خطی نامحدودی از توابع متعامد نمایش می دهد. این قضیه به افتخار دامُودار دارماناندا کُوسامبی، و نامیده شده است. این تبدیل هم چنین به تبدیل هُتِلینگ و تبدیل بردار ویژه نیز شناخته می شود و با تحلیل مولفه اصلی () مرتبط است که در پردازش تصویر و آنالیز داده ها، فراوان استفاده می شود. در مقایسه با تبدیل فوریه که ضرایب آن اعداد معیّن () و پایه های آن توابع سینوسی هستند، ضرایب تبدیل کارهونن-لُواِو متغیرهای تصادفی هستند و پایه های آن بستگی به فرایند دارند. می توان گفت این تبدیل به گونه ای با فرایند تصادفی سازگار می شود که به بهترین پایه ها برای آن فرایند می انجامد. برای یک "فرایند تصادفی متمرکز " (، ) می نویسیم: که در آن formula_2ها متغیرهای تصادفی، و دوبه دو ناهمبسته هستند و formula_3ها، توابع پیوسته حقیقی در بازهٔ و دوبه دو در متعامد هستند. فرایندی که "متمرکز "نیست را می توان با متمرکز کرد. اگر فرایند گاوسی باشد، formula_2ها گاوسی و مستقل آماری هستند. یک مثال از یک فرایند متمرکز در بازهٔ ، فرایند وین
ر است. بیانی از قضیه. قضیه. را یک فرایند تصادفی با میانگین صفر و انتگرال پذیر برای مربع آن در فضای احتمال و نمایه آن در بازهٔ بستهٔ ["a", "b"] با تابع کوواریانس پیوستهٔ در نظر می گیریم. حال یک هسته ی مرسر است و "e""k" را یک پایهٔ متعامد بر روی می گیریم که از توابع ویژهٔ "T""K""X" دارای مقدار ویژهٔ تشکیل شده است. می توان را به صورت زیر بیان کرد که در "L"2 هم گراست و همچنین متغیرهای تصادفی "Z""k" دارای میانگین صفر، ناهم بسته و دارای واریانس "λk" هستند اثبات. که در آن ضرایب (متغیرهای تصادفی) "Z""k" به صورت زیر به دست می آیند: مشخصات تبدیل کارهونن-لُواِو. حالت خاص: توزیع گاوسی. ازآنجاکه حد امید ریاضی متغیرهای تصادفی مشترکاً گاوسی، خود مشترکاً گاوسی هستند و متغیرهای تصادفی گاوسی مستقل هستند اگر و فقط اگر متعامد باشند، می توان نتیجه گرفت: قضیه. متغیر تصادفی دارای توزیع مشترک گاوسی است و به طور تصادفی مستقل است اگر فرایند اولیه گاوسی باشد. در این حالت (گاوسی بودن)، از آنجایی که ها مستقل هستند، می توان گفت: تقریباً مطمئناً. بسط کارهونِن-لُواِو فرایند را ناهمبسته می کند. این نتیجه از استقلال حاصل می شود. بسط کارهونِن-
لُواِو مقدار خطای میانگین مربعات را به حداقل می رساند. در بخش معرفی، بیان کردیم که بسط خلاصه شدهٔ کارهونِن-لُواِو بهترین تخمین برای یک فرایند است به طوری که خطای میانگین مربعات حداقل شود. به خاطر همین خصوصیت است که بیان می شود این تبدیل به طور بهینه انرژی را فشرده (ذخیره) می کنند. به طور دقیق تر، برای هر پایهٔ متعامد {"f""k"} از فضای "L"2(["a", "b"])، می توان فرایند "Xt" را به صورت زیر تجزیه کرد: که در آن و می توان "X""t" را با جمع متناهی زیر برای هر عدد صحیح 'N" به صورت زیر تخمین زد یافتن واریانس. یک نتیجهٔ مهم این تبدیل را می توان این مورد در نظر گرفت که از آنجایی که "Z""k"ها در تبدیل کارهونِن-لُواِو ناهمبسته هستند، نتیجه می دهد که "X""t" برابر است با جمع واریانس جملات جمع، داریم: تعریف شده روی ["a", "b"] و استفاده از این مسئله که "e""k"ها متعامد هستند، نتیجه می گیریم که واریانس کل فرایند برابر است با:
یک مدل گرافیکی یا مدل گرافیکی احتمالاتی(PGM) یک مدل احتمالاتی است که بیانگر ساختار [conditional dependancy وابستگی شرطی] بین متغیرهای تصادفی توسط یک گراف است. مدل های گرافیکی معمولاً در آمار و احتمال (به طور دقیق تر در آمار بیزی) و یادگیری ماشین استفاده می شوند. انواع مدل های گرافیکی. به طور کلی مدل های گرافیکی احتمالی از یک نمایش مبتنی بر گراف به عنوان پایه و اساس برای رمزگذاری کامل توزیع بیش از یک و چند بعدی در فضا است و یک گراف که نمایش فاکتور سازی شده مجموعه ای از عدم وابستگی ها در توزیع خاص است استفاده می کند. دو شاخه از نمایش های گرافیکی از توزیع ها معمولاً استفاده می شوند، که شبکه های بیزی و مارکوف در شبکه های نام دارند. هر دو خانواده شامل خواص فاکتور سازی و عدم وابستگی هستند، اما آن ها در مجموعه ای از عدم وابستگی از توزیع که می توانند رمز و فاکتور سازی کنند تفاوت دارند. شبکه بیزی. اگر ساختار شبکه از نوع یک مدل گرافی جهت دار بدون دور باشد، مدل نشان دهنده فاکتور سازی توزیع احتمال توأم از تمام متغیرهای تصادفی است. به بیان دقیق تر اگر واقعه های formula_1 باشند سپس احتمال مشترک به صورت: که در آن formula_3
مجموعه ی والدهای گره formula_4 است. به عبارت دیگر توزیع مشترک به صورت ضرب توزیع های شرطی فاکتور می شود. برای مثال مدل گرافیکی که در شکل بالا نشان داده شده است (که در واقع یک گراف جهت دار بدون دور نیست و یک گراف اجدادی است) متشکل از متغیرهای تصادفی formula_5 با یک تابع چگالی احتمال مشترک است که به صورت زیر فاکتور می شود: هر دو گره با داشتن مقادیر والدهای خود به صورت مستقل شرطی هستند. در کل اگر معیار d-separation در گراف موجود باشد هر دو مجموعه از گره ها با داشتن هر مجموعه سومی مستقل شرطی هستند. عدم وابستگی محلی و کلی در شبکه های بیز یکسان هستند. این نوع از مدل گرافیکی به نام مدل گرافیکی جهت دار، شبکه بیز یا شبکه های باور شناخته شده اند. روش های یادگیری ماشین کلاسیک مانند مدل پنهان مارکوف و شبکه های عصبی و مدل های جدیدتر مانند مدل variable-order Markov می توانند به عنوان موارد خاص از شبکه های بیزی در نظر گرفته بشوند. میدان تصادفی مارکوف. یک میدان تصادفی مارکوف، که به صورت شبکه مارکوف نیز شناخته شده است، یک مدل روی یک گراف بدون جهت است. یک مدل گرافیکی با بسیاری زیر ساختارهای تکرار شونده که با plate notation نشان
داده می شود. کاربردها. چارچوب مدل، الگوریتم هایی برای شناخت و تجزیه و تحلیل ساختارها در توزیع های پیچیده برای توصیف آن ها به صورت خلاصه و استخراج اطلاعات بدون ساختار ارائه می دهد، که به آن ها اجازه می دهد تا به صورت مؤثر ساخته و بهینه سازی شوند. کاربردهای مدل های گرافیکی شامل استخراج اطلاعات، تشخیص گفتار، بینایی ماشین، رمز گشایی از کدهای بررسی توازن کم چگالی، مدل سازی شبکه تنظیم ژن, پیدا کردن ژن ها و تشخیص بیماری ها، و مدل های گرافیکی برای ساختار پروتئین است.
فرایند تولد مرگ (زاد مرگ) صورت خاصی از فرایند مارکف زمان گسسته است که در آن تغییر حالت ها تنها از دو نوع است: اسم مدل از کاربردهای معمول می آید٬مانند زمانی که استفاده از این مدل ها برای نشان دادن سایز فعلی جمعیت و مدلی از مرگ و تولد به معنای واقعی به کار می رود. فرایندهای زاد و مرگ کاربردهای زیادی در آمارنگاری مردم٬تئوری صف٬مهندسی کارائی٬علم امراض مسری یا در زیست شناسی دارد. این روش می تواند در کاربرد هائی نظیر مطالعهٔ تکامل باکتری ها٬تعداد مردم با وجود یک بیماری در جمعیت٬یا تعداد مشتری ها در یک صف سوپرمارکت استفاده شود. هنگامی که تولد رخ می دهد فرایند از حالت "n" به "n" + 1 می رود. هنگامی که مرگ رخ می دهد فرایند از حالت "n" به حالت "n" − 1 می رود. این فرایند را می توان با نرخ تولدformula_1و نرخ مرگformula_2مشخص نمود. نمونه هایی از فرایند زاد-مرگ. یک فرایند زاد-مرگ را یک فرایند تولد خالص می نامیم اگر در آن برای همهٔ formula_3 داشته باشیم formula_4. یک فرایند زاد-مرگ را یک فرایند مرگ خالص می نامیم اگر در آن برای همهٔ formula_3 داشته باشیم formula_6. فرایند پواسون (همگن) حالتی خاصی از فرایند زاد-مرگ خالص است که
برای آن داشته باشیم formula_7. مدل M/M/1 و مدل "M/M/c" که هر دو در تئوری صف استفاده شده اند، فرایند تولد مرگی هستند که برای توصیف مشتریان در صف نامحدود استفاده می شوند. استفاده در تئوری صف. در تئوری صف فرایند تولد مرگ یکی از اساسی ترین مثال های مدل صف بندی "M/M/C/K/formula_8/FIFO/(در علامت گذاری کامل kandell) است. این یک صف با ورود پواسون است که از یک جمعیت بینهایت که از C سرویس رسان با زمان سرویس توزیع نمائی با K مکان استفاده می کند. به رغم فرض جمعیت نامحدود، این مدل یک مدل خوب برای سیستم های مخابراتی متنوع است. صف M/M/1. M/M/1 یک صف سرویس رسانی منفرد از اندازه بافر بی نهایت است. در محیط غیر تصادفی، فرایند تولد مرگ در مدل صف بندی تمایل دارد که با میانگین بلند مدت باشد٬بنابراین نرخ میانگین ورودها به صورت formula_9 و متوسط زمان سرویس دهی به صورت formula_10 می باشد. فرایند تولد و مرگ یک صف M/M/1 است زمانی که داشته باشیم: معادلهٔ تفاضلی برای این احتمال که سیستم در حالت "k و" در زمان "t" باشند به صورت زیر بیان می شود. صف M/M/c. M/M/c چندین صف با C سرور و بافر نامحدود است. این حالت با M/M/1 تنها در زمان سرویس متف
اوت است که اکنون به صورت زیر محاسبه خواهد شد. و با صف M/M/1/K. M/M/1/K یک صف سرور سرویس رسانی منفرد با بافری از اندازی K است. این صف در مخابرات و همچنین زیست شناسی هنگامی که محدودیتی بر روی ظرفیت داریم استفاده می شود. در مخابرات ما دوباره از پارامترهایی که از صف M/M/1 بدست می آیند٬به صورت استفاده می کنیم. در زیست شناسی به خصوص در مبحث رشد باکتری ها زمانی که جمعیت صفر است هیچ توانایی برای رشد نیست بنابراین داریم علاوه بر این اگر ظرفیت نشان دهندهٔ محدودیت باشد مثلاً در جایی که جمعیت از جمعیت زیاد بمیرند داریم: معادلات دیفرانسیل برای احتمال این که سیستم در حالت "k" در زمان "t" باشد به صورت زیر است: تعادل. یک صف گفته می شود که در تعادل است٬اگر حد formula_25 وجود داشته باشد. برای این مورد formula_26 باید صفر باشد. اگر صف M/M/1 را فرض بگیریم٬پاسخ حالت دائم (تعادل) به صورت زیر است: اگر برای همه formula_29 داشته باشیم:formula_30 و formula_31 (حالت همگن) این فرض می تواند به معادله زیر بینجامد. رفتار محدود. در یک زمان کوچک formula_33 تنها سه نوع از انتقال امکان پذیر است: یک مرگ یا یک تولد یا نه مرگ و نه تولد. اگر نرخ و
قوع (در واحد زمان) تولد formula_9 باشد برای مرگ formula_35 باشد. سپس احتمالات جابجائی به ترتیب formula_36, formula_37و formula_38 می باشد. برای یک فرایند جمعیت «تولد» انتقال به سمت افزایش جمعیت به مقدار ۱ است در حالی که «مرگ» انتقال به سمت کاهش اندازهٔ جمعیت به مقدار ۱ است.
بیوپرل مجموعه ای از افزونه های زبان برنامه نویسی پرل است که توسعهٔ اسکریپت های پرل را برای برنامه های بیوانفورماتیک را تسهیل می بخشد. این نقش مهمی در در پروژه ژنوم انسان بازی می کند. پس زمینه. بیوپرل یک پروژه نرم افزاری متن باز است که توسط بنیاد آزاد انفورماتیک پشتیبانی می شود. اولین مجموعه از کدهای پرل از بیوپرل توسط تیم هابرد و جونگ بک از شورای تحقیقاتی پزشکی مرکز کمبریج که در آن اولین تعیین توالی ژنوم توسط فرد سنجر انجام شد شکل گرفت. مرکز شورای تحقیقاتی پزشکی یکی از قطب ها و محل های تولد بیوانفورماتیک جدید است چنان که مقدار زیادی توالی DNA و ساختار سه بعدی پروتئین در آن جا دارد. نام بیوپرل به طور مشترک توسط جونگ بک و استیو برنر در اتاقی کوچک از مرکز مهندسی پروتئین (CPE) از مرکز شورای تحقیقات پزشکی (MRC) که مدیرش آلن فرشت بود ابداع شد. در آن اتاق کوچک، سایرس چوتیا و تیم هابرد با تعدادی از دانشجویان دکترا و همکارانشان کار می کردند. تیم هابرد متخصص برنامه نوسی پرل است و از th_llib.pl که که شامل تعداد زیادی زیرروال برای بیوانفورماتیک است استفاده می کرد. جونگ بک، اولین دانشجوی دکترای تیم هابرد بود که jong_lib.p
l را ساخت. جونگ دو کتابخانهٔ زیرروال پرل را در Boi.pl با هم ادغام کرد. یک روز در ۱۹۹۵، استیو برنر، یک دانشجوی دکترای سایرس چوتیا به آن اتاق سر زد و بر روی آنچه آنها کتابخانهٔ پرل می نامند بحث کردند که این بعد از مباحثهٔ طولانی (چند ماه) بر سر اینکه آیا پرل از سی بهتر است بود زیرا استیو برنر کتابخانهٔ سی برای بیوانفورماتیک مختص خودش را داشت. این دو دانشجوی دکترا بعد از گذشتن از نام هایی مانند پروتئین پرل، پروتوپرل، بیوپرل و غیره برای زیست شناسی بیوپرل نام کتابخانه پرل خالص را گذاشتند. استیو برنر در سال ۱۹۹۵ یک بخش بیوپرل در سیستم های هوشمند برای زیست شناسی مولکولی (ISMB) کمبریج را سازماندهی کرد اگرچه واقعاً اتفاق نیفتاد. بیوپرل در ماه های آینده کاربرانی شامل جورج فیولن که یک دوره آموزشی در آلمان را سازماندهی کرد داشت. همکاران و دانشجویان جورج بیوپرل را بیشتر دادند که این بعداً توسط افراد دیگری مانند استیو چرویتز که به طور فعال کدهایی به زبان پرل برای پایگاه داده ژنوم مخمرش توسعه می داد به هم متصل شد. توسعهٔ عمده هنگامی انجام شد که دانشجوی کمبریج دیگری به نام ایوان برنی بعد از مباحثهٔ طولانی دیگری بر سر اینکه آ
یا پرل در بیوانفورماتیک از سی بهتر است به این واگن پیوست و ایوان و افراد زیاد دیگری در توسعهٔ بیوپرل فعال بودند. اولین نسخه پایدار در ۱۱ ژوئن ۲۰۰۲بود؛ نسخه های اخیر پایدار (از نظر API) نسخهٔ ۱٫۶٫۹ از ۱۴ مارس ۲۰۱۱ است. همچنین تعدادی نسخه های توسعه یافته وجود دارند که به صورت دوره ای تولید می شوند. نسخه سری ۱٫۶٫۰ به عنوان پایدارترین (از نظر اشکل) نسخه بیوپرل است و برای استفاده روزمره توصیه می شود، اما نسخه های آزمایشی نیز بسیار پایدار و بسیاری از کاربران بیوپرل در حال حاضر بر روی آنها اقامت دارند. به منظور استفاده از مزیت های بیوپرل، کاربر به درک پایه ای از زبان برنامه نوسی پرل شامل درکی از اینکه چگونه از ارجاعات، افزونه ها، اشیاء و رویه های پرل استفاده کنیم نیاز دارد. امکانات. بیوپرل افزونه های نرم افزاری ای برای بسیاری از کارهای معمولی برنامه نوسی بیوانفورماتیک فراهم می کند. این ها شامل موارد زیر اند: کاربرد. علاوه بر استفاده مستقیم توسط کاربرهای نهایی، بیوپرل همچنین پایه ای برای گستره وسیعی از ابزارهای بیوانفورماتیک فراهم کرده است که شامل موارد زیر می باشد: گاهی ابزارها و الگوریتم های جدیدی از توسعه دهندگان
خارجی مستقیماً به بیوپرل ادغام می شوند: کتابخانه های مرتبط در زبان های برنامه نویسی دیگر. شماری کتابخانه بیوانفورماتیک مرتبط در دیگر زبان های برنامه نویسی به عنوان بخشی از بنیاد آزاد بیوانفورماتیک پیاده سازی شده اند که شامل موارد زیر اند:
در نظریه احتمال فرایند کوشی یک نوع فرایند تصادفی است. فرایند کوشی انواع متقارن و نامتقارن دارد. عبارت «فرایند کوشی» به صورت مشخص نشده برای اشاره به فرایند کوشی متقارن استفاده می شود. فرایند کوشی دارای ویژگی های زیر است: فرایند کوشی متقارن. فرایند کوشی متقارن را می توان با یک حرکت براونی یا فرایند وینر مرتبط با پیرو (subordinator) لوی توصیف کرد. پیرو (subordinator) لوی یک فرایند در ارتباط با توزیع لوی با داشتن پارامتر مکان formula_1 و یک پارامتر مقیاس formula_2. توزیع لوی یک حالت خاص از معکوس توزیع گاما است؛ بنابراین با استفاده از formula_3 به نمایندگی از فرایند کوشی و formula_4 به نمایندگی از پیرو (subordinator) لوی فرایند کوشی متقارن را می توان به صورت زیر توضیح داد: توزیع لوی، احتمال اولین ضربه برای یک حرکت براونی است، و در نتیجه فرایند کوشی اساساً نتیجه مستقل دو فرایند حرکت براونی است نمایش لوی–خینشین برای فرایند کوشی متقارن، یک سه گانه با رانش صفر و انتشار صفر یک لوی–خینشین سه گانه از formula_6 که در آن formula_7. حاشیه تابع مشخصه فرایند کوشی متقارن به صورت زیر است: توزیع احتمال حاشیه ای فرایند کوشی متقار
ن، تابع توزیع توزیع کوشی است فرایوند کوشی نامتقارن. فرایند کوشی نامتقارن در شرایط استفاده از یک پارامتر formula_10 تعریف شده. در اینجا formula_10 چولگی است و قدر مطلق آن باید کمتر یا برابر با ۱ یاشد. در حالتی که در آن formula_12 است فرایند کوشی کاملاً نامتقارن در نظر گرفته می شود. سه گانه لوی–Khintchine به صورت (0,0,W) است formula_6 که در آن formula_14 که در آن formula_15، formula_16 و formula_17. با توجه به این، formula_10 یک تابع از formula_19 و formula_20 است. تابع مشخصه نامتقارن توزیع کوشی به صورت زیر است: توزیع حاشیه ای توزیع نامتقارن فرایند کوشی توزیع پایدار با شاخص پایداری برابر با ۱ است.
در ریاضیات فرایند اورنشتاین-اولنبک (برگرفته شده از نام لئونارد اورنشتاین و جرج اولنبک) فرایند تصادفی است که به طور کلی سرعت توده ای از ذرات برونی تحت تأثیر اصطکاک را توصیف می کند. این فرایند، فرایند گاوس–مارکف (فرایندی با مشخصات گوسی و مارکوف) ایستا بوده و تنها فرایند غیرجزئی است که سه شرط فرایندهای گاوسی-مارکوف را ارضا کرده و تبدیلات خطی فضا و زمان را ممکن می سازد. در طول زمان این فرایند به میانگین طولانی مدت خود میل می کند: به این فرایندها، بازگشت به میانگین می گویند. این فرایند را می توان به عنوان تبدیلی از قدم زدن تصادفی در زمان پیوسته، یا فرایند وینر دانست که در آن خواص به گونه ای تغییر کرده است که قدم زدن و بازگشت به سمت محل مرکزی تمایل داشته و هرچه فاصله از این مرکز بیشتر باشد، شدت تمایل نیز بیشتر خواهد شد. فرایند اورنستین-یولنبک را نیز می توان به عنوان آنالوگ پیوسته-زمان فرایند گسسته-زمان AR(1) در نظر گرفت. نمایش توسط تساوی دیفرانسیلی تصادفی. فرایند اورنشتاین-یولنبک Xt تساوی دیفرانسیلی تصادفی زیر را ارضا می کند: که در آن formula_2 با formula_3 و formula_4 پارامترها بوده و formula_5 نشان دهنده فرایند و
ینر است. نمایش بالا را می توان به عنوان تعریف اصلی فرایند اورنستین-یولنبک دانست و که به عنوان مدل واسیک نیز معرفی می گردد. فوکر–پلانک معادله نمایندگی. تابع دانسیته احتمال ("ƒ"("x", "t" فرایند اورنشتاین-اولنبک تساوی فوکر-پلانک را مرتفع می کند:
در علوم رایانه، الگوریتم هیرشبرگ الگوریتمی برای هم ترازسازی بهینهٔ دو توالی است که دان هیرشبرگ (Dan Hirschberg) در سال ۱۹۷۵ آن را ارائه کرد. در این الگوریتم برای ارزیابی هم ترازی ها از فاصله لون اشتاین استفاده می شود؛ در هم ترازی بهینه مجموع هزینه های درج، حذف و جایگزین کردن حروف برای یکسان کردن دو رشته، کمینهٔ تمام هم ترازی های ممکن است. الگوریتم نیدلمن-وانچ یکی از اولین الگوریتم هایی است که برای هم ترازسازی سراسری دو توالی از برنامه نویسی پویا استفاده می کند. الگوریتم هیرشبرگ در واقع نسخه ای از الگوریتم نیدلمن-وانچ است که با تقسیم و حل مسئله را حل می کند و مصرف حافظهٔ بهینه تری دارد. ایده های اصلی. هوشمندی الگوریتم هیرشبرگ در استفاده از مشاهده های زیر است: این الگوریتم از ایدهٔ Savitch در نظریهٔ پیچیدگی الهام گرفته است. امتیازدهی. برای محاسبهٔ امتیاز هم ترازی (درج و حذف، جایگزینی و تطابق) از ماتریسهای امتیازدهی استفاده می شود. برای مثال، در ماتریس بلوسام-۶۲, امتیاز جایگزینی آمینواسیدهای Ala و Trp، تطابق آمینواسید Ala و حذف آمینواسید Ala، به ترتیب ۳-، ۴ و ۴- است. معمولاً برای امتیازدهی هم ترازی های آمینواسید
ی (توالی های پروتئینی) از ماتریس های بلوسام یا ماتریس های جهش پذیرفتهٔ نقطه ای استفاده می شود. الگوریتم. برای رشتهی مفروض formula_5; formula_6 حرف i ام این رشته (formula_7), formula_8 زیررشتهٔ آن از حرف i ام تا j ام و formula_9 رشتهٔ معکوس آن است. برای دو حرف x و y که به ترتیب از رشتههای X و Y اند؛ امتیاز حذف x, درج y و جایگزینی x با y به ترتیب برابر formula_10است. تابع NWscore. شبه کد: function NWscore(X,Y) Score(0,0) = 0 for j=1 to length(Y) Score(0,j) = Score(0,j-1) + Ins(Yj) for i=1 to length(X) Score(i,0) = Score(i-1,0) + Del(Xi) for j=1 to length(Y) if( Xi == Yj ) scoreSub = Score(i-1,j-1) + Match(Xi, Yj) else scoreSub = Score(i-1,j-1) + Sub(Xi, Yj) scoreDel = Score(i-1,j) + Del(Xi) scoreIns = Score(i,j-1) + Ins(Yj) Score(i,j) = max(scoreSub, scoreDel, scoreIns) end end for j=0 to length(Y) LastLine(j) = Score(length(X),j) return LastLine این تابع آخرین سطر از ماتریس امتیاز نیدلمن-وانچ را (که معمولاً با F یا score نشان داده می شود) در زمان formula_11 و با حافظهٔ formula_11 محاسبه می کند. پیاده سازی زیر
در MATLAB, با همین پیچیدگی زمانی ولی با حافظهٔ formula_13 نتیجه را محاسبه می کند: function [ lastLine ] = NWscore( X, Y ) % assume length(Y) &lt;= length(X) scorePrev = zeros(1, length(Y) + 1); lastLine = zeros(1, length(Y) + 1); for i = 1:length(Y) scorePrev(i + 1) = scorePrev(i) + Ins(Y(i)); end for i = 1:length(X) lastLine(1) = scorePrev(1) + Del(X(i)); for j = 1:length(Y) if( X(i) == Y(j) ) s1 = scorePrev(j) + Match(X(i), Y(j)); else s1 = scorePrev(j) + Sub(X(i), Y(j)); end s2 = scorePrev(j + 1) + Del(X(i)); s3 = lastLine(j) + Ins(Y(j)); lastLine(j + 1) = max([s1, s2, s3]); end scorePrev = lastLine; end end تابع Hirschberg. شبه کد: function Hirschberg(X,Y) Z = "" W = "" if length(X) == 0 for i=1 to length(Y) Z = Z + '-' W = W + Yi end else if length(Y) == 0 for i=1 to length(X) Z = Z + Xi W = W + '-' end else if length(X) == 1 or length(Y) == 1 (Z,W) = NW(X,Y) else xlen = length(X) xmid = length(X)/2 ylen = length(Y) ScoreL = NWscore(X1:xmid, Y) ScoreR = NWscore(rev(Xxmid+1:xlen), rev(Y)) ymid = arg max S
coreL + rev(ScoreR) (Z,W) = Hirschberg(X1:xmid, y1:ymid) + Hirschberg(Xxmid+1:xlen, Yymid+1:ylen) end return (Z,W) پیاده سازی در MATLAB: function [ Z, W, maxScore ] = Hirschberg( X, Y ) if( isempty(X) ) Z = char(ones(1, length(Y)) * '-'); W = Y; elseif( isempty(Y) ) Z = X; W = char(ones(1, length(X)) * '-'); elseif( length(X) == 1 || length(Y) == 1 ) [Z, W] = NW(X, Y); else mid1 = floor(length(X) / 2); s1 = NWscore(X(1:mid1), Y); s2 = NWscore(flip(X(mid1 + 1:end)), flip(Y)); [maxScore, mid2] = max(s1 + flip(s2)); mid2 = mid2 - 1; [temp11, temp21] = Hirschberg(X(1:mid1), Y(1:mid2)); [temp12, temp22] = Hirschberg(X(mid1 + 1:end), Y(mid2 + 1:end)); Z = [temp11, temp12]; W = [temp21, temp22]; end end این تابع با استفاده از روش تقسیم و حل، هم ترازی بهینه و امتیاز این هم ترازی را به دست می آورد. نحوهٔ پیاده سازی تابع NWscore بیان شد و تابع NW از الگوریتم نیدلمن-وانچ استفاده می کند. زمان اجرای این تابع formula_11 است. دقت کنید که الگوریتم نیدلمن-وانچ در حالت کلی به formula_11 حافظه نیاز دارد، اما اینجا، تنها درصورتی
استفاده شده است که طول یکی از رشتهها (m یا n) برابر ۱ باشد و در نتیجه با مصرف حافظهٔ خطی اجرا می شود. مقایسه با الگوریتم نیدلمن-وانچ. الگوریتم هیرشبرگ، مشابه الگوریتم نیدلمن-وانچ، بهترین امتیاز را با استفاده از برنامه نویسی پویا محاسبه کرده و هم ترازی متناظر با آن را می یابد. پیچیدگی زمانی هم ترازی دو رشته با طول های m و n در الگوریتم هیرشبرگ formula_11 (مشابه الگوریتم نیدلمن-وانچ) است. این الگوریتم تنها formula_13حافظه نیاز دارد که بهینه تر از الگوریتم نیدلمن-وانچ (با حافظه formula_11) است. مثال. فرض کنید دو توالی DNA بنام های X و Y و امتیازهای هم ترازسازی به صورت زیر باشند: formula_19 formula_20 در اولین مرحلهٔ الگوریتم هیرشبرگ،formula_21فراخوانده می شود که رشتهی X را به صورت formula_22 تقسیم بندی می کند. سپس formula_23فراخوانده می شود که حاصل آن به صورت زیر است: C G T A T 0 -2 -4 -6 -8 -10 A -2 -1 -3 -5 -4 -6 C -4 0 -2 -4 -6 -5 G -6 -2 2 0 -2 -4 C -8 -4 0 1 -1 -3 و در نتیجه: ScoreL = [ -8 -4 0 -2 -1 -3 ] rev(ScoreR) = [ -3 -1 1 0 -4 -8 ] Sum = [-11 -5 1 -2 -5 -11] بیشینهٔ امتیاز در ymid = ۲ است و در نتیجه
formula_24 تقسیم بندی بهینهٔ Y است. به همین ترتیب در هر مرحله زیررشته ها تقسیم شده و هم ترازی بهینه به دست می آید. درخت زیر خلاصه ای از مراحل تقسیم بندی در این مثال را نشان می دهد: (AGTACGCA,TATGC) (AGTA,TA) (CGCA,TGC) (AG, ) (TA,TA) (CG,TG) (CA,C) (T,T) (A,A) (C,T) (G,G) برگ های این درخت، هم ترازی بهینه را نشان می دهند که به صورت زیر است: W = AGTACGCA Z = --TATGC- کاربرد. معمولاً در بیوانفورماتیک از الگوریتم هیرشبرگ برای هم ترازسازی سراسری توالی های زیستی (توالی های آمینواسیدی و توالی های DNA) استفاده می شود. بلاست (BLAST) و فاستا (FASTA) نمونه های هیوریستیک استفاده از آن هستند.