Subsecuencia

Relación binaria matemática

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

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

La lista de todas las subsecuencias de la palabra " manzana " 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 ).

Subsecuencia común

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

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

Aplicaciones

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

Tomemos dos secuencias de ADN que contengan 37 elementos, digamos:

SEQ ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

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

LCS _{(SEC 1 ,SEC 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, posicionar 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 (aquí, un guión) para rellenar las subsecuencias vacías que surjan:

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 qué tan similares son las dos cadenas de ADN, utilizando las bases de ADN: adenina , guanina , citosina y timina .

Teoremas

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

Véase también

• Límite subsiguiente  : El límite de alguna subsecuencia
• Límite superior y límite inferior  – Límites de una secuenciaPages displaying short descriptions of redirect targets
• Problema de la subsecuencia creciente más larga  – Problema de informáticaPages displaying short descriptions of redirect targets

Notas

1. En informática, cadena se utiliza a menudo como sinónimo de secuencia , pero es importante tener en cuenta que subcadena y subsecuencia no son sinónimos. Las subcadenas son partes consecutivas de una cadena, mientras que las subsecuencias no necesariamente lo son. Esto significa que una subcadena de una cadena es siempre una subsecuencia de la cadena, pero una subsecuencia de una cadena no siempre es una subcadena de la cadena, véase: Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology . EE. UU.: Cambridge University Press. pág. 4. ISBN 0-521-58519-8.

Este artículo incorpora material de la subsecuencia en PlanetMath , que está licenciado bajo la Licencia Creative Commons Atribución/Compartir-Igual .