Біоінформатика наука, що займається вивченням організації та функціонування біологічних систем різного рівня (від молекулярного до популяційного) на основі
|
|
Скачати 2.37 Mb.
|
|
Таблиця 4.5. Локальне вирівнювання: зворотній шлях вирівнювання. Таким чином, послідовність амінокислот у найбільш біологічно важливій частині цих білків висококонсерватина, у той час, як подібність інших ділянок незначна. У таких випадках, як розглянутий, локальне вирівнювання дає кращий спосіб порівняння амінокислотних послідовностей, ніж глобальне. 4.3 Псевдоглобльне вирівнювання Псевдоглобальне вирівнювання – це таке вирівнювання, яке не враховує деякі кінцеві пробіли в послідовностях, тобто ті, які стоять перед першим або після останнього символу. Наприклад, всі пробіли у другій послідовності кінцеві, на відміну від єдиного пробілу в першій. AGAC_CAGATTTCTGCCAG AGACTСAG _ _ _ _ _ _ _ _ _ _ Відмітимо, що дві послідовності значно відрізняються за довжиною. Якщо застосовувати основний алгоритм глобального вирівнювання, то отримуємо наступний результат: AGACCAGATTTCTGCCAG AGA_C _ _ _ _ _ Т_ _ _ _СAG з вагою –12, на відміну від ваги попереднього вирівнювання, яка дорівнює –15. Друге вирівнювання, незважаючи на більшу вагу, буде гіршим, з точки зору пошуку співпадаючих фрагментів в послідовностях. Це відображує той факт, що, якщо не враховувати кінцеві пробіли, вага першого вирівнювання дорівнює 5. Алгоритм псевдоглобального вирівнювання застосовується з тими ж цілями, що і алгоритм локального вирівнювання, а саме для пошуку співпадаючих ділянок, а також для порівняння послідовностей, що дуже відрізняються по довжині. Алгоритм псевдоглобального вирівнювання
Вирівнювання, коли не штрафується перший пробіл в t, еквівалентно найкращому вирівнюванню між t та підпослідовностями послідовності s. Значення a(i, j) відповідає максимальній подібності префікса t, довжиною i та підпослідовностями префікса s, довжиною j. Ініціюючи нулями нульовий стовпчик, одержуємо випадок вирівнювання, коли ігноруються перші пробіли в послідовності t. Ініціюючи нулями нульові рядок та стовпчик одержуємо випадок вирівнювання, коли ігноруються перші пробіли в обох послідовностях. a(0,j) = 0, i= 0,...m, де a(i,0) = 0, j = 0,...n.
Розглянемо модифікацію основного алгоритму для побудови псевдоглобальнго вирівнювання, коли кінцевий пробіл в послідовності t не штрафується. Кінцевий пробіл в t співпадає з підпослідовностями послідовностей s. Ця частина вирівнювання – вирівнювання між t і префіксом s, і, щоб одержати оптимальне вирівнювання без врахування кінцевих пробілів, потрібно вирівняти t і префікс s. Подібність між t та префіксом s буде одержано, якщо взяти максимальне значення в останньому рядку масиву а, тобто Max = max a(m, j ), j =1,...,n(таблиця 4.6). Аналогічним чином потрібно діяти, якщо не штрафується кінцевий пробіл у s. Максимум в цьому випадку шукається в останньому стовпчику масиву а Max = max a(i,n), i =1,...,m (таблиця 4.6). Якщо не штрафуються кінцеві пробіли у t та s, то для одержання вирівнювання потрібно знаходити максимальне значення в останніх рядку та стовпчику масиву а:  Значения Max дорівнює вазі найкращого псевдоглобального вирівнювання. Таким чином, зворотній хід алгоритму псевдоглобального вирівнювання полягає у пошуку максимального елементу в останніх рядку та стовпчику масиву а і побудові зворотного шляху, рухаючись від зазначеного максимального значения масиву а (значения Мах) до елементу з координатами (0,0). Таким чином, для вказаних послідовностей існує декілька значень Max = 1, які породжують три наступних варіанти вирівнювання: _ _ САААТС САААТС_ _ САААТС СТС _ _ _ _ _ _ _ _ _ _ СТС _ _ _ СТС
Таблиця 4.6. Псевдоглобальне вирівнювання: зворотній шлях вирівнювання для послідовностей s = САААТС та t = СТС. Очевидно, що ваги усіх трьох вирівнювань при ігноруванні пробілів рівні між собою ω = 1. Це означає, що усі три вирівнювання є оптимальними. Ми розглянули приклад, у якому існує декілька максимальних елементів, але одне максимальне значения у останніх рядку і стовпчику також не рідкісний випадок. 4.4. Вирівнювання подібних послідовностей Розглянемо алгоритм швидкого вирівнювання подібних послідовностей (лише для випадку глобального вирівнювання), коли порівнюються послідовності однакової довжини n. В цьому випадку масив a(i, j) стає квадратною матрицею і по головній діагоналі розміщено вирівнювання без пробілів між s i t. Якщо таке вирівнювання не оптимальне, то необхідно ввести пробіли для одержання більшої ваги. Пробіли завжди вводяться попарно, один в s і один в t. Вирівнювання ведеться поблизу головної діагоналі. Основна ідея полягає в тому, що у випадку схожих послідовностей, найкраще вирівнювання лежить в малому оточенні головної діагоналі. Розглянемо приклад алгоритму для заповнення матриці в горизонтальній та вертикальній смузі шириною 2k +1 навколо головної діагоналі (рис.4.2).  Рис. 4.2 Масив ваг вирівнювання префіксів а для порівняння подібних послідовностей однакової довжини Елемент a(n,n) містить максимальну вагу вирівнювання в смузі заданої ширини. Відмітимо, що значення поза смугою ширини k не використовуються івідповідно не розраховуються. Для того, щоб визначити, чи лежить позиція (i,j) всередині смуги, використовується проста перевірка -k ≤i - j ≤k. Як i в інших алгоритмах динамічного програмування, кожен елемент a(i,j) залежить лише від трьох попередніх значень: a(i-1,j),a(i-1,j-1), a(i,j-1). Але перевіряти елемент a(i-1,j-1) не обов’язково, оскільки він знаходиться на тій самій діагоналі, що і елемент a(i,j), і завжди буде знаходитися всередині смуги. Перевіряти потрібно елементи a(i-1,j), a(i,j-1), котрі можуть виходити за межі смуги, за умови того, що елемент a(i,j) знаходиться всередині неї. Модифікація основного алгоритму для вирівнювання подібних послідовностей • Ініціалізація першого рядка і стовпчика масиву ваг префіксів а: перші k елементів рядка і стовпчика обчислюються за формулою! а(0,j)=0, i = 0,..k, де а(і,0)=0, j = 0,..k. (величина k наперед задана). • Заповнення частини таблиці (рис 4.2), що знаходиться у смузі шириною 2k + 1, за наступним принципом: Якщо елемент a(i - 1,j) знаходиться всередині смуги, тоді: Якщо елемент a(i,j -1) знаходиться всередині смуги, тоді:  Очевидно, що у випадку коли обидва елементи a(i-1,j) та a(i,j-1) знаходяться всередині смуги, тоді елемент a(i,j) потрібно розраховувати зa вже відомою формулою (4.2). Після першого проходження алгоритму, якщо одержане значения а(n,n) для фіксованого значения k більше, або дорівнює вазі найкращого вирівнювання з k+1 пробілами, у такому випадку знайдено оптимальне вирівнювання. Враховуючи, що у вирівнюванні присутні принаймні k+1 пар пробілів, то можливо найкраща вага вирівнювання дорівнює M[n-(k+1)]+2(k+1)g. Ця величина вираховується з припущенням, що у вирівнюванні знаходиться точно k+1 пара пробілів, а усі інші пари дають співпадіння (М > 0 - вага співпадіння). Якщо а(n,n) менше цієї величини, ширина смуги подвоюється і знову розраховується а(n,n). Описаний метод можна розширити і для послідовностей різної довжини. 4.5. Загальна функція штрафу Визначимо розрив в послідовності як безперервну кількість k > 1 пробілів. 3 урахуванням виникнення можливих мутацій, поява розриву з k пробілами більш ймовірна, ніж поява к незалежних пробілів. Це пов’язано з тим, що поява довгого розриву може бути результатом лише однієї делеції, в той час як к пробілів, розділених блоками «символ-символ», утворюються через k мутацій, а виникнення однієї мутаційної події більш ймовірне, ніж декількох. Блочне вирівнювання враховує можливу кластеризацію пробілів. Позначимо ω(k) функцію штрафу розриву з к пробілами. ω(k)=gk, де g -величина штрафу за індивідуальний пробіл, k - кількість пробілів. Відмінності між алгоритмом подібності послідовностей з урахуванням загальної функції штрафу та основним алгоритмом виникають через неадитивну схему штрафів. Кожне вирівнювання тепер можна розкласти на суму послідовних блоків трьох типів:
Розглянемо наступне блочне вирівнювання. TTG_ _ _TTAAGGCTGATG TGATCCA _ _ _ _ _ _ GCG_ _ T|T|G|_ _ _ |T|TAAGGC|TGA|TG T|G|A|TGG|A| _ _ _ _ _ _ |GCG|_ _ Блоки першого типу одержують вагу p(i, j), де і та j – символи, що вирівнюються. Блоки другого та третього типів одержують вагу w(k), де k – довжина розриву. Тепер вага вирівнювання розраховується на рівні блоків. Адитивність ваг зберігається тільки на межах блоків, що призводить до деяких змін в основному алгоритмі. Блоки не можуть йти довільно один за одним, блоки другого та третього типів не можуть йти за блоками того ж типу. Для кожної пари (i, j) тепер зберігається не значення ваги найкращого вирівнювання між префіксом t, довжиною i та префіксом s, довжиною j, а вага вирівнювання між їх останніми блоками певного типу. Для порівняння послідовності t довжиною m та послідовності s довжиною n використовують три масиви розміру (m +1)(n +1): Масив a – для порівняння символьних блоків; Масив b – для порівняння блоків, що закінчуються пробілами в t; Масив с – для порівняння блоків, що закінчуються пробілами в s. Алгоритм подібності з урахуванням загальної функції штрафу
Масиви ініціюються за наступними формулами:  3) Розрахунок усіх інших елементів масивів a,b,c. В залежності від типу блоку, яким закінчується вирівнювання, змінюються значення у відповідних масивах за рекурентними формулами:  Відмітимо, що значення масивів b і c залежать від декількох величин, оскільки останній блок може мати різну довжину. 4) Пошук максимального з трьох елементів a(m,n), b(m,n), c(m,n) та вибір стартової точки. Для одержання значення максимальної ваги вирівнювання береться максимум по всім a(m,n), b(m,n), c(m,n). 5) Побудова вирівнювання на основі значень елементів масивів a, b, c. Для вирівнювання використовується та ж ідея, що і в інших алгоритмах. Ми вибираємо елементи масивів з максимальною вагою, запам’ятовуючи масив якого типу було використано. |
-1Схожі:
|
Гриби – це одна з найбільших у природі груп організмів. Їх вивченням... Гриби – це одна з найбільших у природі груп організмів. Їх вивченням займається спеціальна наука – мікологія ( від грец. «мікос»... |
*Кроманьйонець Наука про минуле, що займається вивченням матеріальних предметів (артефактів) діяльності людини |
|
Тема Гриби Загальна характеристика грибів. Різноманітність грибів Гриби – це одна з найбільших у природі груп організмів. Їх вивченням займається спеціальна наука – мікологія ( від грец. «мікос»... |
1 Значення і теоретичні основи фінансового аналізу Дана спеціальність передбачає вивчення процесів формування і виконання бюджетів різного рівня, механізму управління державним боргом,... |
|
Оповідь, переказ про відоме, досліджене минуле наука, яка займається... Рід — доісторична і ранньоісторична суспільно-організаційна спільнота, стадія еволюції Етносу, до якої належали кровно пов'язані... |
Цієї презентації – Електродинаміка Медико біологічних систем. Створював... Я, Лесюк Анастасія Юріївна приймала активну участь у класному і позакласному житті Українського медичного ліцею 11-В класу. Писала... |
|
ОБҐРУНТУВАННЯ Україні проводиться модернізація організації документообігу, зважаючи на функціонування документів у традиційній та електронній формах.... |
ОБҐРУНТУВАННЯ Україні проводиться модернізація організації документообігу, зважаючи на функціонування документів у традиційній та електронній формах.... |
|
ПРОГРАМА З МАТЕМАТИКИ для 10 11 класів загальноосвітніх навчальних... Програма призначена для організації навчання математики в класах з поглибленим вивченням математики. Вона розроблена на основі Державного... |
1 Менеджмент при процесному підході – це Досягнення високого рівня ефективності організації на основі використання знань та навичок підлеглих |
При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
bibl.com.ua
звернутися до адміністрації
bibl.com.ua