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

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

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

Список всех подпоследовательностей для слова « яблоко » будет « a », « ap », « al », « ae », « app », « apl », « ape », « ale », « app », « Appe », " АЕЕ ", " яблоко ", " р ", " р ", " пли ", " ре ", " PPL ", " PPE ", " PLE ", " pple ", " л ", " ль ", « е », «» ( пустая строка ).

• 1 Общая подпоследовательность
• 2 Приложения
• 3 теоремы
• 4 См. Также
• 5 Примечания

Принимая во внимание две последовательности и последовательность называется быть общей подпоследовательности из, и, если это подпоследовательностью как и, например, если ${\ displaystyle X}$${\ displaystyle Y,}$${\ displaystyle Z}$${\ displaystyle X}$${\ displaystyle Y,}$${\ displaystyle Z}$${\ displaystyle X}$${\ displaystyle Y.}$

$${\ displaystyle X = \ langle A, C, B, D, E, G, C, E, D, B, G \ rangle \ qquad {\ text {and}}}$$ $${\ displaystyle Y = \ langle B, E, G, J, C, F, E, K, B \ rangle \ qquad {\ text {and}}}$$ $${\ displaystyle Z = \ langle B, E, E \ rangle.}$$ то называется общей подпоследовательностью и${\ displaystyle Z}$${\ displaystyle X}$${\ displaystyle Y.}$

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

Подпоследовательности применяются в информатике, особенно в области биоинформатики, где компьютеры используются для сравнения, анализа и хранения последовательностей ДНК, РНК и белков.

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

SEQ 1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ 2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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

LCS (SEQ 1, SEQ 2) = CGTTCGGCTATGCTTCTACTTATTCTA

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

SEQ 1 = A CG G T G TCG T GCTATGCT GA T G CT G ACTTAT A T G CTA

SEQ 2 = CGTTCGGCTAT C G TA C G TTCTA TT CT A T G ATT T CTA A

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

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

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

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

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

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

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

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