Subsecuencia

En matemáticas , una subsecuencia de una secuencia dada es una secuencia que se puede derivar de la secuencia dada eliminando algunos o ningún elemento sin cambiar el orden de los elementos restantes. Por ejemplo, la secuencia${\displaystyle \langle A,B,D\rangle }$es una subsecuencia de${\displaystyle \langle A,B,C,D,E,F\rangle }$obtenido después de la eliminación de elementos${\displaystyle C,}$${\displaystyle E,}$y${\displaystyle F.}$La relación de que una secuencia sea subsecuencia de otra es un orden parcial .

Las subsecuencias pueden contener elementos consecutivos que no eran consecutivos en la secuencia original. Una subsecuencia que consiste en una sucesión consecutiva de elementos de la secuencia original, como${\displaystyle \langle B,C,D\rangle,}$de${\displaystyle \langle A,B,C,D,E,F\rangle,}$es una subcadena . La subcadena es un refinamiento de la subsecuencia.

La lista de todas las subsecuencias para la palabra " apple " sería " a ", " ap ", " al ", " ae ", " app ", " apl ", " ape ", " ale ", " appl ", " appe ", " aple ", " apple ", " p ", " pp ", " pl ", " pe ", " ppl ", " ppe ", " ple ", " pple ", " l ", " le ", " e ", "" ( cadena vacía ).

Dadas dos secuencias${\displaystyle X}$y${\displaystyle Y,}$una secuencia${\displaystyle Z}$Se dice que es una subsecuencia común de${\displaystyle X}$y${\displaystyle Y,}$si${\displaystyle Z}$es una subsecuencia de ambos${\displaystyle X}$y${\displaystyle Y.}$ Por ejemplo, si $${\displaystyle X=\langle A,C,B,D,E,G,C,E,D,B,G\rangle \qquad {\text{ y}}}$$$${\displaystyle Y=\langle B,E,G,J,C,F,E,K,B\rangle \qquad {\text{ y}}}$$$${\displaystyle Z=\langle B,E,E\rangle.}$$ entonces${\displaystyle Z}$Se dice que es una subsecuencia común de${\displaystyle X}$y${\displaystyle Y.}$

Esta no sería la subsecuencia común más larga , ya que${\displaystyle Z}$solo tiene longitud 3 y la subsecuencia común${\displaystyle \langle B,E,E,B\rangle }$tiene longitud  4. La subsecuencia común más larga de${\displaystyle X}$y${\displaystyle Y}$es${\displaystyle \langle B,E,G,C,E,B\rangle.}$

Las subsecuencias tienen aplicaciones en la informática , ^{[ 1 ]} especialmente en la disciplina de la bioinformática , donde se utilizan ordenadores para comparar, analizar y almacenar secuencias de ADN , ARN y proteínas .

Tomemos dos secuencias de ADN que contengan 37 elementos, por ejemplo:

SEQ ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

La subsecuencia común más larga de las secuencias 1 y 2 es:

LCS _{(SEQ 1 ,SEQ 2 )} = CGTTCGGCTATGCTTCTACTTATTCTA

Esto se puede ilustrar resaltando los 27 elementos de la subsecuencia común más larga en las secuencias iniciales:

SEQ ₁ = A CG G T G TCG T GCTATGCT GA T G CT G ACTTAT A T G CTA

SEQ ₂ = CGTTCGGCTAT C G TA C G TTCTA TT CT A T G ATT T CTA A

Otra forma de mostrar esto es alinear las dos secuencias, es decir, colocar los elementos de la subsecuencia común más larga en una misma columna (indicada por la barra vertical) e introducir un carácter especial (en este caso, un guion) para rellenar las subsecuencias vacías resultantes:

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

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

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

Las subsecuencias se utilizan para determinar el grado de similitud entre las dos hebras de ADN, utilizando las bases del ADN: adenina , guanina , citosina y timina .

• Toda sucesión infinita de números reales tiene una subsucesión monótona infinita . (Este es un lema utilizado en la demostración del teorema de Bolzano-Weierstrass ).
• Cada secuencia infinita acotada en${\displaystyle \mathbb {R} ^{n}}$tiene una subsucesión convergente . (Este es el teorema de Bolzano-Weierstrass ).
• Para todos los números enteros${\displaystyle r}$y${\displaystyle s,}$toda secuencia finita de longitud al menos${\displaystyle (r-1)(s-1)+1}$contiene una subsecuencia monótonamente creciente de longitud ${\displaystyle r}$o una subsecuencia monótonamente decreciente de longitud ${\displaystyle s}$. (Este es el teorema de Erdős-Szekeres ).
• Un espacio métrico${\displaystyle (X,d)}$es compacto si cada secuencia en${\displaystyle X}$tiene una subsecuencia convergente cuyo límite está en${\displaystyle X}$.

• Límite subsiguiente
• Limitar lo superior y limitar lo inferior
• Subsecuencia creciente más larga
• Subsecuencia alternante más larga
• Subsecuencia común más larga

Este artículo incorpora material de una publicación posterior en PlanetMath , que está bajo la licencia Creative Commons Attribution/Share-Alike License .