La secuenciación de ADN de Sanger produce una traza de cromatograma que se puede visualizar con varios programas, incluidos FinchTV o ChromasLite. Los datos brutos consisten en coordenadas para cada una de las cuatro bases de ADN (A, C, G y T). Sin embargo, los gráficos se muestran como picos suavizados, como se muestra en la imagen anteriormente. Muchos programas permiten que los ejes x e y de la gráfica se escalen más o menos para cambiar la forma de la gráfica. ¿Qué método matemático se utiliza para trazar curvas suaves como estas a partir de un (pequeño) número de puntos de datos sin procesar?
image-processing
discrete-signals
interpolation
SabreWolfy
fuente
fuente
Respuestas:
Implementación
Suponiendo que ya tiene una rutina de dibujo lineal, solo necesita complementarla con algún tipo de interpolación. Las curvas se crean dibujando suficientes líneas cortas interpoladas para que el resultado se vea suave. Un buen punto de partida sería utilizar una rutina de interpolación existente, como las que da Paul Bourke aquí .
Ilustraré esto usando las rutinas cúbicas que proporciona, ya que esas son algunas de las más simples que aún darán resultados razonables. Aquí está el primero (traducido a python) como referencia:
Cada rutina tiene un parámetro
mu
que representa la parte fraccionaria del índice que desea interpolar. Dependiendo de la rutina, los otros parámetros serán cierto número de muestras que rodean el índice en cuestión. En el caso cúbico, necesitará cuatro muestras. Por ejemplo, si los datos esy[n]
, y desea que el valor en10.3
,mu
sería.3
, y que le pasa eny[9]
,y[10]
,y[11]
, yy[12]
.Luego, en lugar de dibujar una sola línea con puntos finales, digamos,( 10 ,y10) → ( 11 ,y11) , dibujaría un montón de valores más cortos utilizando los valores interpolados (p. ej. ( 10 ,y10) → ( 10.1 , cúbico ( .1 ,y9 9,y10,y11,y12) ) ... ) Obviamente esos puntos tendrían que ser escalados aX y y dimensiones de la imagen a renderizar.
Teoría
Ahora, dado que la página / rutina a la que hice referencia no cita ninguna fuente, vale la pena explicar de dónde provienen esas rutinas cúbicas (y cómo funcionan). Tanto el que reproduje arriba como el spline Catmull-Rom muy similar que menciona justo debajo de él, son dos casos específicos de usar el siguiente núcleo de convolución cúbica:
La rutina mencionada anteriormente corresponde a un valor deα = - 1 , y la spline Catmull-Rom corresponde a α = - 1 / 2 . No entraré en demasiados detalles sobre cómo se deriva la forma general del núcleo, pero implica varias restricciones, como asegurarse de queψ ( x ) es uno en cero y cero en todos los demás enteros.
Esto es lo que parece:
Las dos opciones para el valor deα provienen de intentos de igualar varios aspectos de la función sinc , el núcleo de reconstrucción ideal. Ajusteα = - 1 hace la derivada de ψ coincidir con la derivada de la función sinc en x = 1 y haciéndolo igual a - 1 / 2 proporciona la mejor aproximación de baja frecuencia en su lugar. Por todas las cuentas, un valor deα = - 1 / 2 tiene propiedades mucho mejores en general, por lo que es probablemente el mejor valor para usar en la práctica. Se puede encontrar una discusión mucho más extensa en el siguiente documento, comenzando en la página 328:
Visión
Ahora, solo mirando ese núcleo en relación con la implementación real del código de interpolación, puede que no esté claro cómo se relacionan los dos. Básicamente, el proceso de interpolación puede considerarse como la suma de copias desplazadas del núcleo, que se escalan por las muestras de los datos, así:
De hecho, si tiene una implementación del núcleo, puede usarlo directamente para hacer la interpolación, de la siguiente manera:
Sin embargo, es mucho menos eficiente desde el punto de vista informático hacerlo de esa manera. Como un puente desde el enfoque de kernel directo al más simplificado anterior, considere que con un poco de manipulación algebraica, la primera implementación se puede poner de la siguiente forma:
En esta formulación, losα = - 1 , al igual que:
c0...c3
valores pueden considerarse como los coeficientes de un filtro FIR que se aplica a los valores de la muestra. Ahora es mucho más fácil ver cómo derivar la rutina del núcleo. Considere el núcleo conAhora evalúe ese núcleo simbólicamente en varios desplazamientos desplazados, teniendo en cuenta queμ ) varía de
mu
(0
a1
:Tenga en cuenta queμ - 1 , μ - 2 obtener "volteado" a 1 - μ , 2 - μ respectivamente debido al valor absoluto en X en la definición del núcleo. Ahora tenemos los polinomios exactos que se usan en la "versión FIR" de la rutina de interpolación. La evaluación de esos polinomios se puede hacer más eficiente a través de técnicas estándar (por ejemplo, el método de Horner ). Se pueden hacer cosas similares con otros núcleos, y también hay otras formas de construir implementaciones eficientes (véase la página de inicio de muestreo de audio digital ).
fuente