Математическое бинарное отношение
В математике подпоследовательность данной последовательности — это последовательность, которая может быть получена из данной последовательности путем удаления некоторых элементов или их отсутствия без изменения порядка остальных элементов. Например, последовательность является подпоследовательностью, полученной после удаления элементов , а отношение одной последовательности как подпоследовательности другой является предварительным порядком .![{\displaystyle \langle A,B,D\rangle}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle \ langle A, B, C, D, E, F \ rangle}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle E,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Ф.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Подпоследовательности могут содержать последовательные элементы, которые не были последовательными в исходной последовательности. Подпоследовательность, состоящая из последовательных элементов исходной последовательности, например from , является подстрокой . Подстрока является уточнением подпоследовательности.![{\displaystyle \langle B,C,D\rangle,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle \ langle A, B, C, D, E, F \ rangle,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Список всех подпоследовательностей слова « 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}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X=\langle A,C,B,D,E,G,C,E,D,B,G\rangle \qquad {\text{and}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y=\langle B,E,G,J,C,F,E,K,B\rangle \qquad {\text{и}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Z=\langle B,E,E\rangle.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Это не будет самая длинная общая подпоследовательность , поскольку ее длина равна только 3, а общая подпоследовательность имеет длину 4. Самая длинная общая подпоследовательность и равна![{\displaystyle Z}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ displaystyle \ langle B, E, E, B \ rangle}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle Y}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \langle B,E,G,C,E,B\rangle.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Приложения
Подпоследовательности находят применение в информатике [1] , особенно в области биоинформатики , где компьютеры используются для сравнения, анализа и хранения последовательностей ДНК , РНК и белков .
Возьмем две последовательности ДНК, содержащие 37 элементов, скажем:
- ПОСЛЕДОВАТЕЛЬНОСТЬ 1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
- ПОСЛЕДОВАТЕЛЬНОСТЬ 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} ^{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Для всех целых чисел и каждая конечная последовательность длины содержит по крайней мере монотонно возрастающую подпоследовательность длины или монотонно убывающую подпоследовательность длины (это теорема Эрдеша – Секереша ).
![{\displaystyle г}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle с,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle (r-1)(s-1)+1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle s}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Метрическое пространство компактно, если каждая последовательность в имеет сходящуюся подпоследовательность, предел которой находится в .
![{\displaystyle (X,d)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Смотрите также
Примечания
- ^ В информатике строка часто используется как синоним последовательности , но важно отметить, что подстрока и подпоследовательность не являются синонимами. Подстроки — это последовательные части строки, а подпоследовательности — не обязательно. Это означает, что подстрока строки всегда является подпоследовательностью строки, но подпоследовательность строки не всегда является подстрокой строки, см.: Gusfield, Dan (1999) [1997]. Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . США: Издательство Кембриджского университета. п. 4. ISBN 0-521-58519-8.
В эту статью включены материалы из подпоследовательности PlanetMath , которая распространяется под лицензией Creative Commons Attribution/Share-Alike License .