Сортировка массива праймеров с использованием 2-3 дерева

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

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

Поэтому было решено провести сортировку этих строк с удалением всех повторяющихся элементов. Для сортировки был выбран метод, предполагающий использование 2-3 дерева (рис. 2.5.).

Рисунок 2.5. Пример организации 2-3 дерева.

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

Метод построения сбалансированных деревьев был открыт 1962 Георгием Адельсон-Вельским и Евгением Ландисом [1] Их метод требует всего лишь двух дополнительных битов на узел, по сравнению с обычным деревом, и никогда не использует более O(log N) операций для поиска по дереву или вставки элемента. Предложенный подход также дает общую технологию представления линейных списков длиной N таким образом, что любая из следующих операций может быть выполнена за время O(log N):

1. поиск элемента по заданному ключу;

2. поиск k-го элемента по заданному k;

3. вставка элемента в определенное место;

4. удаление определенного элемента.

При последовательном расположении элементов линейных списков операции ( 1 ) и ( 2 ) выполняются очень эффективно, в то время как операции ( 3 ) и ( 4 ) требуют порядка N шагов. С другой стороны, при использовании связанных элементов эффективно будут выполняться операции ( 3 ) и ( 4 ), а операции ( 1 ) и ( 2 ) потребуют порядка N шагов. Представление линейных списков в виде дерева позволяет выполнить все четыре операции за O(log N) шагов. При этом можно более или менее эффективно выполнять и другие операции, например сцепление списка из М элементов со списком из N элементов за O(log( M+N )) шагов.

Однако сбалансированные деревья хороши лишь при наличии большого количества элементов. Например, если есть эффективный метод, который требует log N единиц времени, и неэффективный, которому необходимо 2 N единиц, то при N < 256 следует использовать неэффективный метод, который при этом становится более эффективным. С другой стороны, при очень больших N хранение данных во внутренней памяти становится невозможным, а при использовании внешних файлов с прямым доступом более эффективны другие методы. Впрочем, объема оперативной памяти у современных машин достаточно для обработки используемого нами количества данных.

Используемое нами 2-3 дерево обладает следующими свойствами:

· все данные хранятся в листьях, в вершинах хранится вспомогательная информация, необходимая для организации поиска по поддеревьям;

· сыновья упорядочены по значению максимума поддерева сына;

· нелистовые вершины содержат один или два ключа, указывающие на диапазон значений в их поддеревьях;

· если нелистовая вершина имеет двух сыновей, то вершина хранит минимум правого поддерева; если трех, то первый ключ равен минимуму среднего поддерева, а второй ключ равен минимуму правого поддерева;

· сбалансированность, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных;

· высота равна O(log N), где N - количество элементов в дереве.

Для поиска в таком 2-3 дереве необходимо последовательно просматривать ключи, хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого элемента сравнивается с первым ключом ячейки и, если искомый ключ меньше, то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым ключом в ячейке (если второго ключа нет — поддерева всего два, то сразу переходим во второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход в среднее поддерево, а если превосходит, то идем в правое поддерево.

Вставка элемента в 2-3 дерево может происходить двумя путями:

· чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу;

· если же в узле уже содержатся два ключа, делим его на два «одноключевых» узла и вставляем средний ключ в родительский узел. Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.

При удалении элемента из узла возникают три варианта:

· если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется;

· если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно;

· если у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом, получая два узла с двумя ключами.

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