En matemáticas , una subsecuencia es una secuencia que se puede derivar de otra secuencia eliminando algunos o ningún elemento sin cambiar el orden de los elementos restantes. Por ejemplo, la secuencia es una subsecuencia de obtenido después de la eliminación de elementos , , y . La relación de una secuencia con la subsecuencia de otra es un preorden .
Las subsecuencias pueden contener elementos consecutivos que no fueron consecutivos en la secuencia original. Una subsecuencia que consiste en una serie consecutiva de elementos de la secuencia original, como de , es una subcadena . La subcadena es un refinamiento de la subsecuencia.
La lista de todas las subsecuencias de 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 ).
Subsecuencia común
Dadas dos secuencias X y Y , una secuencia Z se dice que es una subsecuencia común de X y Y , si Z es una subsecuencia de ambos X y Y . Por ejemplo, si
- y
- y
luego se dice que es una subsecuencia común de X y Y .
Esta no sería la subsecuencia común más larga , ya que Z solo tiene una longitud de 3 y la subsecuencia comúntiene longitud 4. La subsecuencia común más larga de X e Y es.
Aplicaciones
Las subsecuencias tienen aplicaciones en la informática , [1] especialmente en la disciplina de la bioinformática , donde las computadoras se utilizan para comparar, analizar y almacenar secuencias de ADN , ARN y proteínas .
Tome dos secuencias de ADN que contengan 37 elementos, digamos:
- SEC 1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
- SEC 2 = 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 1 = A CG G T G TCG T GCTATGCT GA T G CT G ACTTAT A T G CTA
- SEC 2 = 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 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 el vacío surgido. subsecuencias:
- SEQ 1 = ACGGTGTCGTGCTAT-G - C-TGATGCTGA - CT-T-ATATG-CTA-
- | || ||| ||||| | | | | || | || | || | |||
- SEC 2 = -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
- Cada 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 ).
- Cada secuencia infinita acotada en R n tiene una subsecuencia convergente (este es el teorema de Bolzano-Weierstrass ).
- Para todos los enteros r y s , cada secuencia finita de longitud al menos ( r - 1) ( s - 1) + 1 contiene una subsecuencia monótonamente creciente de la longitud de r o una disminución de subsecuencia monotónicamente de longitud s (Este es el Erdős-Szekeres teorema ).
Ver también
- Límite posterior : el límite de alguna subsecuencia.
- Límite superior y límite inferior
- Problema de subsecuencia creciente más largo
Notas
- ^ 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 sonpartes consecutivas de una cadena, mientras que las subsecuencias no necesitan serlo. 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, ver: Gusfield, Dan (1999) [1997]. Algoritmos sobre cadenas, árboles y secuencias: informática y biología computacional . Estados Unidos: Cambridge University Press. pag. 4. ISBN 0-521-58519-8.
Este artículo incorpora material de la subsecuencia en PlanetMath , que tiene la licencia Creative Commons Attribution / Share-Alike License .