Subsucesión
# Subsucesión

En matemáticas, una subsucesión es una sucesión que puede derivarse de otra eliminando algunos elementos sin cambiar el orden de los elementos restantes. Por ejemplo, la sucesión $\langle A,B,D\rangle$ es una subsucesión de $\langle A,B,C,D,E,F\rangle$ obtenida tras eliminar los elementos $C$, $E$, y $F$. La relación de ser una sucesión subsucesión de otra es un preorden.

No se debe confundir la subsucesión con la subcadena $\langle A,B,C,D\rangle$, que se puede obtener de la cadena $\langle A,B,C,D,E,F\rangle$ eliminando la subcadena $\langle E,F\rangle$. El concepto de subcadena es un refinamiento del concepto de subsecuencia.

## Subsucesión común

Dadas dos sucesiones X e Y, se dice que una sucesión Z es una subsucesión común de X e Y, si Z es una subsucesión tanto de X como de Y. Por ejemplo, si

    $X=\langle A,C,B,D,E,G,C,E,D,B,G\rangle$ e
    $Y=\langle B,E,G,C,F,E,U,B,K\rangle$

una subsucesión común de X e Y puede ser

    $Z=\langle B,E,E\rangle .$

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

## Aplicaciones

Las subsucesiones tienen aplicaciones en ciencias de la computación, especialmente en la disciplina de la bioinformática, donde se usan computadoras para comparar, analizar y almacenar secuencias de ADN, ARN y proteínas.

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

    $SEQ_1$ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
    $SEQ_2$ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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

    $LCS_{(SEQ1,SEQ2)}$ = CGTTCGGCTATGCTTCTACTTATTCTA

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

    $SEQ_1$ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
    $SEQ_2$ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Otra forma es alinear las dos secuencias, esto es, colocar los elementos de la subsecuencia común más larga en la misma columna (indicada por una barra vertical) e introducir un carácter especial (en este caso, un guion) en una secuencia cuando dos elementos en la misma columna difieren:

    $SEQ_1$ = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-
    $SEQ_2$ = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA

Las subsecuencias se utilizan para determinar cómo de similares son las dos cadenas de ADN, usando las bases del ADN: adenina, guanina, citosina y timina.

## Teoremas

* Toda sucesión infinita de números reales tiene una subsucesión monótona infinita (lema utilizado en la demostración del teorema de Bolzano-Weierstrass).
* Toda sucesión infinita acotada en $R^n$ tiene una subsucesión convergente (teorema de Bolzano-Weierstrass).
* Para todo par de enteros r y s, toda sucesión finita de longitud al menos (r − 1)(s − 1) + 1 contiene una subsucesión monótonamente creciente de longitud r o una subsucesión monótonamente decreciente de longitud s (teorema de Erdős–Szekeres).
