Vybraná posloupnost

Vybraná posloupnost je v matematice posloupnost, kterou lze odvodit z jiné posloupnosti vypuštěním některých prvků bez změny pořadí zbývajících prvků. Například posloupnost \langle A,B,D \rangle je vybranou posloupností z \langle A,B,C,D,E,F \rangle, která byla získána odstraněním prvků C, E, a F. Relace mezi vybranou posloupností a původní posloupností je kvaziuspořádání.

Vybrané posloupnosti mohou obsahovat po sobě jdoucí prvky, které v původní posloupnosti po sobě nešly. Vybranou posloupnost, která sestává z takových prvků původní posloupnosti, které šly po sobě, jako například \langle B,C,D \rangle z \langle A,B,C,D,E,F \rangle , nazýváme podřetězec. +more Podřetězec je speciálním případem vybrané posloupnosti.

Všechny vybrané posloupnosti ze slova „apple“ jsou „a“, „ap“, „al“, „ae“, „app“, „apl“, „ape“, „ale“, „appl“, „appe“, „aple“, „apple“, „p“, „pp“, „pl“, „pe“, „ppl“, „ppe“, „ple“, „pple“, „l“, „le“, „e“, „“ (prázdný řetězec).

Společná vybraná posloupnost

Jsou-li dány dvě posloupnosti X a Y, pak se posloupnost Z nazývá společná vybraná posloupnost z X a Y, pokud Z je vybranou posloupností z X i Y. Pokud například

: X = \langle A,C,B,D,E,G,C,E,D,B,G \rangle a

: Y = \langle B,E,G,J,C,F,E,K,B \rangle a

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

pak Z se nazývá společná vybraná posloupnost z X a Y.

Nejde o nejdelší společnou podposloupnost, protože Z má délku pouze 3, a společná vybraná posloupnost \langle B,E,E,B \rangle má délku 4. Nejdelší společná vybraná posloupnost z X a Y je \langle B,E,G,C,E,B \rangle .

Aplikace

Vybrané posloupnosti se využívají v matematické informatice, zvláště v oboru bioinformatiky, kde se používají počítače pro porovnávání, analýzu, a uchovávání sekvencí DNA, RNA, a bílkovin.

Uvažujme následující dvě posloupnosti DNA obsahující 37 prvků:

:SEQ1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA :SEQ2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Nejdelší společná vybraná posloupnost posloupností 1 a 2 je:

:LCS(SEQ1,SEQ2) = CGTTCGGCTATGCTTCTACTTATTCTA

To lze ilustrovat zvýrazněním 27 prvků nejdelší společné vybrané posloupnosti do počáteční posloupnosti:

:SEQ1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA :SEQ2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Jiným způsobem znázornění je zarovnání prvků nejdelší společné vybrané posloupnosti nad sebou (indikováno svislítkem; vzniklé mezery vyplněny spojovníky): :SEQ1 = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA- : | || ||| ||||| | | | | || | || | || | ||| :SEQ2 = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA

Vybrané posloupnosti se používají pro určení, jak podobná jsou dvě vlákna DNA co do posloupnosti DNA bází (A - adenin, G - guanin, C - cytosin, T - thymin).

Věty

Každá nekonečná posloupnost reálných čísel obsahuje nekonečnou monotónní vybranou posloupnost (Toto lemma se používá v důkazu Bolzanovy-Weierstrassovy věta). * Každá nekonečná omezená funkce v Rn obsahuje konvergentní vybranou posloupnost (Bolzanova-Weierstrassova věta). +more * Pro všechna celá čísla r a s obsahuje každá konečná posloupnost délky alespoň (r − 1)(s − 1) + 1 monotonně rostoucí vybranou posloupnost délky r nebo monotonně klesající vybranou posloupnost délky s (Erdősova-Szekeresova věta).

Odkazy

Poznámky

Reference

Tento článek obsahuje materiál ze stránky Subsequence na PlanetMath, jejíž licence umožňuje dále šířit publikované texty.

Související články

Limita vybrané posloupnosti * Limes superior a limes inferior * Problém nejdelší rostoucí podposloupnosti

Kategorie:Elementární matematika Kategorie:Matematické posloupnosti a řady