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

Математическое бинарное отношение

В математике подпоследовательность данной последовательности — это последовательность, которая может быть получена из данной последовательности путем удаления некоторых элементов или их отсутствия без изменения порядка остальных элементов. Например, последовательность является подпоследовательностью, полученной после удаления элементов , а отношение одной последовательности как подпоследовательности другой является предварительным порядком . ${\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 ,}$

Список всех подпоследовательностей слова « appl » будет выглядеть так: « a », « ap », « al », « ae », « app », « apl », « ape », « ale », « appl », « appe ", " aple ", " apple ", " p ", " pp ", " pl ", " pe " , " ppl ", " ppe ", " ple ", " pple ", " l ", " le " , " e ", "" ( пустая строка ).

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

Учитывая две последовательности , последовательность называется общей подпоследовательностью , а if является подпоследовательностью обеих и. Например, если ${\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 .}$

Приложения

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

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

ПОСЛЕДОВАТЕЛЬНОСТЬ ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

ПОСЛЕДОВАТЕЛЬНОСТЬ ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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

LCS _{(SEQ 1 , SEQ 2 )} = CGTTCGGCTATGCTTCTACTTATTCTA

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

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

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

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

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

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

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

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

Теоремы

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

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

• Последующий предел  - предел некоторой подпоследовательности.
• Ограничить верхний и нижний предел  – границы последовательностиPages displaying short descriptions of redirect targets
• Проблема самой длинной возрастающей подпоследовательности  - Задача информатикиPages displaying short descriptions of redirect targets

Примечания

1. В информатике строка часто используется как синоним последовательности , но важно отметить, что подстрока и подпоследовательность не являются синонимами. Подстроки — это последовательные части строки, а подпоследовательности — не обязательно. Это означает, что подстрока строки всегда является подпоследовательностью строки, но подпоследовательность строки не всегда является подстрокой строки, см.: Gusfield, Dan (1999) [1997]. Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . США: Издательство Кембриджского университета. п. 4. ISBN 0-521-58519-8.

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