Подпоследовательность - Subsequence

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Ноябрь 2018) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Подпоследовательность»  – Новости  · газеты  · книги  · ученый  · JSTOR (Ноябрь 2018) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

В математика, а подпоследовательность это последовательность который может быть получен из другой последовательности путем удаления некоторых элементов или отсутствия элементов без изменения порядка остальных элементов. Например, последовательность ${ displaystyle langle A, B, D rangle}$ является подпоследовательностью ${ displaystyle langle A, B, C, D, E, F rangle}$ получается после удаления элементов ${ displaystyle C}$, ${ displaystyle E}$, и ${ displaystyle F}$. Отношение одной последовательности, являющейся подпоследовательностью другой, является Предварительный заказ.

Подпоследовательности могут содержать последовательные элементы, которые не были последовательными в исходной последовательности. Подпоследовательность, состоящая из последовательного выполнения элементов исходной последовательности, например ${ displaystyle langle B, C, D rangle}$ из ${ displaystyle langle A, B, C, D, E, F rangle}$, это подстрока. Подстрока - это уточнение подпоследовательности.

Список всех подпоследовательностей для слова "яблоко" было бы "а", "ap", "аль", "ае", "приложение", "apl", "обезьяна", "эль", "приложение", "Appe", "апл", "яблоко", "п", "pp", "pl", "pe", "человек", "ppe", "Ple", "pple", "л", "ле", "е", "".

Общая подпоследовательность

Учитывая две последовательности Икс и Y, последовательность Z считается общая подпоследовательность из Икс и Y, если Z является подпоследовательностью обоих Икс и Y. Например, если

${ Displaystyle X = langle A, C, B, D, E, G, C, E, D, B, G rangle}$ и

${ Displaystyle Y = langle B, E, G, C, F, E, U, B, K rangle}$ и

${ displaystyle Z = langle B, E, E rangle.}$

тогда ${ displaystyle Z}$ называется общей подпоследовательностью Икс и Y.

Это бы нет быть самая длинная общая подпоследовательность, поскольку Z имеет длину только 3, а общая подпоследовательность ${ displaystyle langle B, E, E, B rangle}$ имеет длину 4. Самая длинная общая подпоследовательность Икс и Y является ${ displaystyle langle B, E, G, C, E, B rangle}$.

Приложения

Подпоследовательности имеют приложения к Информатика,^[1] особенно в дисциплине биоинформатика, где компьютеры используются для сравнения, анализа и хранения ДНК, РНК, и белок последовательности.

Возьмем две последовательности ДНК, содержащие 37 элементов, скажем:

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Самая длинная общая подпоследовательность последовательностей 1 и 2:

LCS_{(SEQ1, SEQ2)} = CGTTCGGCTATGCTTCTACTTATTCTA

Это можно проиллюстрировать, выделив 27 элементов самой длинной общей подпоследовательности в начальных последовательностях:

SEQ₁ = АCGграммТграммTCGТGCTATGCTGAТграммCTграммACTTATАТграммCTA

SEQ₂ = CGTTCGGCTATCграммTACграммTTCTATTCTАТграммATTТCTAА

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

SEQ₁ = ACGGTGTCGTGCTAT-G - C-TGATGCTGA - CT-T-ATATG-CTA-

        | || ||| ||||| |  | |  | || |  || | || |  |||

SEQ₂ = -C-GT-TCG-GCTATCGTACGT - T-CT-ATTCTATGAT-T-TCTAA

Подпоследовательности используются для определения сходства двух цепей ДНК с использованием оснований ДНК: аденин, гуанин, цитозин и тимин.

Теоремы

• Каждая бесконечная последовательность действительные числа имеет бесконечный монотонный подпоследовательность (это лемма, используемая в доказательство теоремы Больцано – Вейерштрасса ).
• Каждый бесконечный ограниченная последовательность в р^п имеет сходящийся подпоследовательность (Это Теорема Больцано – Вейерштрасса ).
• Для всех целые числа р и s, любая конечная последовательность длины не меньше (р − 1)(s - 1) + 1 содержит монотонно возрастающую подпоследовательность длиныр или же монотонно убывающая подпоследовательность длиныs (Это Теорема Эрдеша – Секереса ).

Смотрите также

• Последующий лимит - предел некоторой подпоследовательности.
• Ограничьте высшее и ограничьте низшее
• Задача самой длинной возрастающей подпоследовательности

Примечания

Эта статья включает материалы из подпоследовательности на PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.