Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2017-11-16 | 225 |
5.00
из
|
Заказать работу |
|
|
Сформированный нами массив строк по заданному префиксу может быть избыточным, то есть содержать одинаковые строки. При этом вероятность появления одинаковых строк обратно пропорциональна их длине и зависит от специфики генома изучаемого образца. Повторяющиеся строки могут иметь случайное расположение в массиве.
Результаты виртуальной ПЦР для таких строк будут одинаковыми. Таким образом их значительное содержание в массиве лишь увеличит нагрузку на программу нахождения теоретических ПЦР-фрагментов по найденным праймерам, не давая при этом ни каких результатов.
Поэтому было решено провести сортировку этих строк с удалением всех повторяющихся элементов. Для сортировки был выбран метод, предполагающий использование 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 дерево может происходить двумя путями:
· чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу;
· если же в узле уже содержатся два ключа, делим его на два «одноключевых» узла и вставляем средний ключ в родительский узел. Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
При удалении элемента из узла возникают три варианта:
· если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется;
· если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно;
· если у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом, получая два узла с двумя ключами.
В нашем алгоритме строки последовательно добавляются в дерево, при этом дерево постоянно реконфигурируется, чтобы сохранить сбалансированность. Для каждого нового элемента делается проверка, не записан ли такой же элемент в дерево. Если подобный элемент в дереве уже существует, то добавление не происходит. После добавления всех возможных элементов, происходит обход всех веток от «меньшего» элемента к «большему» и запись этих строк в массив.
|
|
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!