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 ${\displaystyle \langle A,B,D\rangle }$ es una subsucesión de ${\displaystyle \langle A,B,C,D,E,F\rangle }$ obtenida tras eliminar los elementos ${\displaystyle C}$, ${\displaystyle E}$, y ${\displaystyle 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 ${\displaystyle \langle A,B,C,D\rangle }$, que se puede obtener de la cadena ${\displaystyle \langle A,B,C,D,E,F\rangle }$ eliminando la subcadena ${\displaystyle \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

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

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

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

${\displaystyle 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 ${\displaystyle \langle B,E,E,B\rangle }$ tiene longitud 4. La subsucesión común más larga de X e Y es ${\displaystyle \langle B,E,G,C,E,B\rangle }$.

Aplicaciones

Las subsucesiones tienen aplicaciones en ciencias de la computación,^[1] 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₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = 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₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = 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₁ = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-

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

SEQ₂ = -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ⁿ 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).

Véase también

• Límite superior y límite inferior
• Problema de la subsecuencia más larga

Referencias

1. En ciencias de la computación, se suele utilizar cadena como sinónimo de sucesión, pero es importante notar que subcadena y subsucesión no son sinónimos. Las subcadenas son partes consecutivas de una cadena, mientras que las subsucesiones no tienen por qué. Esto significa que una subcadena de una cierta cadena es siempre una subsucesión de la cadena, pero el recíproco no siempre se cumple. Esto viene tratado en Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. 1999. p. 4. ISBN 0-521-58519-8.

Este artículo incorpora material de subsequence en PlanetMath, que tiene licencia Creative Commons Atribución Compartir-Igual.

• Datos: Q1332977