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

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

Подпоследовательности могут содержать последовательные элементы, которые не были последовательными в исходной последовательности. Подпоследовательность, состоящая из последовательного набора элементов исходной последовательности, например $\langle B,C,D\rangle ,$ от $\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 ", "" ( пустая строка ).

Общая последовательность [ править ]

Даны две последовательности $X$ и $Y,$ последовательность $Z$ называется общей подпоследовательностью $X$ и $Y,$ если $Z$ является подпоследовательностью обоих $X$ и $Y.$ Например, если

X=\langle A,C,B,D,E,G,C,E,D,B,G\rangle \qquad {\text{ and}}

Y=\langle B,E,G,J,C,F,E,K,B\rangle \qquad {\text{ and}}

Z=\langle B,E,E\rangle .

затем

Z

называется общей подпоследовательностью

X

и

Y.

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

Приложения [ править ]

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

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

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

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

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

LCS _{(SEQ ₁ , SEQ ₂ )} = 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

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

Теоремы [ править ]

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

См. также [ править ]

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

Примечания [ править ]

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

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

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

[1]