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. 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,^[1] 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ů:

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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

LCS_{(SEQ₁,SEQ₂)} = CGTTCGGCTATGCTTCTACTTATTCTA

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

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = 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):

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

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

SEQ₂ = -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 Rⁿ obsahuje konvergentní vybranou posloupnost (Bolzanova–Weierstrassova věta).
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

↑ V matematické informatice se často používá textový řetězec jako synonymum pro posloupnost. Je však důležité si všimnout, že podřetězec a vybraná posloupnost nejsou synonyma. Podřetězce jsou po sobě jdoucí složky řetězce, zatímco vybrané posloupnosti nemusí obsahovat jen po sobě jdoucí prvky. To znamená, že podřetězec řetězce je vždy vybranou posloupností řetězce, ale vybraná posloupnost řetězce nemusí být podřetězcem řetězce, viz: GUSFIELD, Dan, 1999. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8. S. 4.

Reference

V tomto článku byl použit překlad textu z článku Subsequence na anglické Wikipedii. 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

[substrVsSubseq-1] V matematické informatice se často používá textový řetězec jako synonymum pro posloupnost. Je však důležité si všimnout, že podřetězec a vybraná posloupnost nejsou synonyma. Podřetězce jsou po sobě jdoucí složky řetězce, zatímco vybrané posloupnosti nemusí obsahovat jen po sobě jdoucí prvky. To znamená, že podřetězec řetězce je vždy vybranou posloupností řetězce, ale vybraná posloupnost řetězce nemusí být podřetězcem řetězce, viz: GUSFIELD, Dan, 1999. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8. S. 4.

[1]