Subsekvence - Subsequence

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto problémech na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Listopadu 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Subsekvence"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Listopadu 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, a subsekvence je sekvence které lze odvodit z jiné sekvence odstraněním některých nebo žádných prvků bez změny pořadí zbývajících prvků. Například sekvence ${ displaystyle langle A, B, D rangle}$ je subsekvence ${ displaystyle langle A, B, C, D, E, F rangle}$ získané po odstranění prvků ${ displaystyle C}$, ${ displaystyle E}$, a ${ displaystyle F}$. Vztah jedné sekvence, která je subsekvencí jiné, je a předobjednávka.

Sekvence mohou obsahovat po sobě jdoucí prvky, které nebyly po sobě následující v původní sekvenci. Subsekvence, která se skládá z následného běhu prvků z původní sekvence, jako je ${ displaystyle langle B, C, D rangle}$ z ${ displaystyle langle A, B, C, D, E, F rangle}$, je podřetězec. Podřetězec je upřesnění subsekvence.

Seznam všech subsekvencí pro slovo „jablko" bylo by "A", "ap", "al", "ae", "aplikace", "apl", "opice", "ale", "appl", "appe", "aple", "jablko", "p", "str", "pl", "pe", "ppl", "ppe", "ple", "pple", "l", "le", "E", "".

Společná posloupnost

Vzhledem ke dvěma sekvencím X a Yposloupnost Z se říká, že je společná posloupnost z X a Y, pokud Z je subsekvence obou X a Y. Například pokud

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

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

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

pak ${ displaystyle Z}$ se říká, že je běžnou posloupností X a Y.

To by bylo ne být nejdelší společná posloupnost, od té doby Z má pouze délku 3 a společnou posloupnost ${ displaystyle langle B, E, E, B rangle}$ má délku 4. Nejdelší společná posloupnost X a Y je ${ displaystyle langle B, E, G, C, E, B rangle}$.

Aplikace

Následnosti mají aplikace na počítačová věda,^[1] zejména v disciplíně bioinformatika, kde se počítače používají k porovnání, analýze a ukládání DNA, RNA, a protein sekvence.

Vezměte dvě sekvence DNA obsahující 37 prvků, řekněme:

SEKV₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEKV₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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

LCS_{(SEKV1, SEKV2)} = CGTTCGGCTATGCTTCTACTTATTCTA

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

SEKV₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEKV₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Další způsob, jak to ukázat, je sladit dvě sekvence, tj., umístit prvky nejdelší společné posloupnosti do stejného sloupce (označené svislou čarou) a zavést speciální znak (zde pomlčku) v jedné sekvenci, když se dva prvky ve stejném sloupci liší:

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

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

SEKV₂ = -C-GT-TCG-GCTATCGTACGT - T-CT-ATTCTATGAT-T-TCTAA

Sekvence se používají k určení toho, jak jsou si oba řetězce DNA podobné, za použití bází DNA: adenin, guanin, cytosin a tymin.

Věty

• Každá nekonečná sekvence reálná čísla má nekonečno monotónní subsekvence (Toto je lemma použité v důkaz věty Bolzano – Weierstrass ).
• Každý nekonečný ohraničená sekvence v Rⁿ má konvergentní subsekvence (Toto je Bolzano – Weierstrassova věta ).
• Pro všechny celá čísla r a s, každá konečná posloupnost délky alespoň (r − 1)(s - 1) + 1 obsahuje monotónně rostoucí posloupnost délkyr nebo monotónně klesající subsekvence délkys (To je Erdős – Szekeresova věta ).

Viz také

• Následný limit - limit nějaké subsekvence.
• Limit superior a limit inferior
• Nejdelší problém s rostoucí posloupností

Poznámky

Tento článek včlení materiál od subsekvence dne PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.