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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

Исследование биологических текстов является одной из актуальнейших задач современного естествознания. При этом под биологическими текстами понимаются символьные модели нуклеотидных и аминокислотных последовательностей. Процесс перевода последовательности нуклеотидов, составляющих ДНК, в символьную последовательность называется процессом секвенирования. При этом предполагается, что исследование таких, доступных моделей, как символьные позволит судить о реальном объекте. Одной из последних диссертаций на соискание степени доктора физико-математических наук, в которых объектом исследования является нуклеотидная последовательность, является диссертация Садовского М.Г. [1]. В ней отмечается, что: «символьные последовательности являются классическим объектом математики, а также встречаются как предмет изучения во многих прикладных задачах - от теоретического программирования и теории управления до биологии и лингвистики». Кроме того в данной работе утверждается, что обработка информации в природе происходит малыми порциями, и этим объясняется переход от рассмотрения объекта в целом к рассмотрению ансамбля его фрагментов.

Изучение функциональных, химических, физико-химических и прочих свойств нуклеиновых кислот активно ведется специалистами в различных областях, и одним из важных направлений является изучение нуклеиновых кислот как символьных последовательностей. В настоящей работе предполагается исследовать свойства нуклеиновых кислот, которые определяются взаимным расположением нуклеотидов друг относительно друга в одной изучаемой молекуле; никакие другие факторы - физико-химическое окружение, особенности состава нуклеотидов и т.п. - не рассматриваются.

Отметим, что все исследования, объектом которых является символьная модель, не имеют возможности рассматривать функциональные, химические, физико-химические и другие свойства реального объекта. Исследователь изучает, в большинстве случаев с использованием вероятностного подхода, свойства символьной последовательности как таковой. При этом полагается, что определенные свойства реального объекта отображаются в свойства символьной последовательности.

В данной работе используется системный подход к изучению символьных последовательностей. Полагается, что символьные последовательности являются целостно-завершенными объектами и их следует рассматривать целиком. Переход от рассмотрения совокупности фрагментов последовательности к рассмотрению её как таковой дает возможность исследовать её строй, как особое свойство последовательности, имеющую корреляцию с физико-химическими, биологическими и другими свойствами, определенными взаимным расположением элементов [2, стр. 16].

Следует отметить, что рассмотрение полных геномов и отдельных генов, с точки зрения системного подхода, позволяет ставить задачу по выявлению «естественных» элементов, из которых состоит данная система. Другая важная проблема, имеющая общую значимость для любых прикладных исследований, предметом которых являются те или иные символьные последовательности, состоит в сравнении двух (или нескольких) символьных последовательностей. Дело в том, что символьные последовательности относятся к такому классу объектов, для которых определение расстояния между ними возможно, однако оно очень «бедно»: очень часто формально введённое расстояние никак не отражает близость или, наоборот, существенные различия свойств, приписываемых исследователем изучаемым символьным последовательностям. Здесь имеет смысл рассматривать меру близости двух (или нескольких) последовательностей, и для её построения информационные и статистические методы являются весьма универсальными и продуктивными.

В частности в настоящее время актуальной является проблема исследования локальной структуры (интроны, экзоны, границы генов) нуклеотидных последовательностей. Разработанный А.С. Гуменюком аппарат анализа строя знаковых последовательностей позволяет в отличие от общепринятых в биоинформатике статистических методов, учитывать также взаимное расположение.

Очевидно использование характеристик строя (описывающих целую генетическую последовательность) также и для анализа локальной структуры такой цепи, путем просмотра её окном разного размера в форме блоков или L-грамм, с последующим применением разнообразных методов анализа функций и числовых последовательностей.

Цель данной работы состоит в разработке программного комплекса и исследовании с его помощью символьных последовательностей. В программной комплексе возможны разбиения знаковой последовательности на блоки, L-граммы, L-граммы с фиксированной привязкой к началу цепочки. Также возможно вычисление спектра по Фурье и вывод графиков разбитых знаковых последовательностей.

Структура и объем работы. Работа состоит из введения, шести разделов, заключения, библиографии, включающей 35 наименований, приложения, содержащего исходный код разработанной программы. Основное содержание работы составляет 73 стр., 55 рисунка.

1. Обзор и анализ методов и программных средств обработки знаковых последовательностей

Методы анализа знаковых последовательностей можно разделить на два класса: анализирующие состав знаковых цепей и косвенно учитывающие взаимное расположение элементов цепи. В данной же работе предлагается использовать подход непосредственно учитывающий взаимное расположение элементов и называемый непосредственным анализом строя цепи. Рассмотрим некоторые методы из каждой группы.

1.1 Методы косвенного анализа структуры знаковых последовательностей на основе состава

Энтропия и информация

В работе [1] представлен обзор работ посвященных исследованию энтропийных свойств нуклеотидных последовательностей. «Изучению информационного содержания символьных последовательностей посвящено большое количество работ. Достаточно велик и поток работ, в которых изучаются информационные, либо энтропийные характеристики символьных последовательностей в связи с их приложениями к задачам молекулярной генетики, молекулярной биологии и биоинформатики. Говоря об энтропийных (или, шире, о статистических) свойствах символьных последовательностей, следует иметь в виду, что в этом случае всякую конечную последовательность следует рассматривать как элемент бесконечно длинной символьной последовательности, реализующей все возможные комбинации символов (слов) любой заданной длины. Обычно при исследовании статистических свойств символьных последовательностей не возникает путаницы, связанной с этим обстоятельством, однако следует иметь в виду, что статистические свойства могут рассматриваться лишь в связи с анализом всего ансамбля символьных последовательностей.

Если рассматривать эксперимент с n возможными исходами, имеющими вероятности осуществления р_п i = 1, 2,…, n, то информация, которую приносит сообщение о том, что реализовался определенный (i-ый) исход полагается равной .

Энтропия S характеризует неопределенность в исходе эксперимента в целом, по определению , т.е. величина S тем больше, чем меньше априорная возможность предсказания исхода эксперимента. S максимальна, если нет исходов более вероятных, чем другие для случая, то есть р, = 1/n и S_max = log₂ n [33].

Если рассматривать случай символьных последовательностей, то их можно интерпретировать с двух точек зрения. Первая состоит в том, что каждый из символов считается результатом эксперимента по выбору символа. Определив вероятности выпадения символов в эксперименте (), можно вычислить I и S, приходящиеся на одну позицию текста по указанным выше формулам. Вторая рассматривает текст в целом как результат эксперимента по генерации текста из N символов. Это позволяет ввести величины I_N и S_N, характеризующие информацию и энтропию «сложного» эксперимента, включающего N «простых» в случае независимости «простых» экспериментов , так как . В том случае, если в рассматриваемой символьной последовательности символы зависимы друг от друга, то информация на один символ (и, соответственно, энтропия) уменьшаются. Степень уменьшения информации либо энтропии существенно зависят от того, насколько неслучайны, зависимы символы, стоящие в различных местах в рассматриваемой последовательности, при этом явный вид такого рода зависимости известен далеко не всегда. Один из путей анализа статистических свойств такого рода неслучайных символьных последовательностей связан с модельными представлениями. Например, если символьная последовательность представляется Марковской цепью первого порядка с известными переходными вероятностями то энтропия приходящаяся на один символ есть

Возможны и иные модели неслучайности (упорядоченности) символьных последовательностей; для некоторых из них также можно получить явные формулы энтропии (либо информации), приходящейся на один символ.

1.2 Анализ строя цепей событий

Псевдовектор строя цепи

Основы аппарата анализа строя цепи представлены А.С. Гуменюком в работе [3]. Рассмотрим множество знаковых последовательностей конечной длины. Выделим подмножество кортежей с одинаковыми наборами чисел вхождения символов собственных алфавитов. Так как имеется ввиду неоднократное вхождение некоторых компонентов, то все множество кортежей, составленных на основе конкретного алфавита - это комбинации типа «перестановки с повторениями», каждая из которых отличается оригинальным взаимным расположением компонентов, собственной их композицией или построением.

Кортеж, в котором знаки заменены натуральными числами, как это показано на рис. 1 на примере преобразования разных знаковых последовательностей, назван порядком следования элементов, построением или строем цепи [4]. В результате таких замен все равномощные по составу знаковые последовательности, имеющие одинаковое взаимное расположение компонентов (композицию), будут отображены одной и той же последовательностью натуральных чисел, которая представляет оригинальный для данного подмножества текстов строй цепи (порядок следования элементов).

Нуклеотидная цепь 1

T

T

A

T

T

T

C

A

A

A

A

A

G

C

G

Цепь комплементарная цепи 1

A

A

T

A

A

A

G

T

T

T

T

T

C

G

C

Строй цепи 1 и цепи компементарной ей

1

1

2

1

1

1

3

2

2

2

2

2

4

3

4

Нуклеотидная цепь 2

G

C

T

C

C

T

G

C

C

A

A

T

A

G

C

Строй цепи 2

1

2

3

2

2

3

1

2

2

4

4

3

4

1

2

Рисунок 1

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

Строем цепи сообщений (событий, знаков и т.п.) назовем кортеж (упорядоченное множество), в котором каждому компоненту данной цепи в соответствие поставлено натуральное число, причем идентичные по выбранному признаку компоненты отображены одним и тем же числом. Самый первый компонент такого кортежа - единица, а все остальные первые встречные разные натуральные числа (представляющие вместе с единицей алфавит строя) возрастают на единицу.

В теоретико-множественном представлении вектором называется кортеж, компонентами которого являются числа. В соответствии с таким определением вектора назовем специфически сформированный (организованный) кортеж «псевдовектором строя».

Таким образом, строй цепи и псевдовектор строя - это синонимы одного и того же абстрактного объекта. Однако на практике следует различать «псевдовектор строя» данной цепи или некоторого их множества и «псевдовектор строя» как элемент множества разных псевдовекторов строя.

Интервально-матричная модель строя цепи событий

Как отмечено в работе [3], операция выявления в разных по природе цепях сообщений одинаковых построений расширяет возможности междисциплинарных исследований. Однако результат такой операции ограничен описанием строя в форме обычного числового кортежа, хотя и имеющего определение «псевдовектора строя». В работе [5] рассматривается более удобное для анализа формальное описание строя, которое позволяет получать приближенные компактные числовые характеристики (подобные используемым для описания случайных величин), полезные, в частности, при опознавании порядков цепей и определении степени их различия. Для определения такого формализма строя отдельного текста при обычном (естественном) способе его чтения «поэлементно-подряд» ведем две нумерации:

– первая нумерует элементы собственного алфавита (словаря) данной знаковой последовательности по мере их первой встречи;

– вторая дает сквозную нумерацию всех компонентов кортежа от начала до конца.

Разложим полную (без пустых мест на позиции) неоднородную символьную последовательность на m неполных «однородных» кортежей, в которых заняты только некоторые позиции одинаковыми знаками. Аналогом однородной последовательности является однородный поток событий, определенный в теории массового обслуживания. Вообще разложение цепи может осуществляться по разным правилам. Так ниже (для общности) представлены декомпозиции строя неоднородной знаковой цепи на неполные однородные (рис. 2) и неполные «разнородные» (рис. 3) цепи. В последнем случае позиции заняты только разными элементами, выбираемыми по следующему правилу: при просмотре цепи от ее начала в состав первой разнородной цепи выбираются все первые вхождения каждого элемента из алфавита, при втором - все вторые вхождения и т.д.

В случае правильно выполненных декомпозиций полученные множества однородных (разнородных) последовательностей будут несовместными (т.е. не содержат занятых мест с одинаковыми номерами на их позициях). Композиция или «совмещение» всех неполных однородных (разнородных) кортежей дает исходную полную неоднородную знаковую последовательность.

Определим «интервал» как расстояние от выделенного в цепи компонента, до другого ближайшего, отмеченного в направлении просмотра (рис. 2); по другому - это модуль разности номеров мест двух выделенных компонентов на позиции кортежа.

Учитывается, соответственно, «величина интервала». В дальнейшем, для краткости, будем называть эти понятия одинаково - интервал.

Назовем привычное чтение текста «подряд слева направо» «обычным способом считывания». Пусть первое считывание последовательности осуществляется отличным от обычного способом с самого начала до конца таким образом, что выбираются только элементы строя с номером «1»; при этом последний интервал определяется до знака «финиш» (возможен и другой вариант - определение первого интервала от начала текста - «старта»). Интервалы данной однородной последовательности разместим в соответствии с номерами считываемых элементов в первой строке матрицы. Далее, при втором просмотре строя текста, аналогично выберем элементы с номером «2» и разместим вектор интервалов, соответствующий другой однородной последовательности, во второй строке матрицы. В каждой следующей строке помещается вектор интервалов «новой» при очередном просмотре однородной последовательности. Одиночные слова будут представлены всего одним интервалом (до финиша), который размещается в крайнем столбце соответствующей строки матрицы. Число столбцов в «матрице интервалов» однородных цепей равно числу вхождений самого частого слова текста. Незанятые интервалами элементы матрицы заполним нулями. Число строк m равно мощности собственного алфавита или словаря текста. Результаты описанных действий представлены на рис. 2.



Рисунок 2 Декомпозиция строя неоднородной знаковой цепи на неполные однородные цепи и их матрица

Пусть считывание текста осуществляется вторым (выше описанным) способом по разнородным цепям. В результате получим матрицу интервалов разнородных цепей, в которой число столбцов равно m, а число строк - .

Рисунок 3 Декомпозиция строя неоднородной знаковой цепи на неполные разнородные цепи и их матрица

Некоторые числовые характеристики строя цепи и их распределения

Используем понятие однородной знаковой последовательности и векторное отображение ее строя в виде соответствующей строки матрицы интервалов для определения числовых характеристик строя текста [3, 6-12].

Абсолютный объем строя j-ой однородной цепи определяется в виде

,

где - интервал от i-го до -го вхождения j-го символа, - число вхождений j-го символа.

Средний геометрический интервал между занятыми местами на позиции строя однородной цепи определяется в виде

Абсолютный объем строя текста это произведение абсолютных объемов всех строев j-ых однородных последовательностей в виде

,

,

где m - мощность алфавита (собственного словаря текста).

Средний геометрический интервал строя цепи на множестве всех однородных цепей текста определяется в виде

,

где n - длина текста, равная числу мест для размещения всех слов на его позиции.

Средний арифметический интервал строя j-ой однородной цепи определяется в виде

,

где Pj - частота вхождения или статистическая вероятность вхождения

j-го элемента в цепи.

Периодичность строя j-ой однородной цепи определяется в виде

Регулярность строя полной неоднородной цепи определяется отношением вида

,

где

Логарифмирование представленных величин дает набор удобных для практики компактных аддитивных информационных характеристик строя цепи. При этом интервал соответствует удаленности определенного j-го символа i-го вхождения относительно его -го вхождения в виде



Объем строя однородной последовательности выделенного j-го символа - глубине расположения строя j-ой однородной цепи в виде

,

Объем строя текста соответствует глубине расположения строя всей цепи в виде

,

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

а также - оценки средних удаленностей соседних одинаковых элементов в строе j-ой однородной цепи, которые отображают средние геометрические интервалы. Средняя удаленность выделенного j-го символа в строе однородной последовательности определяется в виде



Средняя удаленность отдельного символа в строе данной цепи или текста определяется в виде

Отношение средней удаленности выделенного j-го символа к средней удаленности отдельного символа в виде

дает характеристику строя, которая дополняет частоту вхождения и названа относительной удаленностью j-го символа.

Как отмечено в [3] для строя любой полной знаковой последовательности (без пустых мест на позиции) сумма произведений частот вхождения выделенных элементов на их относительные удаленности равна единице, так как

Множество величин {G_j} всех однородных последовательностей является распределением глубин однородных последовательностей для строя отдельной цепи и представляют, в некотором смысле, его «полное» описание. Множество величин {g_j} является распределением средних удаленностей однородных последовательностей. При анализе и описании строя данной цепи распределение средних удаленностей дополняет обычное частотное распределение знаков {n_j} комплексным распределением строя вида {<n_j, g_j >}.

Легко определяются аналогичные по форме, но отличные по содержанию, числовые характеристики строя данной цепи, с использованием векторов интервалов, представленных строками матрицы для разнородных цепей. В таком случае формулы определяются при выделении знаков j в i-ых разнородных цепях и представляют числовые характеристики строя на основе разнородных цепей, а также его «полное» описание с помощью аналогичных распределений.

1.3 Выводы

В данном разделе были описаны некоторые числовые характеристики строя цепи и их распределения, также были рассмотрены интервально-матричные модели строя цепи событий.

2. Анализ предметной области

2.1 Биоинформатика и генетика

В работе [1] представлен обзор и анализ основных подходов к исследованию нуклеотидных последовательностей и основных проблем биоинформатики. На момент написания данной работы, обзор, приведенный в [1], не утратил актуальность и отражает состояние проблемы в полном объеме. Полагаем уместным приведение, с указанием авторства, фрагментов данного обзора для описания состояния проблемы на данный момент.

Успех в теоретических исследованиях свойств символьных последовательностей самого разного направления фактически всегда был обусловлен возникновением соответствующих прикладных задач. Одной из таких задач, имеющих различные сферы приложения, является изучение тех свойств символьных последовательностей, которые могут оказаться информативными при исследованиях их функции.

В работе [1] отмечается, что «изучение статистических свойств биологических макромолекул началось задолго до появления соответствующих возможностей, предоставляемых современным уровнем развития вычислительной техники [14, 15]. С момента открытия структуры молекулы ДНК с исследованием статистических свойств связывались надежды на скорую «расшифровку» всех свойств, которые кодируются нуклеотидными последовательностями. Дальнейшее развитие молекулярной биологии и смежных дисциплин показало, что эти надежды реализованы не были, по крайней мере, не полностью.

С другой стороны, развитие прикладных исследований, в первую очередь в области биотехнологии, привело к тому, что статистический анализ биологических макромолекул (нуклеотидных и аминокислотных последовательностей) развился в специфическую область исследований, наиболее важными в которой с точки зрения нашей работы стали исследования, посвященные проблеме организации быстрого поиска аналогов и гомологов (подобия) для различных (как правило, коротких) последовательностей. Эта сфера исследований в последнее время оформилась в область со своими школами, течениями, направлениями, и получила в науке название биоинформатики [15-21].»

В работе [1] приведен обзор методов сравнения генетических текстов. «Одной из основных задач статистического анализа последовательностей биологических полимеров является выявление сходства (гомологии) различных генетических текстов или их фрагментов. Наличие такого сходства может служить признаком эволюционной близости геномов или функционального сходства рассматриваемых участков. Интерес к данной проблеме особенно усилился в связи с бурным ростом банков генетических текстов. Ключевым моментом в задаче выявления сходства является выбор мер близости между текстами. Этой тематике посвящено множество работ [15, 19-24].

Одним из традиционных методов сравнения текстов является представление текста точкой в многомерном пространстве, соответствующем какой-либо совокупности признаков. Расстояние между двумя точками характеризует степень близости текстов, отображаемых в эти точки. Вместо расстояния часто используют теоретико-множественные меры близости в виде отношения пересечения двух множеств к их объединению [25, 26]. Некоторые из указанных мер вычисляются очень просто, с линейной относительно длин сравниваемых текстов сложностью. В этом состоит их преимущество перед другими, более сложными методами сравнения текстов, достигаемое за счет потери некоторой информации о тексте. В [25] предлагается способ оценки близости символьных последовательностей, основанный на сравнении частот соответствующих l-грамм.

Другая, достаточно общая идея сравнения двух текстов состоит в переводе одного текста в другой с использованием заданного набора элементарных операций. Каждая операция имеет свою «стоимость». Оптимальному переводу соответствует последовательность элементарных операций с минимальной суммарной стоимостью. Она и характеризует степень различия двух текстов. Эта мера близости двух текстов получила название «редакционного расстояния». Определение расстояния между парой текстов минимальным числом операций, переводящих один текст в другой, впервые было предложено В.И. Левенштейном [27] в связи с изучением ошибок синхронизации в системах связи. Этот подход не получил особого развития в теории кодирования, но оказался очень плодотворным для анализа первичных структур молекул ДНК и белков. В генетических исследованиях идея оптимального перевода одной последовательности в другую впервые была высказана в связи с определением меры сходства аминокислотных последовательностей [28]. В дальнейшем такая техника была перенесена на поиск гомологии в первичных последовательностях ДНК [29]. Множество элементарных операций (преобразований) в основном определяется спецификой той области прикладных исследований, в которой используется метод редакционного расстояния. Во множестве элементарных операций можно выделить две базовые: устранение символа из текста и вставка символа в текст. Все остальные операции можно описать, ограничившись только базовыми. Однако сведение всех элементарных преобразований к базовым может завуалировать истинную картину в перестройке текстов и привести к тому, что тексты, близкие в пространстве специфических элементарных операций для данной предметной области, окажутся далекими в пространстве базовых элементарных операций. Поэтому для анализа генетических текстов удобно, кроме указанных базовых операций, выделять следующие типы элементарных преобразований: замену одного символа другим; перестановку соседних символов; вставку или устранение группы символов; повторение символов в обратном порядке (инверсия) перекодировку элементов текста в соответствии с заданным отображением алфавита самого на себя (комплиментарность). Замена указанных элементарных преобразований базовыми носила бы искусственный характер и приводила бы к дополнительным трудностям при сопоставлении «стоимостей», так как «стоимость» групповой операции, как правило, меньше суммы стоимостей заменяющих ее базовых операций [30].

Другой метод сравнения основан на поиске общих слов в сравниваемых словарях с учётом числа копий таких слов, встречающихся в сравниваемых последовательностях [24, 25]. Наконец, ещё один метод основан на вычислении относительной неопределённости обнаружения того или иного слова в некотором конкретном словаре, если совокупная частота встречаемости такого слова во всей группе сравниваемых последовательностей известна [31, 32].»

В данной работе используется несколько основных понятий генетики:

Нуклеотиды - фосфорные эфиры нуклеозидов, нуклеозидфосфаты, являются элементарными компонентами нуклеиновых кислот, таких как ДНК и РНК. Существует 5 типов нуклеотидов:

– A - аденин;

– G - гуанин;

– C - цитозин;

– T - тимин, не встречается в РНК, занимает место урацила в ДНК;

– U - урацил, не встречается в ДНК, занимает место тимина в РНК.

Кодон (кодирующий тринуклеотид, триплет) - единица генетического кода, тройка нуклеотидных остатков в ДНК или РНК, кодирующая включение одной аминокислоты.

Аминокислоты (аминокарбоновые кислоты) - органические соединения, в молекуле которых одновременно содержатся карбоксильные и аминные группы. Всего в ДНК существует 20 видов аминокислот, таким образом, одной аминокислоте может соответствовать несколько различных триплетов, так как возможных комбинаций трёх нуклеотидов в общей сложности 64.

Белки (протеины, полипептиды) - высокомолекулярные органические вещества, состоящие из соединённых в цепочку пептидной связью аминокислот.

При рассмотрении белков в биологии выделяется четыре уровня их структурной организации (рис. 4):

1. Первичная структура - последовательность аминокислот в цепи. Важными особенностями первичной структуры являются консервативные мотивы - сочетания аминокислот, важных для функции белка. Консервативные мотивы сохраняются в процессе эволюции видов, по ним можно предсказать функцию неизвестного белка.

2. Вторичная структура - локальное упорядочивание в пространстве фрагмента цепи, стабилизированное физико-химическими связями.

3. Третичная структура - пространственное строение цепи - взаимное расположение элементов вторичной структуры, стабилизированное физико-химическими связями.

4. Четверичная структура - имеется только у некоторых белков. Такие белки построены из нескольких цепей. Каждая цепь имеет свою первичную, вторичную, третичную структуру, называются протомером. Несколько протомеров соединяются вместе в одну молекулу. Один протомер не функционирует как белок, а только в соединении с другими протомерами.

В свойствах белков наибольшую роль играют вторичная, третичная и четверичная структура аминокислотной последовательности. Именно они обуславливают способность белка выполнять свои биологические функции. Процесс изменения биологических свойств белка под действием внешних реагентов называется денатурацией. При этом нарушается пространственная структура белка. Первичная структура не изменяется, изменяются биологические свойства белка, он перестает функционировать.



Рисунок 4 Различные уровни организации белка

Рассмотрим процесс формирования белка с точки зрения теории информации информирования М. Мазура [33-35], при этом нуклеотидная последовательность представляет собой информационную цепь оригиналов, а последовательность аминокислот представляет собой информационную цепь образов.

Поскольку процесс сворачивания белка напрямую зависит от взаимного расположения аминокислот в последовательности, которое в свою очередь обусловлено взаимным расположением нуклеотидов в цепи, кодирующей данную последовательность, полагаем, что основная информация содержится именно во взаимном расположении элементов.

2.2 Выравнивание аминокислотных и нуклеотидных последовательностей

Выравнивание аминокислотных или нуклеотидных последовательностей - это процесс сопоставления сравниваемых последовательностей для такого их взаиморасположения, при котором наблюдается максимальное количество совпадений аминокислотных остатков или нуклеотидов. Различают 2 вида выравнивания: парное (выравнивание двух последовательностей ДНК, РНК или белков) и множественное (выравнивание трех и более последовательностей).

2.3 Выводы

Изучение символьных последовательностей, в том числе их статистических и информационных характеристик является центральным местом во многих задачах биоинформатики, лингвистики, некоторых других областях знания. Биоинформатики, занимающиеся изучением различных свойств символьных последовательностей, отмечают особую важность взаимного расположения элементов последовательностях. При решении любых прикладных задач биоинформатики исследователь сталкивается с проблемой учета построения последовательности. Следует отметить, что, несмотря на признание биоинформатиками особой важности взаимного расположения нуклеотидов и триплетов в ДНК и РНК последовательностях исследования их взаимного расположения как такового не проводились.

3. Обоснование выбора средств разработки.

3.1 Разработка через тестирование

Разработка через тестирование (англ. test-driven development, TDD) - техника разработки программного обеспечения, которая основывается на повторении очень коротких циклов разработки: сначала пишется тест, покрывающий желаемое изменение, затем пишется код, который позволит пройти тест, и под конец проводится рефакторинг нового кода к соответствующим стандартам.

Тест - это процедура, которая позволяет либо подтвердить, либо опровергнуть работоспособность кода.

Этапы разработки в TDD:

– красный;

– зелёный;

– рефакторинг.

Разработка в стиле TDD состоит из коротких циклов (длительностью от 2 минут, в зависимости от опытности и стиля работы программиста). Каждый цикл состоит из следующих шагов:

1. Из репозитория извлекается программная система, находящаяся в согласованном состоянии, когда весь набор модульных тестов выполняется успешно.

2. Добавляется новый тест. Он может состоять в проверке, реализует ли система некоторое новое поведение или содержит ли некоторую ошибку, о которой недавно стало известно.

3. Успешно выполняется весь набор тестов, кроме нового теста, который выполняется неуспешно. Этот шаг необходим для проверки самого теста - включён ли он в общую систему тестирования и правильно ли отражает новое требование к системе, которому она, естественно, еще не удовлетворяет.

4. Программа изменяется с тем, чтобы как можно скорее выполнялись все тесты. Нужно добавить самое простое решение, удовлетворяющее новому тесту, и одновременно с этим не испортить существующие тесты. Большая часть нежелательных побочных и отдалённых эффектов от вносимых в программу изменений отслеживается именно на этом этапе, с помощью достаточно полного набора тестов.

5. Весь набор тестов выполняется успешно.

6. Теперь, когда требуемая в этом цикле функциональность достигнута самым простым способом, программа подвергается рефакторингу для улучшения структуры и устранения избыточного, дублированного кода.

7. Весь набор тестов выполняется успешно.

8. Комплект изменений, сделанных в этом цикле в тестах и программе, заносится в репозиторий (операция commit), после чего программа снова находится в согласованном состоянии и содержит четко осязаемое улучшение по сравнению с предыдущим состоянием.

Рисунок 5 Графическое представление цикла разработки

Кроме того разработка через тестирование подразумевает ряд особенностей, например, при обнаружении неверной работы какого-либо модуля, ошибочная ситуация (входные и выходные данные) должна быть реализована в виде теста, даже если эта ошибка исправляется на месте.

Так как тесты пишутся до кода, то они, по сути, определяют будущий интерфейс классов, методов и функций фиксируя связи внутри системы. Модульное тестирование позже позволяет программистам проводить рефакторинг, будучи уверенными, что модуль по-прежнему работает корректно (регрессионное тестирование). Это поощряет программистов к изменениям кода, поскольку достаточно легко проверить, что код работает и после изменений. Кроме того данная методика помогает устранить сомнения по поводу отдельных модулей и может быть использована для подхода к тестированию «снизу вверх»: сначала тестируются отдельные части программы, затем программа в целом. В дополнение ко всему модульные тесты можно рассматривать как «живой документ» для тестируемого класса. Клиенты, которые не знают, как использовать данный класс, могут использовать юнит-тест в качестве примера.

3.2 Прочие средства обеспечения надёжности ПО

Инспекция кода или ревизия кода (англ. Code review) - систематическая проверка исходного кода программы с целью обнаружения и исправления ошибок, которые остались незамеченными в начальной фазе разработки. В результате улучшается качество программного продукта и навыки разработчика.

В процессе инспекции кода могут быть найдены и устранены такие уязвимости, как ошибки в форматировании строк, состояние гонки, утечка памяти и переполнение буфера, что улучшает безопасность программного продукта. Системы контроля версий, основанные на Subversion, а также такие инструменты как Trac, Mercurial, GIT дают возможность проведения совместной инспекции кода. Кроме того, существуют инструменты, специально предназначенные для проведения совместной инспекции кода.

Программное обеспечение для автоматизированной инспекции кода упрощает задачу просмотра больших кусков кода, систематически сканируя его на предмет обнаружения наиболее известных уязвимостей.

Статический анализ кода (англ. static code analysis) - анализ программного обеспечения, производимый без реального выполнения исследуемых программ (анализ, производимый с выполнением программ, называется динамический анализ кода). В большинстве случаев анализ производится над какой-либо версией исходного кода. Термин обычно применяют к анализу, производимому специальным ПО, тогда как ручной анализ называют пониманием или постижением программы. В рамках данной бакалаврской работы для статического анализа кода использовалось дополнение к IDE Visual Studio - Resharper.

В зависимости от используемого инструмента глубина анализа может варьироваться от определения поведения отдельных операторов до анализа, включающего весь имеющийся исходный код. Способы использования полученной в ходе анализа информации также различны - от выявления мест, возможно содержащих ошибки, до формальных методов, позволяющих математически доказать какие-либо свойства программы (например, соответствие поведения спецификации).

Кроме того методами статического анализа возможет подсчёт программных метрик кода и осуществление обратной разработки. В последнее время статический анализ всё больше используется в верификации свойств ПО, используемого в компьютерных системах высокой надёжности.

3.3 Парадигма разработки

Парадигма программирования - это система идей и понятий, определяющих стиль написания компьютерных программ. Парадигма, в первую очередь, определяется базовой программной единицей и самим принципом достижения модульности программы. Парадигма программирования определяет то, в каких терминах программист описывает логику программы. Важно отметить, что парадигма программирования не определяется однозначно языком программирования - многие современные языки программирования являются мультипарадигмальными, то есть допускают использование различных парадигм. К примеру, язык Си, который не является объектно-ориентированным, можно работать в соответствии с принципами объектно-ориентированного программирования, хотя это и сопряжено с определёнными сложностями; функциональное программирование можно применять при работе на любом императивном языке, в котором имеются функции (для этого достаточно не применять присваивание).

При объектно-ориентированном подходе программа представляет собой описание объектов, их свойств (или атрибутов), совокупностей (или классов), отношений между ними, способов их взаимодействия и операций над объектами (или методов). Несомненным преимуществом данного подхода является концептуальная близость к предметной области произвольной структуры и назначения. Механизм наследования атрибутов и методов позволяет строить производные понятия на основе базовых и таким образом создавать модель сколь угодно сложной предметной области с заданными свойствами. Объекты, классы и методы могут быть полиморфными, что делает реализованное программное обеспечение более гибким и универсальным.

Понятие класса является фундаментальным в ООП и служит основой для создания объектов. В описании класса определяются данные (т.е. переменные) и код (т.е. методы), манипулирующий этими данными.

Объекты являются экземплярами класса. Методы и переменные, составляющие класс, называются членами класса.

Наследование - свойство производного объекта сохранять поведение родительского объекта. Под поведением будем иметь в виду для математического объекта его атрибуты и операции над ним, а для языкового объекта ООП - поля и методы. Заметим, что дочерний объект не обязательно наследует все без исключения атрибуты и операции родительского, а лишь некоторые из них.

Агрегация - отношение «часть-целое» между двумя равноправными объектами, когда один объект (контейнер) имеет ссылку на другой объект. Оба объекта могут существовать независимо: если контейнер будет уничтожен, то его содержимое - нет.

Композиция - отношение «часть-целое» между двумя равноправными объектами, когда один объект (контейнер) имеет ссылку на другой объект. Оба объекта могут существовать независимо: если контейнер будет уничтожен, то его содержимое - нет.

Метод - функция или процедура внутри класса. Как и процедура в процедурном программировании, метод состоит из некоторого количества операторов для выполнения какого-то действия, имеет набор входных аргументов и возвращаемое значение. Различают простые методы и статические методы (методы класса). Простые методы имеют доступ к данным объекта (конкретного экземпляра данного класса), а статические методы не имеют доступа к данным объекта и для их использования не нужно создавать экземпляры (данного класса). Методы предоставляют интерфейс, при помощи которого осуществляется доступ к данным объекта некоторого класса, тем самым, обеспечивая инкапсуляцию данных.

Поле (атрибут) - параметр объекта, задающий его состояние. Т.е. переменная, хранимая в данном объекте. Иначе говоря это данные, хранимые объектом. Один объект может быть полем другого объекта.

Концепция инкапсуляции призвана обеспечивать безопасность проектирования и реализации программного обеспечения на основе локализации манипулирования объектом в областях его полей и методов. Иначе говоря, инкапсуляция - это сокрытие реализации. При этом пользователю предоставляется только спецификация (интерфейс) объекта.

Полиморфизм - возможность оперирования объектами без однозначной идентификации их типов. Концепция полиморфизма предполагает в части реализации отложенное связывание переменных со значениями. При этом во время выполнения программы происходят так называемые «ленивые» или «замороженные» вычисления. Таким образом, означивание языковых идентификаторов выполняется по мере необходимости.

Прототип - это объект-образец, по образу и подобию которого создаются другие объекты. Объекты-копии могут сохранять связь с родительским объектом, автоматически наследуя изменения в прототипе, эта особенность определяется в рамках конкретного языка.

Свойства объекта - псевдополя, доступные для чтения и / или записи. Свойства внешне выглядят как поля и используются аналогично доступным полям (с некоторыми исключениями), однако фактически при обращении к ним происходит вызов методов доступа. Таким образом, свойства можно рассматривать как «умные» поля данных, сопровождающие доступ к внутренним данным объекта какими-либо дополнительными действиями (например, когда изменение координаты объекта сопровождается его перерисовкой на новом месте). Конкретная языковая реализация свойств может быть разной. Например, в C# объявление свойства непосредственно содержит код методов доступа, который вызывается только при работе со свойствами, то есть не требует отдельных методов доступа, доступных для непосредственного вызова. В Delphi объявление свойства содержит лишь имена методов доступа, которые должны вызываться при обращении к полю. Сами методы доступа представляют собой обычные методы с некоторыми дополнительными требованиями к сигнатуре.

3.4 Диаграмма классов

Центральное место в объектно-ориентированном программировании занимает разработка логической модели системы в виде диаграммы классов. Диаграмма классов (class diagram) служит для представления статической структуры модели системы в терминологии классов объектно-ориентированного программирования. Диаграмма классов может отражать, в частности, различные взаимосвязи между отдельными сущностями предметной области, такими как объекты и подсистемы, а также описывать их внутреннюю структуру и типы отношений.

Диаграмма классов представляет собой граф, вершинами которого являются элементы типа «классификатор», связанные различными типами структурных отношений. Диаграмма классов может также содержать интерфейсы, пакеты, отношения и даже отдельные экземпляры, такие как объекты и связи.

3.5 Программные средства разработки

В соответствии с выбранной парадигмой и методами обеспечения надёжности программного обеспечения определим используемые программные средства разработки.

В качестве языка программирования для данной работы был выбран объектно-ориентированный язык C#, что было обусловлено наличием большого количества дополнительных программных средств для данного языка, а также его соответствие всем требованиям по разработке.

Из дополнительных средств в процессе выполнения работы были использованы следующие:

1. Visual Studio 2012 - среда разработки (IDE) для языка C# под операционную систему Windows. Данный продукт позволяет разрабатывать как консольные приложения, так и приложения с графическим интерфейсом, в том числе с поддержкой технологии WindowsForms, а также веб-сайты, веб-приложения, веб-службы как в родном, так и управляемом кодах для всех платформ. Visual Studio включает в себя редактор исходного кода и возможностью поддержкой простого рефакторинга кода. Среда разработки позволяет создавать и подключать сторонние приложения (плагины) для расширения функциональности, включая добавления поддержки систем контроля версий исходного кода (как например, Subversion и Git).

2. ReSharper (R#) - программный пакет, дополнение к среде разработки, производит анализ и модификацию исходного кода с целью обеспечения следующих функций:

– автозаполнение;

– поиск;

– подсветка синтаксиса;

– форматирование исходного кода;

– автоматизированный рефакторинг;

– статический анализ кода;

– Value Analysis - анализ, выявляющий избыточные проверки, присваивания и логические операторы, ветки кода, недостижимые ни при каких входных данных, показывающий предупреждения о возможных исключениях при вызове методов и операторов;

– подсказка при вводе кода - улучшенный вариант IntelliSense, учитывающий контекст (например, ожидаемый тип выражения);

– упрощение тестирования.

3. NUnit - программный пакет, позволяющий производить модульное тестирование приложений, основанных на технологии. Net.

4. GitHub - система учёта и контроля версий, являющаяся расширением оболочки операционной системы. Основан на системе контроля версий Git. Кроме размещения кода, участники могут общаться, комментировать правки друг друга, следить за новостями знакомых. С помощью широких возможностей Git программисты могут объединить свои репозитории и GitHub предлагает удобной интерфейс для этого и может отобразить вклад каждого участника в виде дерева.

5. Libiada - библиотека для анализа строя знаковых последовательностей. Использование языка C# и системы контроля версий позволило интегрировать один из компонентов разрабатываемого комплекса в данную библиотеку, обеспечив взаимодействие с ней посредством веб-сервисов.

6. IIS (Internet Information Services, до версии 5.1 - Internet Information Server) - проприетарный набор серверов для нескольких служб Интернета от компании Майкрософт. Основным компонентом IIS является веб-сервер, который позволяет размещать в Интернете сайты.

7. Git - распределённая система управления версиями файлов. Поддерживает быстрое разделение и слияние версий, включает инструменты для визуализации и навигации по нелинейной истории разработки. Предоставляет каждому разработчику локальную копию всей истории разработки, изменения копируются из одного репозитория в другой. Удалённый доступ к репозиториям Git обеспечивается git-daemon, SSH- или HTTP-сервером.

8. Redmine - открытое серверное веб-приложение для управления проектами и задачи (в том числе для отслеживания ошибок). Позволяет отслеживать ошибки (багтрекер), учёт временных затрат для выполнения задачи, оповещения об изменениях с помощью RSS-потоков и электронной почты.

3.6 Вывод

Были выбраны парадигма и средства разработки для написания программного комплекса.

4. Проектирование структуры программного комплекса

Была проведена разработка программного комплекса, описание алгоритмов функционирования, структура и интерфейс которого приведены далее. Ниже представлены алгоритмы работы, диаграмма классов и их описание.

4.1 Алгоритм работы

На рисунке 6 представлена схема алгоритма работы серверной части программного комплекса. Работа данного алгоритма приводится ниже в инструкции пользователя.

Рисунок 6 Общая схема работы

Подробнее вышеуказанный алгоритм описан в инструкции пользователя.

Рисунок 7 Ввод данных

Подробнее вышеуказанный алгоритм описан в инструкции пользователя.



Рисунок 8 Извлечение цепочки

Для извлечение цепочки из базы данных используется модель данных которая автоматически формирует и скрываем в себе все SQL-запросы. В первую очередь извлекается объект исследования. Далее по его идентификатору и выбранной пользователем формы записи извлекается сам строй цепочки и прочие её параметры. Затем цепочка перекодируется в представление библиотеки LibiadaCore для дальнейших вычислений.

Рисунок 9 Выбор разбивающей процедуры

В зависимости от выбранных параметром выполняется разбиение знаковой цепочки. Выполняется разбиение символьной последовательности на подпоследовательности: блоками, L-граммами, L-граммами с фиксированной привязкой к началу цепочки.

Рисунок 10 Подсчёт локальных характеристик

Для каждого из фрагментов цепочек формируется калькулятор, вычисляющий ту или иную характеристику, результаты сохраняются в двумерном массиве.



Рисунок 11 Алгоритм разбиения знаковой последовательности

В первую очередь происходит получение числа элементов (массивы начала и конца фрагментов). Затем происходит извлечение фрагмента в зависимости от выбранного способа разбиения. Далее происходит сохранение извлечённого фрагмента в массив фрагментов цепочки.

Рисунок 12 Вычисление разницы между характеристиками

Для всех вычисленных значений характеристик кроме первой вычисляется разница между текущим значением и предыдущим. Результаты сохраняются в тот же массив.

Рисунок 13 Вычисление спектра по Фурье

Вычисление спектра состоит из трёх этапов:

1. Преобразование всех значений характеристик в комплексный вид.

2. Вычисление спектра.

3. Преобразование вещественный тип.



Рисунок 14 Вывод результата

Подробнее вышеуказанный алгоритм описан в инструкции пользователя.

4.2 Диаграмма классов программного комплекса

На данном рисунке представлена структура программного комплекса. Представлена диаграмма классов, для разбиения знаковых последовательностей на блоки, L - граммы.



Рисунок 15 Диаграмма классов программного комплекса

4.3 Описание классов

Рисунок 16 Диаграмма класса FromFixStartCutRule

Данный класс разбивает знаковую последовательность по правилу фиксированного начала. Класс имеет два метода FromFixStartCutRule (конструктор) и getIterator. Метод FromFixStartCutRule принимает два параметра (длину цепочки и шаг разбиения) и выполняет разбиение цепочки. Метод getIterator возвращает значение начала и конца разбиения.

Рисунок 17 Диаграмма класса SimpleCutRule

Данный класс разбивает знаковую последовательность на блоки равной длины. Класс имеет два метода SimpleCutRule (констуктор) и getIterator. Метод SimpleCutRule принимает два параметра (длину цепочки и шаг разбиения) и выполняет разбиение цепочки. Метод getIterator возвращает значение начала и конца разбиения.