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 ${\displaystyle \langle A,B,D\rangle }$ je vybranou posloupností z ${\displaystyle \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 ${\displaystyle \langle B,C,D\rangle }$ z ${\displaystyle \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

${\displaystyle X=\langle A,C,B,D,E,G,C,E,D,B,G\rangle }$ a

${\displaystyle Y=\langle B,E,G,J,C,F,E,K,B\rangle }$ a

${\displaystyle Z=\langle B,E,E\rangle .}$

pak ${\displaystyle 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 ${\displaystyle \langle B,E,E,B\rangle }$ má délku 4. Nejdelší společná vybraná posloupnost z X a Y je ${\displaystyle \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_(SEQ1,SEQ2) = 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

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

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