title: Subsucesión
text: # 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).
  