Saltar al contenido principal

# 3.3: Alineación global vs. alineación local vs. alineación semi-global

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

Una alineación global se define como la alineación de extremo a extremo de dos cadenas s y t.
Una alineación local de cadenas s y t es una alineación de subcadenas de s con subcadenas de t.
En general se utilizan para encontrar regiones de alta similitud local. A menudo, estamos más interesados en encontrar locales

alineaciones porque normalmente no conocemos los límites de los genes y sólo se puede conservar un pequeño dominio del gen. En tales casos, no queremos hacer cumplir que otras partes (potencialmente no homólogas) de la secuencia también se alineen. El alineamiento local también es útil cuando se busca un gen pequeño en un cromosoma grande o para detectar cuándo una secuencia larga puede haber sido reordenada (Figura 4).

Una alineación semi-global de cadena s y t es una alineación de una subcadena de s con una subcadena de t.

Esta forma de alineación es útil para la detección de solapamientos cuando no deseamos penalizar las brechas iniciales o finales. Para encontrar una alineación semi-global, las distinciones importantes son inicializar la fila superior y la columna más a la izquierda a cero y terminar el extremo en la fila inferior o la columna más a la derecha.

El algoritmo es el siguiente:

\ [
\ begin {array} {l}
\ text {Inicialización}:\ begin {aligned}
F (i, 0) =0\\
F (0, j) =0
\ text {iteración}: & F (i, j) =\ max\ left\ {\ begin {alineado}
F (i-1, j) -d\\
F (i, j-1) -d &\\
F (i-1, j-1) +s\ izquierda (x_ {i}, y_ {j}\ derecha)
\ end {array}
\]

$\text{Termination : Bottom row or Right column} \nonumber$

## Uso de la programación dinámica para alineaciones locales

En esta sección veremos cómo encontrar alineaciones locales con una modificación menor del algoritmo de Needleman-Wunsch que se discutió en el capítulo anterior para encontrar alineaciones globales.

Para encontrar alineaciones globales, se utilizó el siguiente algoritmo de programación dinámica (algoritmo Needleman-Wunsch):

$\text {Initialization : F(0,0)=0} \nonumber$

\begin{aligned} \text { Iteration } &: F(i, j)=\max \left\{\begin{aligned} F(i-1, j)-d \\ F(i, j-1)-d \\ F(i-1, j-1)+s\left(x_{i}, y_{j}\right) \end{aligned}\right.\end{aligned}

$\text{Termination : Bottom right} \nonumber$

Para encontrar alineaciones locales solo necesitamos modificar ligeramente el algoritmo de Needleman-Wunsch para comenzar de nuevo y encontrar una nueva alineación local siempre que la puntuación de alineación existente sea negativa. Dado que una alineación local puede comenzar en cualquier lugar, inicializamos la primera fila y columna de la matriz a ceros. El paso de iteración se modifica para incluir un cero para incluir la posibilidad de que iniciar una nueva alineación sea más económico que tener muchos desajustes. Además, dado que la alineación puede terminar en cualquier lugar, necesitamos atravesar toda la matriz para encontrar la puntuación de alineación óptima (no solo en la esquina inferior derecha). El resto del algoritmo, incluido el rastreo, permanece sin cambios, con rastreo indicando un final en cero, indicando el inicio de la alineación óptima.

Estos cambios dan como resultado el siguiente algoritmo de programación dinámica para la alineación local, que también se conoce como:

\ [\ begin {array} {ll}
\ text {Inicialización}: & F (i, 0) =0\\
& F (0, j) =0
\ end {array}\ nonumber\]

\ [\ text {Iteración}:\ quad F (i, j) =\ max\ izquierda\ {\ begin {array} {c}
0\\
F (i-1, j) -d\\
F (i, j-1) -d\\
F (i-1, j-1) +s\ left (x_ {i}, y_ {j}\ right)
\ end {array}\ derecha. \ nonumber\]

$Termination : Anywhere \nonumber$

## Variaciones algorítmicas

A veces puede resultar costoso tanto en tiempo como en espacio ejecutar estos algoritmos de alineación. Por lo tanto, en esta sección se presentan algunas variaciones algorítmicas para ahorrar tiempo y espacio que funcionan bien en la práctica.

Un método para ahorrar tiempo, es la idea de delimitar el espacio de alineaciones a explorar. La idea es que las buenas alineaciones generalmente se mantengan cerca de la diagonal de la matriz. Así podemos simplemente explorar celdas de matriz dentro de un radio de k desde la diagonal. El problema con esta modificación es que se trata de una heurística y puede conducir a una solución subóptima ya que no incluye los casos límite mencionados al inicio del capítulo. Sin embargo, esto funciona muy bien en la práctica. Además, dependiendo de las propiedades de la matriz de puntuación, puede ser posible argumentar la corrección del algoritmo de espacio rebotado. Este algoritmo requiere$$O(k ∗ m)$$ espacio y$$O(k ∗ m)$$ tiempo.

Anteriormente vimos que para calcular la solución óptima, necesitábamos almacenar la puntuación de alineación en cada celda así como el puntero reflejando la elección óptima que conduce a cada celda. Sin embargo, si solo nos interesa la puntuación óptima de alineación, y no la alineación real en sí, existe un método para calcular la solución mientras se ahorra espacio. Para calcular la puntuación de cualquier celda solo necesitamos las puntuaciones de la celda anterior, a la izquierda, y a la diagonal izquierda de la celda actual. Al guardar la columna anterior y actual en la que estamos calculando puntuaciones, la solución óptima se puede calcular en el espacio lineal.

Si utilizamos el principio de dividir y conquistar, en realidad podemos encontrar la alineación óptima con el espacio lineal. La idea es que calculemos las alineaciones óptimas desde ambos lados de la matriz, es decir, de izquierda a derecha, y viceversa. Vamos$$u=\left\lfloor\frac{n}{2}\right\rfloor$$. Digamos que podemos identificar v tal que la célula$$(u, v)$$ está en el óptimo

trayectoria de alineación. Eso significa que v es la fila donde la alineación cruza la columna u de la matriz. Podemos encontrar la alineación óptima concatenando las alineaciones óptimas de (0,0) a (u, v) más la de (u, v) a (m, n), donde m y n es la celda inferior derecha (nota: las puntuaciones de alineación de las subalineaciones concatenadas usando nuestro esquema de puntuación son aditivas. Así que hemos aislado nuestro problema a dos problemas separados en las esquinas superior izquierda e inferior derecha de la matriz DP. Entonces podemos seguir dividiendo recursivamente estos subproblemas en subproblemas más pequeños, hasta que estemos abajo a alinear secuencias de longitud 0 o nuestro problema sea lo suficientemente pequeño como para aplicar el algoritmo DP regular. Para encontrar v la fila en la columna central donde se cruza la alineación óptima simplemente agregamos las puntuaciones entrantes y salientes para esa columna.

Un inconveniente de este enfoque de dividir y conquistar es que tiene un tiempo de ejecución más largo. Sin embargo, el tiempo de ejecución no se incrementa drásticamente. Dado que v se puede encontrar usando una pasada de DP regular, podemos encontrar v para cada columna en$$O(mn)$$ tiempo y espacio lineal ya que no necesitamos realizar un seguimiento de los punteros de rastreo para este paso. Luego al aplicar el enfoque dividir y conquistar, los subproblemas tardan la mitad del tiempo ya que solo necesitamos hacer un seguimiento de las celdas diagonalmente a lo largo de la trayectoria de alineación óptima (la mitad de la matriz del paso anterior) Eso da un tiempo de ejecución total de$$O\left(m n\left(1+\frac{1}{2}+\frac{1}{4}+\ldots\right)\right)=O(2 M N)=O(m n)$$ (usando la suma de series geométricas), para darnos un tiempo de ejecución cuadrática (dos veces más lento que antes, pero sigue siendo el mismo comportamiento asintótico). El tiempo total nunca superará$$2MN$$ (el doble del tiempo que el algoritmo anterior). Aunque el tiempo de ejecución se incrementa en un factor constante, una de las grandes ventajas del enfoque de dividir y conquistar es que el espacio se reduce drásticamente a$$O(N)$$.

P: ¿Por qué no usar la variación de espacio rebotado sobre la variación de espacio lineal para obtener tanto el tiempo lineal como el espacio lineal?

R: La variación del espacio rebotado es un enfoque heurístico que puede funcionar bien en la práctica pero no garantiza la alineación óptima.

Las penalizaciones por brecha determinan la puntuación calculada para una subsecuencia y así afectan qué alineación se selecciona. El modelo normal es usar a donde cada hueco individual en una secuencia de huecos de longitud k se penaliza por igual con valor p. Esta penalización puede modelarse como$$w(k) = k ∗ p$$. Dependiendo de la situación, podría ser una buena idea penalizar de manera diferente por, digamos, brechas de diferentes longitudes. Un ejemplo de esto es un en el que la penalización incremental disminuye cuadráticamente a medida que crece el tamaño de la brecha. Esto se puede modelar como$$w(k) = p+q∗k+r∗k2$$. Sin embargo, la compensación es que también hay costos asociados con el uso de funciones de penalización de brecha más complejas al aumentar sustancialmente el tiempo de ejecución. Este costo puede mitigarse usando aproximaciones más simples a las funciones de penalización por brecha. El es un intermedio fino: se tiene una penalización fija para iniciar una brecha y un costo lineal para agregar a una brecha; esto se puede modelar como$$w(k) = p + q ∗ k$$.

También se pueden considerar funciones más complejas que tomen en consideración las propiedades de las secuencias codificadoras de proteínas. En el caso del alineamiento de regiones codificadoras de proteínas, un hueco de longitud mod 3 puede ser menos penalizado porque no resultaría en un desplazamiento de marco.

This page titled 3.3: Alineación global vs. alineación local vs. alineación semi-global is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Manolis Kellis et al. (MIT OpenCourseWare) via source content that was edited to the style and standards of the LibreTexts platform.