Identificación de Genes Mediante la Transformada
Modificada de Morlet
Jesús P. Mena-Chalco
Roberto Marcondes Cesar Junior
http://www.vision.ime.usp.br/∼jmena/DSPgenomics/
Departamento de Ciência da Computação - IME - USP
13/01/2006
Introducción: Genoma
El genoma de un organismo es
un modelo para que este pueda
auto construirse y mantenerse.
Casi todas las células de los organismos tienen un genoma.
Diferentes tipos de eucariotos
tienen diferentes números de
cromosomas:
Café (88), perros (78), Humanos (46), ratones (40), Manzana
(34), Drosofila (8).
“National Human Genome Research Institute” (NHGRI).
1
Introducción: DNA
Todo organismo vivo almacena su
información hereditária en la forma de
moléculas doblemente enlazadas de DNA.
Tipos de monómeros:
Adenina: A
Citosina: C
Guanina: G
Timina: T
Alberts et al, Molecular Biology of the Cell 2002.
2
Introducción: Genes
Replicação
Un gen es una región que expresa o
controla una proteı́na.
5’
3’
Inter-génica
gene
DNA
Transcrição
Sub-regiones:
éxon
1.
2.
3.
4.
5.
6.
7.
8.
9.
De reconocimiento (promotora);
De inicio de transcripción;
Región no-traducida 50 ;
De inı́cio de traducción (start codon);
Región para la codificación de proteı́na (CDS);
De traducción (stop codon);
Región no-traducida 30 ;
De poliadenilación (polyA, eucariotos);
De fin de transcripción.
íntron
Pre-mRNA
Retirada dos íntrons
mRNA
Tradução
...
Ser
Ala
Val
...
Proteína
3
Introducción: Proteı́nas
Las células en un organismo poseen el mismo DNA: el mismo conjunto de genes.
Pero diferentes genes son expresos (funcionalmente) en las diferentes células.
Células foto-receptor: conos
Célula neuronal
Célula de la sangre
Cuando un gen es expreso da las instrucciones a la célula para producir una
proteı́na particular.
4
Ejemplo de una proteı́na: Mioglobina
Representación de la estrutura 3D (135 Amino ácidos). Posiblemente causante de la falla renal aguda.
5
Tópicos
El problema de la identificación de genes.
Métodos de DSP para la identificación de CDSs.
Transformada modificada de Morlet.
Método propuesto.
Resultados.
Conclusiones.
6
El Problema: Identificación de Genes
Un tópico importante en el análisis de secuencias biológicas es la busqueda de genes (identificación de regiones codificantes de proteı́na).
Metodologias computacionales para identificar genes e otras regiones funcionales fueron desarrolladas en los últimos 20 años.
Los métodos de procesamiento digital de señales (DSP) tiene un papel
importante en ese contexto.
Los métodos de DSP brindan una base robusta para la identificación de
regiones codificantes de proteı́na (CDSs).
7
El Problema: Identificación de Genes
Categorias que agrupan abordages para su solución:
1. Métodos basados en reconocimento de patrones:
Busqueda por sı́tios: se busca la presencia o ausencia de una secuencia
especı́fica, patrón o consenso asociado a la expresión genica;
Busca por contenido: se busca segmentos con propiedades especı́ficas.
2. Métodos basados en comparaciones por homologia con proteı́nas.
3. Métodos basados en el uso de expressed sequence tags (ESTs).
8
Periodicidades en las Regiones Codificantes
Las CDSs, tipicamente exhiben una organización periódica de tres bases
(TBP, three-base periodicity) no uniforme (latente) que no es encontrada en
otras regioes [EEKR04].
Esa propiedade ha sido analisada para explicar su causa y cuantificarla [SL86].
Las frecuencias no uniformes del codon usage determinan la periodicidad.
El código genético es responsáble por el tamaño del perı́odo [EEKR04].
9
Mapeamiento Numérico de Nucleotı́deos
Análisis de los datos simbólicos de secuencias de DNA para ser tratados como
secuencias numéricas.
Mapeamiento fijo.
Regla
A
1
2
3
4
5
6
7
Enlaces de hidrogenio
Purina/pirimidina
Hibrida
Base A
Base C
Base G
Base T
0
1
1
1
0
0
0
Atribución
C
G
1
0
1
0
1
0
0
1
1
0
0
0
1
0
T
0
0
0
0
0
0
1
Mapeamiento basado en critérios de optimización.
10
Mapeamiento Fijo Binário
Sea a, c, g e t valores numéricos arbitrários correspondientes a las bases de
una secuencia de DNA A, C, G e T .
Una secuencia s de DNA de tamaño N puede ser representada como
s[b] = a.uA[b] + c.uC [b] + g.uG[b] + t.uT [b],
b = 0, 1, . . . , N − 1
donde uX [n] representa la secuencia binária asociada a la secuencia s.
Esta representación permite que uA[b] + uC [b] + uG[b] + uT [b] = 1
11
Análisis de Fourier
La transformada de Fourier posibilita decomponer una señal en componentes
que representen frecuencias.
Dada una señal f (t) la transformada de Fourier es definida como
Z ∞
f (t)e−jωtdt
F (ω) =
−∞
La transformada de Fourier de tiempo reducido es definida como
Z ∞
ST F T (b, ω) =
g ∗(t − b)f (t)e−jωtdt
−∞
12
Espectro de Frecuencia de DNA
La Transformada Discreta de Fourier de s es definida como [Ana01]
S[k] =
N
−1
X
s[b]e−2πjkb/N ,
k = 0, 1, . . . , N − 1
b=0
s[b] = a.uA[b] + c.uC [b] + g.uG[b] + t.uT [b]
S[k] = a.UA[k] + c.UC [k] + g.UG[k] + t.UT [k]
El espectro de frecuencia total es representado por
E[k] = |UA[k]|2 + |UC [k]|2 + |UG[k]|2 + |UT [k]|2
13
Espectro de Frecuencia
Arabidopsis thaliana
4
7
x 10
7000
6
6000
5
5000
4
Energía
Energía
4000
3
3000
2
2000
1
1000
0
10 9 8
7
6
5
4
Freqüência
3
Región codificante (CDS)
2
0
10 9 8
7
6
5
4
Freqüência
3
2
Región inter-genica
14
Métodos de Fourier y DNA
En [TRB+97] se define 4 coeficientes normalizados en la frecuencia tres ( N3 ),
como
A=
G=
1
UA
N
1
UG
N
N
,
3
N
,
3
C=
T =
1
UC
N
1
UT
N
N
,
3
N
,
3
y el identificador de CDSs como
W = |A|2 + |C|2 + |G|2 + |T |2,
15
Métodos de Fourier y DNA
0.016
Basado en el trabajo [TRB+97]
0.014
0.012
Coeficiente
0.01
Gen F56F11.4 de C. elegans
0.008
Posición relativa
0.006
928-1039
2528-2857
4114-4377
5465-5644
7255-7605
0.004
0.002
0
0
1000
2000
3000
4000
Posição
5000
6000
7000
Tamaño
112
330
264
180
351
8000
16
Métodos de Fourier y DNA
En [Ana01] se define
W = |a.A + c.C + g.G + t.T |2
donde a, c, g e t son números complejos arbitrários tal que A + C + G + T = 0.
E{|a.A + t.T + g.G|} − E{|a.AR + t.TR + g.GR|}
p(a, g, t) =
std(|a.A + t.T + g.G|) + std(|a.AR + t.TR + g.GR|)
Para los genes del cromosoma XVI de S. cerevisiae
a = 0,10 + 0,12j
c=0
g = 0,45 − 0,19j
t = −0,30 − 0,20j
17
Métodos de Fourier y DNA
−3
5
x 10
Basado en el trabajo [Ana01]
4
Gen F56F11.4 de C. elegans
Coeficiente
3
Posición relativa
2
928-1039
2528-2857
4114-4377
5465-5644
7255-7605
1
0
0
1000
2000
3000
4000
Posição
5000
6000
7000
Tamaño
112
330
264
180
351
8000
18
Filtros Digitais y DNA
C. Elegans
Filtro pasa banda
Filtro multistage
[VY04]
19
Análise en Wavelets
La transformada en wavelets permite un análisis tiempo-escala de una señal
en terminos de señales simples (wavelet).
Para una señal u a transformada en wavelets contı́nua es dada por:
1
U (b, a) = √
a
a>0
b
ψ(t)
√1
a
Z
∞
u(t)ψ ∗
−∞
t−b
dt
a
coeficiente de escala.
coeficiente de traslación (tiempo o posición).
función de análisis wavelet.
factor de normalización de la energia.
20
Función de Análise de Morlet
Apropiada para el análisis de patrones periódicos locales, pues es bien localizada en el domı́nio del tiempo y de la frecuencia.
2
ψM (t) =
t
ejω0te− 2
1
Real
Imaginária
0.8
0.6
0.4
Amplitude
0.2
0
−0.2
−0.4
−0.6
−0.8
−1
−10
−8
−6
−4
−2
0
Tempo
2
4
6
8
10
21
Diferencias entre las Funciones de Análisis
1
1
0.8
0.8
0.6
0.6
0.4
0.4
Amplitude
amplitude
0.2
0
0.2
0
−0.2
−0.2
−0.4
−0.4
−0.6
−0.6
−0.8
−8
−6
−4
−2
0
tempo
2
4
6
8
−0.8
−10
10
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
Amplitude
amplitude
−1
−10
0
−0.2
−0.4
−0.4
−0.6
−0.6
−4
−2
0
Tempo
2
4
6
8
10
−8
−6
−4
−2
0
Tempo
2
4
6
8
10
−8
−6
−4
−2
0
Tempo
2
4
6
8
10
−0.8
−1
−10
−8
−6
−4
−2
0
tempo
2
4
6
8
−1
−10
10
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
Amplitude
amplitude
−6
0
−0.2
−0.8
−8
0
0
−0.2
−0.2
−0.4
−0.4
−0.6
−0.6
−0.8
−0.8
−1
−10
−8
−6
−4
−2
0
tempo
2
4
6
8
Morlet
ψM (t) =
2
jω0 t − t2
e
e
10
−1
−10
“Gaborettes”
G(t, a) =
2
jat − t2
e e
22
Transformada Modificada de Morlet (MMT)
De la función de análisis de Morlet tenemos que
ψ
t−b
a
1
U (b, a) = √
a
2
t−b
(
a )
t−b
jω0 ( a ) −
2
e
=e
∞
Z
2
jω0 ( t−b
a ) −
u(t)e
e
( t−b
a )
2
dt
−∞
Usamos el parametro de escala a para mantener constante la frecuencia
1
U (b, a) = √
a
Z
∞
(t−b)2
−
u(t)ejω0(t−b)e 2a2
dt
−∞
23
Función de Análisis da MMT
Apropiada para el análisis de patrones periódicos locales de frecuencia fija, y
de escala variable.
t2
−
ejω0te 2a2
ψM M (t, a) =
1
Real
Imaginária
0.8
0.6
0.4
Amplitude
0.2
0
−0.2
−0.4
−0.6
−0.8
−1
−10
−8
−6
−4
−2
0
2
4
6
8
10
Tempo
24
Diferencias entre las Funciones de Análisis
1
1
1
0.8
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.6
0
Amplitude
amplitude
amplitude
0.4
0
−0.2
−0.2
−0.4
−0.4
−0.6
−0.6
−0.8
−0.8
0.2
0
−0.2
−6
−4
−2
0
tempo
2
4
6
8
−0.6
−1
−10
10
−8
−6
−4
−2
0
tempo
2
4
6
8
−0.8
−10
10
1
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0
Amplitude
1
0.8
amplitude
1
0.8
0
−0.2
−0.2
−0.4
−0.4
−0.4
−0.6
−0.6
−0.6
−0.8
−0.8
−8
−6
−4
−2
0
tempo
2
4
6
8
−8
−6
−4
−2
0
tempo
2
4
6
8
−1
−10
10
1
1
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
Amplitude
1
0
0
−0.2
−0.2
−0.4
−0.4
−0.4
−0.6
−0.6
−0.6
−0.8
−0.8
−8
−6
−4
−2
0
tempo
2
4
6
8
10
Morlet modificado
ψM M (t, a) =
t2
jω0 t − 2a2
e
e
−4
−2
0
Tempo
2
4
6
8
10
−8
−6
−4
−2
0
Tempo
2
4
6
8
10
−8
−6
−4
−2
0
Tempo
2
4
6
8
10
0
−0.2
−1
−10
−6
−0.8
−1
−10
10
−8
0
−0.2
−1
−10
amplitude
−8
amplitude
amplitude
−1
−10
−0.4
−0.8
−1
−10
−8
−6
−4
−2
0
tempo
2
4
6
8
Morlet
ψM (t) =
2
jω0 t − t2
e
e
10
−1
−10
“Gaborettes”
G(t, a) =
2
jat − t2
e e
25
Nuevo Método para Identificación de CDSs
Seqüência
de DNA
Mapeamento
fixo
Seqüências
binárias
MMT
Coeficientes
da transformação
normalizados
CDSs com
TBP latente
Limiarização
Coeficientes
da Projeção
Projeção no
eixo das posições
26
Mapeamiento de Bases
Se utiliza 4 reglas del mapeamiento fijo binário (uA, uC , uG, e uT ).
A
C
1000101...0110000
0010000...0000101
ATCGACA...TAAGCTC
G
Seqüência de DNA
T
0001000...0001000
0100000...1000010
Seqüências binárias
27
Aplicación de la MMT
Se calcula la MMT de las secuencias binárias, para un tamaño N arbitrário de
ψM M con ω0 = N3 y diferentes escalas.
1
UA(b, a) = √
a
1
UC (b, a) = √
a
∞
Z
∗
uA(t)ψM
M (t − b, a)dt
−∞
Z ∞
∗
uC (t)ψM
M (t − b, a)dt
−∞
∞
1
UG(b, a) = √
a
Z
1
UT (b, a) = √
a
Z
∗
uG(t)ψM
M (t − b, a)dt
−∞
∞
∗
uT (t)ψM
M (t − b, a)dt
−∞
28
Normalización de los Coeficientes
Los coeficiente son normalizados a fin de mantener una medida comparable
en todas las escalas.
2
mA(b, a) = a |UA(b, a)|
2
mC (b, a) = a |UC (b, a)|
2
mG(b, a) = a |UG(b, a)|
2
mT (b, a) = a |UT (b, a)|
La medida normalizada total de la secuencia de DNA es dada por:
M (b, a) = mA(b, a) + mC (b, a) + mG(b, a) + mT (b, a)
29
Proyección de los Coeficientes
Los coeficientes de la MMT son proyectados en el eje de las posiciones, a fin
de representar las posibles CDSs.
X
Mp(b) =
M (b, a), 1 ≤ b ≤ N
a
Las proyecciones en el eje de las escalas revelan cual de ellas mantiene mayor energia através de las posiciones
Ms(a) =
N
X
M (b, a),
∀a
b=1
30
Limiarización de los Coeficientes de Proyección
El proceso de la limiarización corresponde a una tentativa de establecer las
fronteras entre las CDSs.
Una de las formas es mediante Wavelet shrinkage, en el cual coeficientes abajo de um limite (“error máximo”) son substituı́dos por cero.
Es considerado un limiar porcentual en las magnitudes de los coeficientes de
proyección.
31
La Importancia de la Escala
Con 20 escalas a exponencialmente separadas en el intervalo [0,25, 0,5]
Coeficientes de la Transformación
Coeficientes de Proyección
Posición
Posición
T
G
C
A
Unión
Gen BTU02285 (Bos taurus) de 6396bp con 6 CDSs.
32
La Importancia de la Escala
Con 20 escalas a exponencialmente separadas en el intervalo [0,025, 0,5]
Coeficientes de la Transformación
Coeficientes de Proyección
Posición
Posición
T
G
C
A
Unión
Gen BTU02285 (Bos taurus) de 6396bp con 6 CDSs.
33
La Importancia de la Escala
Con 20 escalas a exponencialmente separadas en el intervalo [0,001, 0,5]
Coeficientes de la Transformación
Coeficientes de Proyección
Posición
Posición
T
G
C
A
Unión
Gen BTU02285 (Bos taurus) de 6396bp con 6 CDSs.
33
La Importancia de la Escala
Con 20 escalas a exponencialmente separadas en el intervalo [0,05, 0,5]
Coeficientes de la Transformación
Coeficientes de Proyección
Posición
Posición
T
G
C
A
Unión
Gen BTU02285 (Bos taurus) de 6396bp con 6 CDSs.
33
La Importancia de la Proyección
Para 20 escalas a exponencialmente separadas en el intervalo [0,05, 0,5]
Coeficientes de Proyección
T
0.89
G
1.39
C
3.46
A
3.17
União
7.99
0
3663
Posição
4221
4779
5285
34
La Importancia de la Limiarización
Para 20 escalas a exponencialmente separadas en el intervalo [0,05, 0,5]
Coeficientes de Proyección de la Unión
35
La Importancia de la Limiarización
Para 20 escalas a exponencialmente separadas en el intervalo [0,05, 0,5]
Coeficientes de Proyección de la Unión
Limiarización arbitrária
35
La Importancia de la Limiarización
Para 20 escalas a exponencialmente separadas en el intervalo [0,05, 0,5]
Coeficientes de Proyección de la Unión
Limiarización arbitrária
Posibles CDSs
35
Secuencias de Prueba
Secuencias sintéticas.
Secuencias reales.
Conjunto
Región
Cantidad
Bases
Tamaño
Média Desvio
A
(570 secs.)
Éxons
Íntrons
Inter-genicas
2649
2079
1132
444498 (15.4 %)
1310452 (45.3 %)
1137199 (39.3 %)
168
630
1004
222
909
1464
B
(195 secs.)
Éxons
Íntrons
Inter-genicas
948
753
390
199176 (14.4 %)
642788 (46.4 %)
544044 (39.2 %)
210
854
1395
271
130
2261
36
Pruebas Preliminares
Coeficientes de la STFT gen BTU02285
1.05
T
T
1.03
1.90
G
G
1.38
3.85
C
C
3.19
2.73
União
6.54
7.45
União
A
A
2.68
0
3663
4221
4779
Posição
Ventana de 200bp
5285
3663
4221
4779
5285
Posição
Ventana de 400bp
37
Pruebas Preliminares
Gen BTU02285
T
T
0.89
G
G
1.39
C
C
3.46
A
A
3.17
0.05
União
União
7.99
0.5
3663
4221
4779
5285
Posição
Coeficientes MMT normalizados
0
3663
Posição
4221
4779
5285
Coeficientes de proyección
38
Medidas de Exactitud
Las medidas de exactitud en el nı́vel de los nucleotı́deos [BG96], proponen
una forma de comparación de regiones identificadas con CDSs conocidas
biologicamente.
La medición de regiones identificadas contra CDSs conocidas es realizada
mediante conteo de nucleotı́deos.
TN
FN
TP
FN
TN
FP
TP
TN
CDSs
conhecidas
Regiões
identificadas
39
Medidas de Exactitud
Sensibilidad (Sn), proporción de nucleotı́deos codificantes correctamente
identificados como codificantes.
Sn =
TP
T P +F N
Especificidad (Sp), proporción de nucleotı́deos identificados como codificantes que son realmente codificantes.
Sp =
TP
T P +F P
Coeficiente de correlación (CC), medida que combina a Sn y Sp.
CC = √
T P.T N −F N.F P
(T P +F N )(T N +F P )(T P +F P )(T N +F N )
40
Resultados Preliminares
Desempeño de la MMT y de la STFT para el gen BTU02285
1
0.9
0.8
0.7
Sn
0.6
0.5
0.4
0.3
0.2
0.1
0
MMT
STFT (200)
STFT (400)
0
0.1
0.2
0.3
0.4
0.5
Sp
0.6
0.7
0.8
0.9
1
41
Resultados Preliminares
Desempeño de la MMT y de la STFT para el gen BTU02285
1
MMT
STFT (200)
STFT (400)
0.9
0.8
0.7
CC
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.1
0.2
0.3
0.4
0.5
Limiar
0.6
0.7
0.8
0.9
1
42
Resultados Preliminares
Desempeño de la MMT y de la STFT para el conjunto A
1
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.6
CC
Sn
1
0.5
0.5
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0
0.1
MMT
STFT (200)
STFT (400)
0
0.1
0.2
MMT
STFT (200)
STFT (400)
0.3
0.4
0.5
Sp
0.6
0.7
0.8
0.9
1
0
0
0.1
0.2
0.3
0.4
0.5
Limiar
0.6
0.7
0.8
0.9
1
570 secuencias
43
Resultados Preliminares
Desempeño de la MMT y de la STFT para el conjunto Am30
1
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.6
CC
Sn
1
0.5
0.5
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0
0.1
MMT
STFT (200)
STFT (400)
0
0.1
0.2
MMT
STFT (200)
STFT (400)
0.3
0.4
0.5
Sp
0.6
0.7
0.8
0.9
1
0
0
0.1
0.2
0.3
0.4
0.5
Limiar
0.6
0.7
0.8
0.9
1
469 secuencias. Tamaño de los éxons mayores a 30bp.
44
Resultados Preliminares
Desempeño de la MMT y de la STFT para el conjunto Am100
1
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.6
CC
Sn
1
0.5
0.5
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0
0.1
MMT
STFT (200)
STFT (400)
0
0.1
0.2
MMT
STFT (200)
STFT (400)
0.3
0.4
0.5
Sp
0.6
0.7
0.8
0.9
1
0
0
0.1
0.2
0.3
0.4
0.5
Limiar
0.6
0.7
0.8
0.9
1
103 secuencias. Tamaño de los éxons mayores a 100bp.
45
Conclusiones
La MMT tiene un desempeño superior a la STFT. Un nivel de exactitud mayor es alcanzado cuando los tamaños de las CDSs son mayores a 100bp.
El método se basa unicamente en la TBP existente en las CDSs. No es
usada ninguna otra outra información adicional.
Este nuevo método es mas robusto a la variación de escalas.
46
Referencias
[Ana01]
D. Anastassiou. Genomic signal processing. IEEE Signal Processing Magazine,
8(4):8–20, 2001.
[BG96]
M. Burset and R. Guigó. Evaluation of gene structure prediction programs. Genomics, 34(3):353–367, 1996.
[EEKR04] S. T. Eskesen, F.Ñ. Eskesen, B. Kinghorn, and A. Ruvinsky. Periodicity of DNA in
exons. Journal Molecular Biology, 5(12):1–11, 2004.
[SL86]
B. D. Silverman and R. Linsker. A measure of DNA periodicity. Journal of Theoretical Biology, 118(3):295–300, 1986.
[TRB+97] S. Tiwari, S. Ramachandran, A. Bhattacharya, S. Bhattacharya, and R. Ramaswamy. Prediction of probable genes by Fourier analysis of genomic sequences.
Bioinformatics, 13(3):263–270, 1997.
[VY04]
P. P. Vaidyanathan and B. Yoon. The role of signal-processing concepts in genomics
and proteomics. Journal of the Franklin Institute, 341(1-2):111–135, 2004.
47