Subsucesión

En matemàtiques, una subsucesión és una successió que pot derivar-se d'una atra eliminant alguns elements sense canviar l'orde dels elements restants. Per eixemple, la successió $⟨ A, B, D ⟩$ és una subsucesión de $⟨ A, B, C, D, E, F ⟩$ obtinguda despuix d'eliminar els elements $C$ , $E$ , i $F$ . La relació de ser una successió subsucesión d'una atra és un preorden.

No es deu confondre la subsucesión en la subcadena $⟨ A, B, C, D ⟩$ , que es pot obtindre de la cadena $⟨ A, B, C, D, E, F ⟩$ eliminant la subcadena $⟨ E, F ⟩$ . El concepte de subcadena és un refinament del concepte de subsecuencia.

Subsucesión comú

Donades dos successions X i I, es diu que una successió Z és una subsucesión comuna de X i I, si Z és una subsucesión tant de X com de I. Per eixemple, si

X = ⟨ A, C, B, D, E, G, C, E, D, B, G ⟩

i

Y = ⟨ B, E, G, C, F, E, U, B, K ⟩

una subsucesión comuna de X i I pot ser

Z = ⟨ B, E, E ⟩ .

Esta no seria la subsucesión comuna més llarga, ya que Z té solament llongitut 3, i la subsucesión comuna $⟨ B, E, E, B ⟩$ té llongitut 4. La subsucesión comuna més llarga de X i I és $⟨ B, E, G, C, E, B ⟩$ .

Aplicacions

Les subsucesiones tenen aplicacions en ciències de la computació,^[1] especialment en la disciplina de la bioinformática, a on s'usen computadores per a comparar, analisar i almagasenar seqüències d'ADN, ARN i proteïnes.

Prenent dos seqüències de ADN que continguen 37 elements, per eixemple:

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

La subsecuencia comuna més llarga de les seqüències 1 i 2 és:

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

Açò es pot ilustrar resaltant els 27 elements de la subsecuencia comuna més llarga en les seqüències inicials:

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Una atra forma és alinear les dos seqüències, açò és, colocar els elements de la subsecuencia comuna més llarga en la mateixa columna (indicada per una barra vertical) i introduir un caràcter especial (en este cas, un guion) en una seqüència quan dos elements en la mateixa columna diferixen:

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

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

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

Les subsecuencias s'utilisen per a determinar cóm de similars són les dos cadenes de ADN, usant les bases de el ADN: adenina, guanina, citosina i timina.

Vore també

Referències

↑ En ciències de la computació, se sol utilisar cadena com a sinònim de successió, pero és important notar que subcadena i subsucesión no són sinònims. Les subcadena són parts consecutives d'una cadena, mentres que les subsucesiones no tenen per qué. Açò significa que una subcadena d'una certa cadena és sempre una subsucesión de la cadena, pero el recíproc no sempre es complix. Açò ve tractat en (1999) Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, USA: Cambridge University Press, pp. 4. ISBN 0-521-58519-8.

Plantilla:PlanetMath attribution

Referències

Este artícul conté una traducció derivada de «Subsucesión» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[substrVsSubseq-1] En ciències de la computació, se sol utilisar cadena com a sinònim de successió, pero és important notar que subcadena i subsucesión no són sinònims. Les subcadena són parts consecutives d'una cadena, mentres que les subsucesiones no tenen per qué. Açò significa que una subcadena d'una certa cadena és sempre una subsucesión de la cadena, pero el recíproc no sempre es complix. Açò ve tractat en (1999) Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, USA: Cambridge University Press, pp. 4. ISBN 0-521-58519-8.

[1]