В математике , А подпоследовательность представляет собой последовательность , которая может быть получена из другой последовательности , путем удаления некоторых или без элементов без изменения порядка остальных элементов. Например, последовательность является подпоследовательностью получается после удаления элементов , , а также . Отношение одной последовательности к подпоследовательности другой является предварительным порядком .
Подпоследовательности могут содержать последовательные элементы, которые не были последовательными в исходной последовательности. Подпоследовательность, состоящая из последовательного выполнения элементов исходной последовательности, например из , это подстрока . Подстрока - это уточнение подпоследовательности.
Список всех подпоследовательностей для слова « яблоко » будет « a », « ap », « al », « ae », « app », « apl », « ape », « ale », « app », « Appe », " АЕЕ ", " яблоко ", " р ", " р ", " пли ", " ре ", " PPL ", " PPE ", " PLE ", " pple ", " л ", " ль " , « е », «» ( пустая строка ).
Общая подпоследовательность
Указанные две последовательности Х и Y , последовательность Z называется быть общей подпоследовательности из X и Y , если Z представляет собой подпоследовательность как X и Y . Например, если
- а также
- а также
тогда Говорят, что общая подпоследовательность X и Y .
Это не будет самой длинной общей подпоследовательностью , поскольку Z имеет длину только 3, а общая подпоследовательностьимеет длину 4. Самая длинная общая подпоследовательность X и Y - это.
Приложения
Подпоследовательности имеют приложение к информатике , [1] , особенно в дисциплине биоинформатики , где компьютеры используются для сравнения, анализа и хранения ДНК , РНК и белков последовательностей.
Возьмем две последовательности ДНК, содержащие 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
Подпоследовательности используются для определения сходства двух цепей ДНК с использованием оснований ДНК: аденина , гуанина , цитозина и тимина .
Теоремы
- Каждая бесконечная последовательность действительных чисел имеет бесконечную монотонную подпоследовательность (эта лемма используется при доказательстве теоремы Больцано – Вейерштрасса ).
- Каждая бесконечная ограниченная последовательность в R n имеет сходящуюся подпоследовательность (это теорема Больцано – Вейерштрасса ).
- Для всех целых чисел r и s каждая конечная последовательность длины не меньше ( r - 1) ( s - 1) + 1 содержит монотонно возрастающую подпоследовательность длины r или монотонно убывающую подпоследовательность длины s (это теорема Эрдеша – Секереша ).
Смотрите также
- Предел подпоследовательности - предел некоторой подпоследовательности.
- Ограничьте высшее и ограничьте низшее
- Задача самой длинной возрастающей подпоследовательности
Заметки
- ^ В информатике строка часто используется как синоним последовательности , но важно отметить, что подстрока и подпоследовательность не являются синонимами. Подстроки - это последовательные части строки, в то время как подпоследовательности могут быть не такими. Это означает, что подстрока строки всегда является подпоследовательностью строки, но подпоследовательность строки не всегда является подстрокой строки, см .: Gusfield, Dan (1999) [1997]. Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология . США: Издательство Кембриджского университета. п. 4. ISBN 0-521-58519-8.
Эта статья включает материалы из подпоследовательности PlanetMath , которая находится под лицензией Creative Commons Attribution / Share-Alike License .