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 je vybranou posloupností z která byla získána odstraněním prvků , , a . 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 z , 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

a
a

pak 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 má délku 4. Nejdelší společná vybraná posloupnost z X a Y je .

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ů:

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

Odkazy

Poznámky

  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. 

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