Документ взят из кэша поисковой машины. Адрес оригинального документа : http://mouse.genebee.msu.ru/~bennigsen/nhunt_files/term_2011.pdf Дата изменения: Mon Sep 12 00:56:59 2011 Дата индексирования: Mon Oct 1 19:30:00 2012 Кодировка: Windows-1251

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имF МF ВF ЛОМОНОСОВА ФАКУЛЬТЕТ БИОИНЖЕНЕРИИ И БИОИНФОРМАТИКИ

Программа для поиска гомологов нуклеотидных последовательностей

Курсовая работа студента s курса ЮF АF Пекова

Научный руководительX кFфFEмFнFD сFнFсF СF АF Спирин

Москва PHII


Оглавление
1 Введение 2 Литературный обзор 3 Описание программы
QFI QFP QFQ Поиск наилучших диагоналей F F F F F F F F F F F F F F F F F F F F F F F F F F F F Локальное выравнивание для лучших диагоналей F F F F F F F F F F F F F F F F F Слияние участков локального сходства F F F F F F F F F F F F F F F F F F F F F F F

2 3 6
T U W

4 Руководство пользователя 5 Выбор параметров K и 6 Результаты тестирования программы
TFI Сравнение программ xhunt и pee F F F F F F F F F F F F F F F F F F F F F F F F TFIFI TFIFP TFP TFPFI TFPFP Поиск гомологов тРНК Поиск гомологов тРНК
E. coli E. coli

10 12 15
IS IS IT IT IU IU в геноме
E. coli

FFFFFFFFFFFFFF

в геномах архей F F F F F F F F F F F F F F в геномах архей F F F F F F F F F F F в геномах бактерий F F F F F

Сравнение программ xhunt и fvex F F F F F F F F F F F F F F F F F F F F F F F Поиск гомологов пяти тРНК
E. coli

Поиск гомологов группы misРНК

E. coli

7 Обсуждение 8 Выводы

20 21

I


Глава 1 Введение
Задача поиска гомологов нуклеотидных последовательностей в банке данных является одной из важнейших задач биоинформатикиF В случае кодирующих последовательностей для проE ведения такого поиска успешно используется программа fvexF Но для поиска гомологов некодирующих последовательностей вполне удовлетворяющего инструмента нетF Для этого используется ряд программD самые распространенные из них " pee PD WD fvex QD RD IH и disontiguous wiqefve IID однако каждая из этих программ обладает существенным недостаткомF pee при сравнении двух последовательностей выдает только одно выравE нивание " тоD которое имеет наивысший счет среди всех найденных выравниванийF Однако очень часто в последовательности из базы данных есть и другие значимые участкиD гомоE логичные входной последовательностиF ИзEза тогоD что выравнивание с ними обладает чуть меньшим счетомD чем лучшее выравниваниеD они не обнаруживаются программойF fvex использует ускоренный алгоритм поискаD записывая положение в базе данных всех слов длиE ной x нуклеотидов @x a UD II или ISAF Но такой подход приводит к уменьшению чувствиE тельностиX если в гомологичной последовательности не встретится участок длиной x буквD полностью совпадающий с участком входной последовательностиD то выравнивание этих двух последовательностей не обнаружитсяF hisontiguous wiqefve индексирует в банке данE ных не словаD а паттерны длиной tF Паттерн соответствует словуD если в них совпадает хотя бы букв в определенных местахF Это призвано увеличить чувствительностьD но на пракE тике в большинстве случаев чувствительность в сравнении с fvex уменьшаетсяF Целью настоящей работы было создание компьютерной программы для поиска гомологов нуклеоE тидных последовательностейD превосходящей по чувствительности как программу peeD так и программу fvexF

P


Глава 2 Литературный обзор
Существует два основных подхода к построению выравнивания двух последовательностей " глобальное и локальное выравниваниеF Оба этих подхода предназначены для построения выравнивания с максимальным весомF Различие состоит в томD что в первом случае выE равнивание включает в себя обе последовательности целикомD а во втором для достижения максимального веса разрешается ограничиться лишь отрезками последовательностейF Общий вес для каждого выравнивания вычисляется как сумма трех слагаемыхF Первое слагаемое " количество позиций выравниванияD в которых содержатся одинаковые буквы @нуклеотидыAD умноженное на некоторое положительное число " цену совпадения @mthAF Второе слагаемое " количество позиций выравниванияD в которых содержатся разные буквыD умноженное на некоторое отрицательное число " цену несовпадения @mismthAF Третье слаE гаемое " штраф за гэпыD неположительное числоD которое зависит от наличия и количества гэпов в выравниванииF Диагональю при сравнении двух последовательностей называется диагональ матрицы " таблицы локального сходстваF Ее также можно описать как сдвиг одной последовательноE сти относительно другойD или как полное выравнивание с гэпами только по краямF Все эти определения эквивалентныF Для построения локального выравнивания обычно используется алгоритм Смита " ВаE термана U или его модификацииF Основное же различие среди программ поиска гомологов нуклеотидных последовательностей заключается в методах предварительного поиска участE ков возможного локального сходстваF Основные подходы и алгоритмыD используемые в поиске сходных последовательностейD описаны в следующих работахX IF urlinD F nd eltshulD F pF IWWHF wethods for ssessing the sttistil signi(ne of moleulr sequene fetures y using generl soring shemesF При построении выравнивания важной задачей является оценка значимости найденE ного выравниванияF Для случая локального выравнивания без разрывов @без гэповA в статье предлагается использовать статистический подходD основанный на распределеE нии максимума весов выравнивания по независимым случайным последовательностямF

Q


Чем меньше вероятностьD что этот максимум будет большеD чем вес найденного выравE ниванияD тем более значима эта находкаF Ожидаемое число выравниваний по случайным последовательностям с весомD превыE шающим SD может быть рассчитано по формулеX

E = K mne-S ,

@PFIA

где m и n " длины сравниваемых последовательностейD а K и " некоторые постоянE ныеF Полученное значение E в литературе часто обозначается как ожидаемая величиE на или expet vlue @далее по тексту E E v alueAF вычисляется как положительный корень уравнения

pi pj exp(s(i, j )) = 1,
i,j

где pi " частота встречаемости буквы iD pj " частота встречаемости буквы j D а s(i, j ) " соответствующий элемент матрицы заменF Постоянная K также зависит только от

pi D pj и s(i, j )D но вычисляется по более сложной формулеF
Необходимо отметитьD что формула @PFIA применима лишь при отрицательном матемаE тическом ожидании цены сопоставления двух случайно выбранных буквF Кроме тогоD алгоритм Смита " Ватермана выдает осмысленный результат только при выполнении того же условия @хотя формально может быть примен?н и без его выполненияAF Вероятность тогоD что существует вес выравнивания большийD чем S D рассчитывается по формулеX

P (x > S ) = 1 - e-

E

При значениях E ` HDHI вероятность P практически совпадает с E F PF ersonD F F nd vipmnD hF tF IWVVF smproved tools for iologil sequene omprisonF В данной статье предложена программа peeD предназначенная для эвристического поиска последовательностей @в том числе нуклеотидныхAF Для нахождения локальноE го выравнивания с высоким весом она использует процедуруD состоящую из четырех этаповF На первом этапе создается таблицаD в которую заносится расположение всех одинаковых букв длины k tup в двух последовательностяхF Для нуклеотидных последоE вательностей k tup может принимать значения от Q до TF Затем отбираются IH лучших @с наибольшим количеством совпадений словA диагоналейF На втором этапе в отобранных диагоналях ищутся безразрывные участки с максиE мальным весомD так называемые затравкиF На третьем этапе проверяетсяD можно ли соединить эти затравкиD используя разрывы и учитывая штрафы за нихF НаконецD для последнего этапа отбираются диагоналиD лежащие вокруг одного участка с самым высоким счетомD на которых вновь проводят локальное выравнивание с помощью моE дифицированных алгоритмов Нидельмана " Вунша и Смита " ВатерманаF

R


Программа pee является самой ранней программой поиска гомологов среди распроE страненных ныне аналоговD и для нуклеотидных последовательностей считается самой чувствительнойF QF eltshulD F pFD qishD FD willerD FD wyersD iF F nd vipmnD hF tF IWWHF fsi lol lignment serh toolF Предложенная в статье программа fve перед началом поиска индексирует послеE довательности из банка данныхF При этом создается списокD содержащий все слова фиксированной длиныD которые локально выравниваются с этими последовательностяE ми с весом выше порогового значенияF Для каждого слова указывается расположение всех участковD с которыми оно выровнялосьF Длина слова для нуклеотидных последоE вательностей " UD II @по умолчаниюA или ISF Затем происходит собственно поискD в ходе которого все слова той же длины из последовательности запроса сравниваются со слоE вамиD найденными в базе данных при индексацииF Если найдена пара одинаковых словD то начинается процесс расширения совпадающего участкаF Расширение происходит без разрывовD в обоих направлениях и до достижения максимального весаF Получающиеся в ходе этого выравнивания выдаются в качестве результатаF RF eutshulD F pFD wddenD F vFD h'erD eF eFD hngD tFD hngD FD willerD F nd vipmnD hF tF IWWUF qpped fve nd sEfveX new genertion of protein dtse serh progrmsF В данной статье описывается новая версия программы fveD которая расширяет совпадающие участки и строит выравнивания с учетом возможных разрывовF SF hisontiguous wiqefveX httpXGGwwwFniFnlmFnihFgovGlstGdisontiguousFshtml hisontiguous wiqefve по сравнению с fvex предназначен для поиска более дальних гомологовF При индексации банка данных записываются не целые словаD а паттерны длиной t @t a ITD IV или PIAF Каждому типу паттернов также соответствует число W X считаетсяD что паттерн подобен словуD если в них совпадает хотя бы W букв в определенных местах @W a II или IPAF После индексации банка данных каждое слово из последовательности запроса сравнивается с записанными паттернамиD и при нахождении подобных паттернов соответствующий участок расширяется подобно томуD как это происходит в программе fvexF Для поиска используется несколько различных типов паттерновD предназначенных для поиска гомологов различной степени сходства для кодирующих или некодирующих поE следовательностейF

S


Глава 3 Описание программы
Ниже изложены основные принципы работы созданной программы xhuntD а также входные и выходные данныеF На вход программе подается файл с банком последовательностей и файл с одной поE следовательностью @запросAD для которой мы хотим найти гомологи из базы данныхF Все последовательности должны быть представлены в pee!форматеF Работа программы соE стоит из трех основных этаповX поиск наилучших диагоналейD локальное выравнивание для найденных наилучших диагоналей и слияние лучших локальных выравниванийF

3.1

Поиск наилучших диагоналей

Диагональ численно определяется сдвигом одной последовательности относительно другойF Вначале программа индексирует последовательность запросаF При этом для каждого возE можного слова длиной w + 1 запоминаются местаD в которых в этой последовательности встретились оно само или его соседиF Слово e является соседом слова fD если выполняютE ся следующие условияX " длины слов e и f совпадают " первые буквы слов e и f совпадают " хотя бы w букв в одинаковых позициях в словах e и f совпадают НапримерD для слова
ata, atc, att, agg, acg, aag atg

всеми возможными соседями являются следующие словаX

Значение w является параметром программы и задается пользователемF Точно так же индексируется последовательностьD комплементарная к последовательности запросаF После этого начинается проход по последовательностям базы данныхF При этом проE грамма поочередно просматривает все позиции каждой последовательности базыD сдвигаясь на один нуклеотидF Для каждой позиции находится слово длиной w + 1D которое начинаетE ся в данной позицииF НапримерD для последовательности найдены следующие словаX
aaa, aat, att, ttc, tcg, cgg, ggc, gca, cat, att, tta aaattcggcatta

при w + 1 = 3 будут

Все буквыD отличные от eD D q и gD заменялись буквой e @это упрощает и ускоряет проE T


цедуру поиска диагоналейD при этом практически не влияя на результатAF Затем для каждого словаD найденного в позиции y последовательности базыD искалось идентичное ему слово из результата индексации запросаF Пусть оно @в качестве себя самого или соседа другого слоE ваA встречалось k раз в запросе в позициях bi F Тогда для всех i от I до k счет для каждой диагоналиD численно задаваемой выражением

y - bi + lenq uery - w,
увеличивается на единицуF Здесь и далее lenq uery " длина последовательности запросаF Для ускорения работы программы слишком длинные последовательности базы данных нарезаются на более короткие кускиD каждый из которых далее обрабатывается независимоF Чтобы предотвратить возможную потерю хороших диагоналейD к началу каждого следующеE го куска добавляется окончание предыдущегоD равное по длине последовательности запросаF После прохождения таким образом всей базы данных из всех возможных диагоналей отбиE раются теD для которых выполняется условиеX

Dk Eq + ћ p,

@QFIA

где Dk " счет k Eой диагоналиD p " задаваемый пользователем параметрD Eq " ожидаемый счет и " среднеквадратичное отклонениеF Эта оценка основана на предположенииD что в каждой позиции каждой диагонали Pn " вероятность случайного совпадения слова из последовательности запроса и слова из банка данных " одинакова и зависит только от длины словаF Такая вероятность может быть вычислена по формуле Pn =
1+3ћw 4w+1

D где w + 1 " длина

словаF Тогда ожидаемый счет для каждой диагонали может быть рассчитан как произведение длины запроса @то есть длины диагоналиA на вероятность совпадения слов в одной позицииX

Eq = Pn ћ lenq uery ,
В рамках предложенной модели количество соседей для каждой диагонали имеет биномиE нальное распределениеD для которого среднеквадратичное отклонение задается следующей формулойX

=

lenq uery ћ Pn ћ (1 - Pn )

Таким образомD чем больше счет диагонали отличается от ожидаемогоD тем более вероE ятноD что она не является случайной и на ней следует провести локальное выравниваниеF

3.2

Локальное выравнивание для лучших диагоналей

Для отобранных вышеописанным способом лучших диагоналей в несколько итераций проE водится локальное выравнивание с помощью упрощ?нного алгоритма Смита " ВатерманаF ПосмотримD как это происходитD на примере одной короткой диагоналиF Сначала обе последовательности в соответствии с номером диагонали записываются друг под другомX U


g q g e e

e

g g

g e

q q

g g

q g

e

e e e g q q

Затем удаляются краевые участкиD в которых представлена только одна последовательE ность и в которых выравнивание невозможноX g e e g g g e q q g g q g e e e

Далее с правого края добавляется лишняя пара букв @pAD а все позиции @пары буквA нумеруютсяD начиная с левого краяX I g e P e Q g g R g e S q q T g g U q g V e W e e IH p p

Затем каждой позиции такого выравнивания присваивается число в соответствии со слеE дующими правилами @параметры match и mismatch задаются пользователемAX " последней по счету позиции @с парой букв pA присваивается число HF " если в позиции под номером n буквы совпадаютD то ей присваивается число Sn+1 +matchD где S
n+1

" числоD присвоенное позиции n + 1D match " натуральное числоD которое по смыслу

является добавленным весом за совпадение буквF " если в позиции под номером n буквы не совпадаютD то ей присваивается число S
n+1

+ +

mismatchD где S

n+1

" числоD присвоенное позиции n + 1D mismatch " отрицательное целое
n+1

числоD которое по смыслу является штрафом за несовпадение буквF Однако если S

mismatch < 0D то позиции присваивается число HF
" для пары буквD одна или обе из которых являются кодами неопредел?нности @miguity odesAD то есть обозначают подмножества множества eD D qD gD вместо значений mth и mismth используется среднее значение цены сопоставления по всем выборам букв eD D qD g из соответствующих множествF Для примера в приведенном ниже выравнивании использованы следующие значенияX

match = 5, mismatch = -4F
I g e Q P e U Q g g II R g e T S q q IH T g g S U q g H V e I W e e S IH p p H

Затем выбирается позицияD которой присвоено наибольшее число @в данном случае это позиция под номером QAF От этой позиции вправо начинается расширение выравниванияD которое заканчивается первой встреченной позициейD которой присвоено число H @в данном случае это позиция UAF Таким образомD в первое найденное локальное выравнивание попадаE ются позиции от Q до T включительноF После этого участок найденного выравнивания вырезаетсяD а участкиD оставшиеся по краямD проверяются на длинуF Если их длина больше заданного пользователем параметра V


L @по умолчанию L a IHAD то с ними по отдельности происходит так же процедураD что и с
исходным выравниваниемD и так далееD пока не останется ни одного кусочкаD большего или равного LF Каждому вырезанному участку локального выравнивания сопоставляется счет

S D равный числуD присвоенному первой позиции этого участка @в нашем примере это число 11AF

3.3

Слияние участков локального сходства

Среди найденных участков локального сходства отбираются теD для которых вес

S z ћ match,

@QFPA

где z " натуральное числоD которое задается пользователемF Отобранные участки со всех диагоналей сортируются по номеру позиции в банке данныхD с которого они начинаютсяF В том случаеD если пара соседних участков расположена достаточно близкоD из запроса и из банE ка данных вырезаются последовательности максимальной длиныD лежащие между началом первого участка и концом второгоF Эти две последовательности выравниваются алгоритмом Смита " Ватермана для локального выравнивания двух последовательностей с афинными штрафами за гэпыF Афинные штрафы означаютD что штраф за участок идущих подряд n гэпов рассчитывается как сумма -GapOpen - n ћ GapE xtentionD где GapOpen E штраф за открытие участка гэповD GapE xtention E штраф за каждый гэп в отдельностиF Оба этих параметра являются неотрицательными целыми числами и задаются пользователемF Если счет получившегося выравнивания большеD чем счет каждого из первоначальных участковD первый участок из пары удаляетсяD а второй заменяется на новое выравниваниеF Далее проверяется следующая параD в которой второй участок из предыдущей пары станоE вится первымD и так далее до проверки последней парыF Все оставшиеся участкиD которые не были слиты с соседямиD также выравниваются алE горитмом Смита " ВатерманаF Далее по формулеD предложенной в ID для каждого выравнивания вычисляется E v alueX

E v alue = K mne-S ,
где m и n " длины последовательностей запроса и базы данныхD а K и " некоторые постоянныеD получение которых описано в главе SF В выходной файл записываются все участки локального выравнивания с E v alueD меньE шим или равным пороговому значению E v alueD которое также задается пользовательским параметромF Программа реализована на языке программирования СF

W


Глава 4 Руководство пользователя
Исполняемые файлы для архитектур vinux xVTGmdTR и исходный код программы для самоE стоятельной компиляции доступны по адресуX пускаX
nhunt -i input.fasta -d database.fasta http://mouse.b elozersky.msu.ru/

~

b ennigsen/nhunt

Программа запускается из командной строкиD ниже приведен минимальный формат заE D

где inputFfst " название файла с последовательностью запросаD dtseFfst " название файла с последовательностями банка данныхF Полный список ключей программыX IF Ключ !iF uery pileF Название файла с последовательностью запросаD для которой веE дется поиск гомологовF Обязательный параметрF PF Ключ !dF htseF Название файла с последовательностями банка данныхD в которых ведется поиск гомологовF Обязательный параметрF QF Ключ !oF nhunt report yutput pileF Название выходного файлаD в который записываются результаты работы программыF Значение по умолчаниюX nhuntFoutF RF Ключ !eF ixpettion vlueF Положительное числоF Порог на значение iEvlueF ВыравE нивания с iEvlueD превышающим заданный этим параметром порогD не выдаются в результатахF Значение по умолчаниюX IFH SF Ключ !sF winiml sore for output lignmentsF Неотрицательное целое числоF Порог на значение счета выравниванияF Выравнивания с счетом меньшимD чем заданный этим параметром порогD не выдаются в результатахF Значение по умолчаниюX H TF Ключ !pF higonls seletion thresholdF Положительное числоF Порог для отбора лучших диагоналей @смF формулу @QFIAAF Значение по умолчаниюX IHF UF Ключ !wF xumer of oinident lettersF Натуральное числоF Минимальное количество буквD которые должны совпадать в двух соседних словахF Значение по умолчаниюX SF VF Ключ !zF ore thresholdF Натуральное числоF Определяет минимальный счет для участE ка локального сходства @смF формулу @QFPAF Значение по умолчаниюX SF IH


WF Ключ !rF ewrd for nuleotide mthF Неотрицательное целое числоF Цена совпадения двух букв в выравниванииF Значение по умолчаниюX SF IHF Ключ !qF enlty for nuleotide mismthF Неположительное целое числоF Цена за несовпадение двух букв в выравниванииF Значение по умолчаниюX ERF IIF Ключ !qF gost to open gpF Неотрицательное числоF Штраф за появление группы идущих подряд гэпов в выравниванииF Значение по умолчаниюX IHF IPF Ключ !iF gost to extend gpF Неотрицательное числоF Штраф за появление каждого нового гэпа в выравниванииF Значение по умолчаниюX SF IQF Ключ !mF elignment view optionF Данный параметр определяет вид выходного файлаF Возможные значенияX HF Выходной файл содержит выровненные последовательности и информацию об этих выравниванияхF VF Выходной файл содержит таблицу с информацией о выравниванияхD но не сами выравниванияF WF То жеD что в предыдущем пунктеD но в файле также содержатся комментарии к таблицеF Значение по умолчаниюX HF Актуальный список параметров можно получитьD вызвав программу без параметровF

II


Глава 5 Выбор параметров K и
Строго говоряD формула @PFIA применима только для подсчета вероятностей появления выE равниваний без гэпов @без разрывовAF При том же условии выводятся и формулы для расчета параметров K и F Общей формулы для подсчета вероятностей появления выравниваний с гэпами в настоящий момент не существуетF В связи с этим для расчета E v alue в програмE ме была использована формула @PFIAD однако параметры K и были выведены на основе статистического моделированияF Процедура моделирования состояла из нескольких этаповX IF Программа nhunt запускалась для поиска гомологов случайных последовательностей запроса на случайных базах данныхF Случайные последовательности генерировались на основе бернуллиевской моделиD то есть вероятности появления каждой из четыE рех букв в каждой позиции были одинаковы и независимыF Длина последовательности банка данных " 5 ћ 106 D длины последовательностей запроса " SHD USD IHHD ISH и PHHF Программа запускалась по IH раз для каждой из длин запросаD причем для каждого нового поиска заново генерировалась как последовательность запросаD так и последоE вательность банка данныхF PF Все веса найденных в результате этих запусков выравниваний были отсортированы по возрастаниюF Затем для каждого Si @значения iEтого весаA была вычислена величина

Ei =

Nalign nћm

D где m, n " длины последовательностей запроса и базы данныхD а Nal

ig n

"

число найденных выравниванийD вес которых оказался большимD чем Si F QF Введем величину Pi = K e- равенство
Si

D где K и " искомые параметрыF Из формулы @PFIA

видноD что в том случаеD когда эти параметры подобраны верноD дожно выполняться

Nal

ig n

= nmK e-

Si

Pi = Ei .

СледовательноD наша цель " подобрать значение Pi таким образомD чтобы оно было как можно ближе к экспериментальному значению Ei F Введем также обозначения fi =

ln P

i+1

- ln Pi и Fi = ln Ei

+1

- ln Ei F Такие замены были произведены для тогоD чтобы
i

подбирать параметры по очередиX вначале путем минимизации разницы между fi и F подбирается параметр D а затем уже параметр K F IP


Легко видетьD что единсвенным аргументом функции fi является X

fi = ln P

i+1

- ln Pi = ln K e-

Si+1

- ln K e-Si = ln K - Si

+1

- ln K + Si = (Si - Si+1 )

Оптимальное значение w параметра было подобрано методом наименьших квадратов с использованием математического пакета qx ytveX

w = arg min(
i

(Fi - fi )2 )

RF Для нахождения оптимального значения Kw параметра K приравняем Ei = Pi и решим получившиеся уравнения Ei = K e-
w ћS
i

относительно K F Среднеарифметическое этих и w достаточно сильно зависили

решений и определим как оптимальное значение Kw F Необходимо отметитьD что получаемые значения K
w

от тогоD используем ли мы для оптимизации весь отсортированный список весов Si или лишь его частьD начиная с некоторого Sk F На наш взглядD это может свидетельствовать о томD что истинный вид зависимости E v alue от счета выравнивания с гэпами отличается от зависимостиD предложенной в формуле @PFIAF Так как нас в первую очередь интересует E v alue для высоких значений счета @то есть для редко встречаемых выравниванийAD то в некоторых случаях для оптимизации использовался список весов лишь начиная с некоторого Sk F Такой подход позволял точнее оценить Kw и w для высоких значений счетаF Таблица SFIX Значения Kw и w при различных параметрах match mismatch GapOpen GapE xtention Kw w S S S S S S S S S S S S S S S S S S EP EP EP EQ EQ EQ ER ER ER ES ES ES EIH EIH EIH EIS EIS EIS IH IS PH IH IS PH IH IS PH IH IS PH IH IS PH IH IS PH S S S S S S S S S S S S S S S S S S HFHHS HFIWP HFHI HFHUI HFPHP HFIS HFIHU HFIUP HFHVS HFHTS HFQQP HFQVQ HFPRT HFST HFTHR HFQTS HFRHU HFPVV HFHTS HFHUR HFHWV HFITW HFIVS HFIVP HFPHR HFPIR HFPHR HFPHT HFPQQ HFPQS HFPT HFPUT HFPUU HFPUS HFPUV HFPUI

IQ


Процедура оптимизации проводилась для каждого набора параметров {matchD mismatchD

GapOpenD GapE xtention} @смF главу RAD где match = 5D mismatch принимает одно из знаE
чений набора {-2, -3, -4, -5, -10, -15}D GapOpen " одно из значений набора {10, 15, 20}D

GapE xtention = 5F Полученные значения Kw и w представлены в таблице SFIF Другие паE
раметры программы подбирались таким образомD чтобы получить максимальное число найE денных выравниваний за разумное времяF Пользователь также может задать параметры match = R и mismatch = QD которые отличаются от представленных в таблицеF В том случаеD если значения параметров R и Q удовлетворяют требованию отрицательного математического ожидания цены сопоставления двух случайно выбранных буквD то оба значения умножаются на величину 5/RD вследствие чего значение параметра match становится равным 5 и таким образом как бы нормируется по таблице SFIF В ином случае пользователю предлагается выбрать другие параметрыF Если

Q ћ 5/R < -15D пользователю также предлагается ввести другие значения параметровF
Параметры GapOpen и GapE xtention нормируются на значение match = 5 по вышеE описанной процедуреD аналогично параметру mismatchF Если получившиеся новые значения отличаются от представленных в таблицеD то для дальнейших вычислений выбираются наE боры параметровD который ближе всего к заданным пользователем значениям GapOpen и

GapE xtentionY кроме тогоD программа выдает предупреждениеD что расчет E v alue может
быть некорректнымD и предлагает использовать варианты значений параметров из таблицы SFIF Далее параметры Kw и w подбираются методом линейной интерполяцииD основываясь на уже вычисленных значениях Kw и w для различных наборов параметровF Для компенE сации изменения значений параметров в 5/R раз окончательное значение вычисляется следующим образомX
w

параметра

w = w ћ 5/R

IR


Глава 6 Результаты тестирования программы
Для сравнения программы xhunt с программами pee и fvex они были попарно заE пущены для поиска гомологов различных РНК в геномах различных прокариотF ПоказатеE лем качества программы служит количество находокD имеющих вес не меньше заданногоF Для тогоD чтобы такое сравнение было корректноD вес каждой находки программ pee и fvex пересчитывался в соответсвии с параметрамиD заданными для программы xhunt по умолчаниюF

6.1

Сравнение программ Nhunt и F ASTA
E. coli

Программы xhunt и pee тестировались на поиске гомологов валиновой тРНК в геноме
E. coli

и в геномах пяти различных архейных микроорганизмовF Для каждой из

программ было измерено время работы и количество находокD имеющих вес большеD чем заданные значенияF Программа xhunt была запущена с параметрами по умолчаниюD проE грамма pee E с параметрами GapOpen = 10D GapE xtention = 5 и k tup = 3 @описание последнего параметра смF в главе PAY значение остальных параметров также были заданы по умолчаниюF В таблицах с результатами тестирования для каждой из сравниваемых программ предE ставлены время ее работы в секундах и количество находокD вес которых не меньшеD чем различные заданные значения весовF Кроме тогоD для каждого из заданного значения весов в скобках представлено значение E v alueD вычисленное по формуле @PFIAY значения параметE ров k и взяты из таблицы SFIF
6.1.1 Поиск гомологов тРНК E. coli в геноме E. coli
E. coli

Входная последовательностьX валиновая тРНК нуклеотидовA Последовательность базы данныхX геном тидовA

@длина последовательности E UU

E. coli K-12

@длина генома " RTQWTUS нуклеоE

Результаты тестирования представлены в таблице TFIX IS


Таблица TFIX Количество находок гомологов тРНК

E. coli

в геноме

E. coli

Программа pee xhunt

Время RFU HFT

QHH @1 ћ 10-19 A P P

PHH @7 ћ 10-11 A T T

ISH @2 ћ 10-6 A PI PI

IHH @5 ћ 10-2 A QV RT

US @8.6A SV VQ

6.1.2

Поиск гомологов тРНК E. coli в геномах архей
E. coli

Входная последовательностьX валиновая тРНК нуклеотидовA Последовательности базы данныхX геномы архей
DSM 9790

@длина последовательности E UU

Archaeoglobus fulgidus DSM 4304D Halobacterium

sp. NRC-1D Sulfolobus solfataricus P2D Pyrobaculum aerophilum str. IM2D Picrophilus torridus

@суммарная длина геномов " IHWSQPHW нуклеотидовA

Результаты тестирования представлены в таблице TFPX Таблица TFPX Количество находок гомологов тРНК Программа pee xhunt Время SFS IFR IRH @4 ћ 10-19 A I P IPH @2 ћ 10-3 A T V
E. coli

в геномах архей VS @2.7A PU RP US @20.5A RW IPW PQ

IHH @0.12A IR IU

6.2

Сравнение программ Nhunt и BLASTN
E. coli

Программы xhunt и fvex тестировались на поиске гомологов нескольких тРНК пы misxe
E. coli

в геномах пяти различных архейных микроорганизмовD а также на поиске гомологов групE в геномах трех бактерийF Для каждой из программ было измерено количество находокD имеющих вес большеD чем заданные значенияF Программа xhunt быE ла запущена с параметрами по умолчаниюD программа fvex " с подобранными нами параметрамиD при которых находится наибольшее число выравниванийF Ниже представлена строка запуска программы fvexX
blastall -p blastn -F F -W 7 -r 5 -q -4 -G 10 -i input.fasta -d database.fasta

Здесь ключ -r задает цену за совпадение двух буквD -q " цену за несовпадениеD -G " штраф за появление группы гэповD -E " штраф за отдельный гэпD -W E длину слова при индексации базы данных @описание последнего параметра смF в главе PAF Остальные параметры заданы по умолчаниюF В таблицах с результатами тестирования для каждой из сравниваемых программ предE ставлено количество находокD вес которых не меньшеD чем различные заданные значения IT


весовF Кроме тогоD для каждого из заданного значения весов в скобках представлено значеE ние E v alueD вычисленное по формуле @PFIAY значения параметров K и взяты из таблицы SFIF
6.2.1 Поиск гомологов пяти тРНК E. coli в геномах архей
E. coli

Входные последовательностиX пять тРНК леотидаA

" валиноваяD селеноцистеиноваяD асE

парагиноваяD лейциновая и аргининовая @средняя длина последовательностей E VP нукE

Последовательности базы данныхX геномы архей
DSM 9790

Archaeoglobus fulgidus DSM 4304D Halobacterium

sp. NRC-1D Sulfolobus solfataricus P2D Pyrobaculum aerophilum str. IM2D Picrophilus torridus

@суммарная длина геномов " IHWSQPHW нуклеотидовA

Результаты тестирования представлены в таблице TFQX Таблица TFQX Количество находок гомологов пяти тРНК Программа fvex xhunt PHH @2 ћ 10-10 A I P ISH @5 ћ 10-6 A IV PI
E. coli

в геномах архей US @21.8A IQW QSU

IPS @8 ћ 10-4 A QV SR

IHH @0.13A US IPI

Кроме тогоD в данном тестировании координаты найденных гомологов сравнивались с координатами аннотированных в геномах архей тРНКF Для каждого найденного выравниваE ния была подсчитана длина правильного фрагмента @то есть число нуклеотидов гомологаD лежащих в пределах координат аннотированной тРНКA и длина неправильного фрагменE та @то есть число нуклеотидов гомологаD лежащих вне предела координат аннотированной тРНКAF Результаты подсчета представлены на рисF TFIF На данном графике каждой проE грамме соответствует графикD а каждому найденному выравниванию соответствует точкаF Значение ординаты этой точки выражает суммарную длину правильных фрагментов для всех выравниванийD имеющих счет большийD чем данноеF Значение абсциссы выражает сумE марную длину неправильных фрагментов для всех выравниванийD имеющих счет большийD чем данноеF ТочкиD обозначающие самые лучшие выравниванияD находятся в начале коордиE натной сеткиF СледовательноD при заданном значении абсциссы качество программы можно охарактеризовать площадью под графикомX действительноD площадь тем большеD чем больше суммарная длина найденных правильных фрагментовF В этом тесте для сравнения была также запущена программа fvex с параметрами по умолчанию @обозначена как fvex @defultAAF
6.2.2 Поиск гомологов группы miscРНК E. coli в геномах бактерий

Под misРНК бактерии будем понимать все РНКD которые не являются транспортными или рибосомальнымиF ОчевидноD что в данную группу входит также большое число тF нF анE IU


9000 8000 7000 6000 5000 4000 3000 2000 1000 00 500 1000

Nhunt BLASTN BLASTN (default)
1500 2000

РисF TFIX Суммарное число правильных и неправильных фрагментов тисмысловых РНКD которые полностью или частично кодируют последовательностьD комE плементарную гену бактерииY это свойство обеспечивает клетке дополнительную ступень регуляции трансляцииF Поэтому для тогоD чтобы не сравнивать последовательности генов различных бактерийD из всей совокупности misРНК имеют гомологов среди генов
E. coliF E. coli

были выбраны теD которые не где проаннотированно
E.

В штамме

Escherichia coli 55989D

наибольшее число misxe @IIHAD таковых оказалось TRF В качестве последовательностей банка данных были выбраны три бактерииD отличные друг от друга по степени родства с
coli

F Входные последовательностиX группа из TR misРНК следовательностей E IRP нуклеотидаA Последовательности базы данныхX геномы бактерий
aeruginosa PAO1 Bacil lus cereus B4264D Pseudomonas E. coli 55989

@средняя длина поE

и

Yersinia pestis KIM

@средняя длина геномов " SRPVHTS нуклеотидовA

Результаты тестирования представлены в таблице TFRX

IV


Таблица TFRX Количество находок гомологов группы misxe Программа
B. cereus

E. coli

в геномах бактерий US @18.7A VSW RIQS QTW PHTH TVR PUWT

PHH @1.6 ћ 10-10 A P P R R PQ PS

ISH @4 ћ 10-6 A S T T V PW QH

IPS @7 ћ 10-4 A IR IS II IQ QR RI

IHH @0.11A IRT PQV WU IVU IIP ITU

fvex xhunt
P. aeruginosa

fvex xhunt
Y. pestis

fvex xhunt

Была также предпринята попытка оценить качество полученных выравниваний способомD аналогичным описанному в разделе TFPFIF Под правильными фрагментами в данном случае понимаются фрагменты гомологаD принадлежащие межгенным промежуткамF ПоказаноD что в находках обеих программ практически независимо от выбранного веса суммарная длина правильных фрагментов выравниваний с б? ольшим весом примерно в два раза превосходит суммарную длину неправильных фрагментовF Значение данного соотношения пока остаE ется неяснымY ожидалосьD что с падением веса иD следовательноD качества находок данное соотношение будет резко падатьD так как по суммарной длине доля межгенных участков не превышает IS 7 по отношению к длине всего геномаF

IW


Глава 7 Обсуждение
Результаты тестирований показалиD что по чувствительности @то есть по количеству нахоE док с весомD больше заданногоA программа xhunt превосходит как программу peeD так и программу fvexF Это различие менее заметно в области больших весов и становится все ? более выражено при уменьшении порогового весаF Это говорит о томD что хорошие выравE нивания с большим весом одинакого хорошо обнаруживаются всеми программамиD однако ? значительное число менее качественных находок обраруживается лишь программой xhuntF Другая оценкаD независимая от веса выравнивания и направленная на подсчет суммы правильных фрагментовD также показала превосходство программы xhuntF Более высоE кая площадь под графиком для этой программы @смF рисF TFIA по сравнению с програмE мой fvex означаетD что выравниванияD найденные программой xhuntD но не найденные программой fvexD являются правильными иD следовательноD обладают биологическим смысломF По скорости работы программа xhunt заметно превосходит программу peeD хотя и работает гораздо медленнееD чем программа fvexF Дальнейшие планы по улучшению программы xhunt включают в себя также ускорение программыF Кроме тогоD программа xhunt имеет множество параметровD позволяющих регулировать соотношение скорость работыGчувствительностьF ПараметрыD заданные по умолчаниюD на наш взглядD позволяют достичь разумного компромисса между этими значениямиF Однако за счет увеличения времени работы чувствительность можно заметно повыситьF Дополнительно показаноD что программа fvex с подобранными нами параметрами заметно провосходит программу fvexD запущенную с параметрами по умолчаниюF Это может означатьD что параметры по умолчанию в программе fvex подобраны неоптиE мальноF

PH


Глава 8 Выводы
IF Нами была создана компьютерная программа xhunt для поиска гомологов нуклеотидE ных последовательностейF PF Эта программа была успешно протестирована на ряде примеровD определены значения параметровD необходимых для правильной оценки значимости найденных выравниваE нийF QF При сравнении программы xhunt с аналогичными программами показаноD что она преE восходит программу pee как в скоростиD так и в чувствительностиD и превосходит в чувствительности программу fvexF

PI


Литература
IF urlinD F nd eltshulD F pF IWWHF wethods for ssessing the sttistil signi(ne of moleulr sequene fetures y using generl soring shemesF roeedings of the xtionl edemy of ienes of the e VUXPPTREPPTVF PF ersonD F F nd vipmnD hF tF IWVVF smproved tools for iologil sequene omprisonF roeedings of the xtionl edemy of ienes of the e RXPRRREPRRVF QF eltshulD F pFD qishD FD willerD FD wyersD iF F nd vipmnD hF tF IWWHF fsi lol lignment serh toolF tournl of woleulr fiology PISXRHQERIHF RF eutshulD F pFD wddenD F vFD h'erD eF eFD hngD tFD hngD FD willerD F nd vipmnD hF tF IWWUF qpped fve nd sEfveX new genertion of protein dtse serh progrmsF xulei eids eserh PSXQQVWEQRHPF SF hemoD eF nd urlinD F IWWIF trong limit theorems of empiril funtionls for lrge exeednes of prtil sums of iFiFdF vrilesF ennls of roility IWXIUQUEIUSSF TF Дурбин РFD Эдди ШFD Крог АFD Митчисон ГF Анализ биологических последовательностейF МFEИжевскD НИЦ Регулярная и хаотическая динамикаD Институт компьютерных исслеE дованийD PHHTF UF mithD F pF nd termnD wF F IWVIF sdenti(tion of ommon moleulr susequenesF tournl of woleulr fiology IRUXIWSEIWUF VF qote FD eermhneni F nd wklowski F wstering seeds for genomi size nuleotide fve serhesF xulei eids eserhD PHHQD QIXTWQSETWRIF WF httpXGGfultyFvirginiFeduGwrpersonGfstG IHF ftpXGGftpFniFnlmFnihFgovGlstGexeutlesGlstCGveiGusermnulFpdf IIF httpXGGwwwFniFnlmFnihFgovGlstGdisontiguousFshtml

PP