• Publicidad

Búsqueda de picos significativos

Perl aplicado a la bioinformática

Búsqueda de picos significativos

Notapor ptahotep » 2013-07-26 13:37 @609

Hola, soy nuevo en esta comunidad a la que estoy encantado de pertenecer.

Llevo programando ya un tiempo en Perl, aunque vengo de la rama de Biología. Actualmente estoy con un problema en un programa que estoy diseñando para el recorte de picos a partir de unos datos de histogramas, de los que muestro un extracto:
Sintáxis: [ Descargar ] [ Ocultar ]
Using text Syntax Highlighting
P       1       2       3       4       5       6
1       0       0       0       0       0       0
2       0       0       0       0       0       0
3       0       0       0       0       0       0
4       0       0       1       0       0       0
5       0       0       1       0       0       0
6       0       0       1       0       0       0
7       0       0       1       0       0       0
8       0       0       1       0       0       0
9       0       0       1       0       0       0
10      0       0       1       0       0       0
11      0       0       2       0       0       0
12      0       0       3       0       0       0
13      0       0       3       0       3       0
14      0       0       3       0       3       0
15      0       0       3       0       5       0
16      0       0       3       0       5       0
17      0       0       3       0       5       0
18      0       0       3       0       5       0
19      0       0       3       0       6       0
20      0       0       4       0       7       0
21      0       0       4       0       7       0
22      0       0       4       0       7       0
23      0       0       4       0       7       0
24      0       0       4       0       7       0
25      0       0       4       0       7       0
26      0       0       4       0       7       0
27      0       0       4       0       7       0
28      0       0       4       0       7       0
29      0       0       4       0       9       1
30      0       0       4       2       9       2
31      0       0       4       2       9       2
32      0       0       4       2       9       2
33      0       0       5       4       9       2
34      0       0       5       4       9       3
35      0       0       5       4       9       3
36      0       0       5       4       9       4
37      0       0       5       6       9       4
38      0       0       5       6       9       4
Coloreado en 0.000 segundos, usando GeSHi 1.0.8.4

Tengo miles de archivos como estos, con unos miles de líneas, donde la primera columna es la posición nucleotídica de unas secuencias, y el resto de columnas son valores de acumulación de señales en los seis marcos abiertos de lectura de las secuencias.

Lo que necesito, y hace ahora mi programa, es buscar picos significativos, separadamente para cada fase. Para ello, tengo calculada la media y desviación para los miles de archivos, y cuando analizo cada uno por separado, calculo un z-score para cada posición (siempre recuerden, separadamente para cada fase). Cuando el z-score es mayor de un umbral (2.5) considero que hay un pico, y cuando hay 20-30 posiciones consecutivas con un z-score > 20 recojo el pico.

Como pueden ver, lo que cojo no es realmente el pico completo, sino la región más alta del pico (de una forma muy sencilla, y quizás burda). Así que quisiera ver alguna forma de recoger las posiciones de TODO el pico, es decir, desde que comienza a subir hasta cuando acaba de bajar. Y claro, sólo quedarme con los picos significativos. Me da igual si consideráis que tengo una sola columna (la 2ª, 3ª, 4ª, 5ª, 6ª o 7ª), ya que una vez sepa cómo hacerlo con una, ya sabría con todas.

¿Sabéis de algún módulo, o me podríais ayudar con algún código que resuelva el problema? Gracias por adelantado,

Pta.
ptahotep
Perlero nuevo
Perlero nuevo
 
Mensajes: 8
Registrado: 2013-07-26 13:21 @598

Publicidad

Re: Búsqueda de picos significativos

Notapor explorer » 2013-07-26 14:30 @646

Bienvenido a los foros de Perl en Español, ptahotep.

Entiendo que lo que llamas z-score es la diferencia de un valor con respecto al siguiente.

Lo que dices del umbral, no lo entiendo muy bien. Dices que miras por un umbral mayor de 2.5, pero luego hablas de un z-score mayor de 20. Creo que te refieres a superar las veinte posiciones con el umbral superior a 2.5.

No sé a qué te refieres con "cuando acaba de bajar". ¿Te refieres a llegar al valor 0?

Sería interesante ver cómo haces el cálculo del z-score, para tener claro en qué consiste ese cálculo.

Una vez localizado el punto, lo que se puede es ir hacia adelante y hacia atrás, para localizar los puntos más bajos, y luego restringirlo a 30 posiciones máximo, pero entonces, no sabemos qué criterio tomar para saber por dónde cortar.

En fin... a mi me falta información. Unos ejemplos vendrían bien :)
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14486
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Búsqueda de picos significativos

Notapor ptahotep » 2013-07-27 11:20 @514

Gracias por la respuesta. La verdad es que olvidé explicar lo del z-score y luego ya no pude hacerlo. El z-score en un sencillo cálculo: Z-score = Valor - Media/Desviación

La media y desviación la calculo previamente, a partir de todos los datos. Así, si un valor es mucho más alto que la media, saldrá con un Z-score positivo y alto (mayor de 2.5).

En cuanto a lo que quiero hacer, creo que se ve mejor con un ejemplo. Imagina que tengo la siguiente columna de números:
0 0 0 1 3 4 6 8 10 12 9 7 7 5 3 2 2 4 5 4 2 1 1 2 3 7 9 12 14 11 9 7 3 2 1 0 0 0

Lo que yo quisiera es localizar los dos picos más significativos ("más altos") que son éstos:
1 3 4 6 8 10 12 9 7 7 5 3 2
1 2 3 7 9 12 14 11 9 7 3 2 1

De hecho, lo que busco son las posiciones de esos picos, es decir, esto otro:
4-16
23-35
ptahotep
Perlero nuevo
Perlero nuevo
 
Mensajes: 8
Registrado: 2013-07-26 13:21 @598

Re: Búsqueda de picos significativos

Notapor explorer » 2013-07-27 11:34 @523

Te falta por decir el criterio que usas para escoger los rangos que rodean a los valores pico.
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14486
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Búsqueda de picos significativos

Notapor ptahotep » 2013-07-27 11:56 @539

Vamos a olvidarnos del Z-score, ya que eso es un simple número. Imagina que mi umbral son 'valores>10'. En el ejemplo anterior hay 5 valores que lo superan: 2 que 'marcan' el primer pico, y 3 que marcan el 2º pico. Por otro lado, imagina que yo sólo cogeré un pico si tiene al menos 2 valores por encima de umbral, lo que por ejemplo no tomaría como significativo este otro pico:
0 0 1 4 5 8 9 12 9 8 6 3 2 2 1 0 0 0

Entonces, dado un pico con al menos 2 valores por encima de 10, quiero que mi programa devuelva las posiciones de todo el pico completo (aunque sólo la parte central, los 2-3 valores en el ejemplo, superen el umbral).
ptahotep
Perlero nuevo
Perlero nuevo
 
Mensajes: 8
Registrado: 2013-07-26 13:21 @598

Re: Búsqueda de picos significativos

Notapor explorer » 2013-07-27 13:41 @611

Quedan detalles por aclarar, como por ejemplo, si un valor es pico en un extremo (al principio o final), si lo consideramos aislado o no.

Esta es una primera prueba:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. #!/usr/bin/perl
  2. use v5.12;
  3. use Range::Object::Serial;                              # gestión de rangos de números
  4.  
  5. my $valor_de_pico = 10;
  6. my @acumulaciones = qw(0 0 10 1 3 4 6 8 10 12 9 7 7 5 3 2 2 4 5 4 2 1 1 2 3 7 9 12 14 11 9 7 3 2 1 0 10 0);
  7.  
  8. say "Acumulaciones:     [@acumulaciones]";
  9.  
  10. ## Búsqueda de posiciones de los picos
  11. my $posiciones = Range::Object::Serial->new();
  12.  
  13. for(my $pos = 0; $pos < @acumulaciones; $pos++) {
  14.     $posiciones->add($pos)                              # añadimos un valor de posición de pico encontrada
  15.         if $acumulaciones[$pos] >= $valor_de_pico;      # si en esa posición, el valor es igual o superior al umbral
  16. }
  17.  
  18. say "Picos encontrados: [", $posiciones->stringify, "] [", $posiciones->stringify_collapsed, "]";
  19.  
  20. ## Simplificación 1: quitar los picos que están aislados
  21. # stringify_collapsed() nos devuelve la representación simplificada de los rangos de posiciones que forman los picos.
  22. # Partimos esa representación, por zonas aisladas, buscando por las comas (,).
  23. # Filtramos solo aquellas zonas que tienen un '-' en su representación, pues implica que tienen más de una posición consecutiva.
  24. my @picos = grep { /-/ } split /,/, $posiciones->stringify_collapsed;
  25.  
  26. ## Informar
  27. for my $pico (@picos) {
  28.     say "Pico en $pico";
  29. }
Coloreado en 0.004 segundos, usando GeSHi 1.0.8.4
sale:
Sintáxis: [ Descargar ] [ Ocultar ]
Using text Syntax Highlighting
Acumulaciones:     [0 0 10 1 3 4 6 8 10 12 9 7 7 5 3 2 2 4 5 4 2 1 1 2 3 7 9 12 14 11 9 7 3 2 1 0 10 0]
Picos encontrados: [2,8,9,27,28,29,36] [2,8-9,27-29,36]
Pico en 8-9
Pico en 27-29
Coloreado en 0.000 segundos, usando GeSHi 1.0.8.4

No está mal... se resuelve en una línea de programa ;)
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14486
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Búsqueda de picos significativos

Notapor ptahotep » 2013-07-28 10:53 @495

Gracias, se acerca a lo que buscaba, de hecho es lo que yo tengo implementado, salvo que lo hacía de manera menos eficiente.

Pero ahora lo que quiero es el pico completo, incluyendo posiciones alrededor del rango:
0 0 10 1 3 4 6 8 10 12 9 7 7 5 3 2 2 4 5 4 2 1 1 2 3 7 9 12 14 11 9 7 3 2 1 0 10 0

3-11
22-34

Como ves, quiero el rango desde que comienza a "subir" hasta que termina de "bajar". Y claro, también quisiera los posibles picos de los extremos, pero siempre 'completos'. Aunque se 'identifican como significativos', cuando al menos tenemos un rango de 2 por encima de 10.

Eso ya requerirá más de una línea :wink:
ptahotep
Perlero nuevo
Perlero nuevo
 
Mensajes: 8
Registrado: 2013-07-26 13:21 @598

Re: Búsqueda de picos significativos

Notapor explorer » 2013-07-28 21:13 @925

Bueno, este es el siguiente intento, con la información disponible hasta ahora:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. #!/usr/bin/perl
  2. use v5.12;
  3. use Range::Object::Serial;
  4.  
  5. my $valor_de_pico = 10;
  6.  
  7. my @secuencias = (
  8.     '0 0 10 1 3 4 6 8 10 12  9  7  7  5  3  2  2  4  5  4  2  1  1  2  3  7  9 12 14 11  9  7  3  2  1  0  0 10',
  9. #    0 1  2 3 4 5 6 7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
  10. #           \__________P__P_____/                               \_______________P__P__P______________/      \P/
  11.  
  12.     '0 0 10 1 3 4 6 8 10 12  9  8 11 12  3  2  2  1  0  0',
  13. #    0 1  2 3 4 5 6 7  8  9 10 11 12 13 14 15 16 17 18 19
  14. #           \__________P__P____\/__P__P_____/
  15.  
  16. );
  17.  
  18. my @acumulaciones;
  19.  
  20. for my $sec (@secuencias) {
  21.     busca_picos($sec);
  22. }
  23.  
  24. sub busca_picos {
  25.     @acumulaciones = split " ", $_[0];
  26.  
  27.     say "Acumulaciones:     [@acumulaciones]";
  28.  
  29.     # Búsqueda de picos
  30.     my $posiciones = Range::Object::Serial->new();
  31.     for my $pos (0 .. $#acumulaciones) {
  32.         $posiciones->add($pos)                          # añadimos un valor de posición de pico encontrada
  33.             if $acumulaciones[$pos] >= $valor_de_pico;
  34.     }
  35.     say "Picos encontrados: [", $posiciones->stringify_collapsed, "]";
  36.  
  37.     # 1 - Simplificación: quitar los picos que están aislados
  38.     my @picos = grep { /-/ } split /,/, $posiciones->stringify_collapsed;
  39.     $posiciones = Range::Object::Serial->new( join ',', @picos );
  40.  
  41.     # 2 - Arreglo: volvemos a añadir los picos que están en los extremos
  42.     for my $pos (0, $#acumulaciones) {
  43.         $posiciones->add($pos)
  44.             if $acumulaciones[$pos] >= $valor_de_pico;
  45.     }
  46.  
  47.     # 3 - Ampliación de la base de cada pico
  48.     my @posiciones_finales;
  49.     for my $zona_ref ($posiciones->collapsed) {
  50.  
  51.         my($limite_bajo, $limite_alto)
  52.             = (ref $zona_ref)                                           # la zona puede ser una referencia o no
  53.             ? @$zona_ref{'start','end'}                                 # caso de zona normal
  54.             : ($zona_ref, $zona_ref)                                    # caso de pico solitario
  55.             ;
  56.  
  57.         $limite_bajo = final_pico($limite_bajo, -1);                    # buscamos la base, por la izquierda
  58.         $limite_alto = final_pico($limite_alto,  1);                    # buscamos la base, por la derecha
  59.  
  60.         push @posiciones_finales, "$limite_bajo-$limite_alto";
  61.     }
  62.  
  63.     # Informar
  64.     for my $pico (@posiciones_finales) {
  65.         say "Pico en [$pico]";
  66.     }
  67. }
  68.  
  69. sub final_pico {
  70.     # Esta subrutina nos devuelve la posición final de caída desde un pico, yendo en una dirección
  71.     my($pos, $paso) = @_;
  72.  
  73.     $pos += $paso                                                               # nos seguimos moviendo
  74.         while                                                                   # mientras
  75.                 $pos + $paso > 0                                                # no lleguemos al límite por la izquierda
  76.         and     $pos + $paso < @acumulaciones                                   # no lleguemos al límite por la derecha
  77.         and     $acumulaciones[ $pos + $paso ] < $acumulaciones[ $pos ]         # sigamos bajando
  78.         and     $acumulaciones[ $pos + $paso ] > 0                              # y no lleguemos a un valor cero
  79.         ;
  80.  
  81.     return $pos;
  82. }
  83.  
Coloreado en 0.003 segundos, usando GeSHi 1.0.8.4
Sale:
Sintáxis: [ Descargar ] [ Ocultar ]
Using text Syntax Highlighting
Acumulaciones:     [0 0 10 1 3 4 6 8 10 12 9 7 7 5 3 2 2 4 5 4 2 1 1 2 3 7 9 12 14 11 9 7 3 2 1 0 0 10]
Picos encontrados: [2,8-9,27-29,37]
Pico en [3-11]
Pico en [22-34]
Pico en [37-37]
Acumulaciones:     [0 0 10 1 3 4 6 8 10 12 9 8 11 12 3 2 2 1 0 0]
Picos encontrados: [2,8-9,12-13]
Pico en [3-11]
Pico en [11-15]
Coloreado en 0.000 segundos, usando GeSHi 1.0.8.4
La segunda prueba es para demostrar el caso de dos picos seguidos. Vemos que tienen un límite común (la posición número 11).
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14486
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Búsqueda de picos significativos

Notapor ptahotep » 2013-07-29 07:11 @341

¡Estupendo! Muchísimas gracias por toda la ayuda. Desde luego, te pondré en los créditos del trabajo, si se llega a publicar en el futuro.

Ya lo he adaptado a mi código y funciona de maravilla. Esta tarde quiero ver si echo otro rato para ajustar más el recorte.

En realidad los número que tengo a veces suben y bajan significativamente en un mismo pico y querría considerar eso como el mismo pico. Así, picos cercanos (usando un umbral) los consideraría uno solo.

Es decir, no querría unir picos cercanos estrictamente, sino que no dejaría de recoger un pico, hasta que no haya bajado un número de puntos. Por ejemplo:
1 1 3 4 5 6 8 9 10 12 14 11 7 7 6 5 7 9 10 14 13 9 8 7 6 6 1 1 0
0 1 2 7 10 12 14 13 10 9 12 14 15 12 9 7 6 2 1 0

Ambos ejemplos de arriba los tendría que considerar como un único pico, ya que: el primero, cuando llega al 5, sube otra vez, pero no ha bajado lo suficiente. Y en el segundo, igual, y además se mantiene muy alto. De esta forma, obtendría picos más amplios.

Un saludo y gracias otra vez. Te voy contando. Por cierto, incluyo un ejemplo real.
Sintáxis: [ Descargar ] [ Ocultar ]
Using text Syntax Highlighting
P       1       2       3       4       5       6
1       0       0       0       0       1       0
2       0       0       0       0       1       0
3       0       0       0       0       1       0
4       0       0       1       0       2       0
5       0       0       1       0       2       0
6       0       0       1       0       2       0
7       0       0       1       0       2       0
8       0       0       1       0       2       0
9       0       0       1       0       2       1
10      0       0       1       0       2       2
11      0       0       2       0       2       4
12      0       0       3       1       2       4
13      0       0       3       1       2       4
14      0       0       3       1       2       6
15      0       0       3       1       2       6
16      0       0       3       1       2       6
17      0       0       3       1       2       7
18      0       0       3       1       3       8
19      0       0       3       1       3       8
20      0       0       4       1       3       8
21      0       0       4       1       3       8
22      0       0       4       1       3       8
23      0       0       4       1       3       8
24      0       0       4       1       3       9
25      0       0       4       1       3       10
26      0       0       4       2       3       10
27      0       0       4       2       3       10
28      0       0       4       2       3       10
29      0       0       4       2       4       10
30      0       0       4       2       4       10
31      0       0       4       2       7       10
32      0       0       4       2       7       10
33      0       0       5       2       7       11
34      0       0       5       3       8       11
35      0       0       5       3       9       11
36      0       0       5       3       10      11
37      0       0       5       3       11      11
38      0       0       5       3       11      11
39      0       0       5       3       14      11
40      0       0       5       4       14      13
41      0       0       5       4       15      13
42      0       0       5       4       15      14
43      0       0       5       4       15      14
44      0       0       5       5       15      14
45      0       0       5       5       16      14
46      0       0       5       5       18      14
47      0       1       5       5       19      14
48      0       1       5       5       19      13
49      0       1       5       5       20      14
50      0       1       5       7       20      14
51      0       1       5       7       21      13
52      0       1       4       7       23      15
53      0       1       5       7       24      16
54      0       1       5       7       24      16
55      0       1       5       7       24      16
56      0       2       5       7       25      13
57      0       2       5       7       25      12
58      0       2       5       7       24      11
59      0       2       5       7       26      11
60      0       2       4       7       27      11
61      0       2       4       6       28      10
62      0       2       4       6       28      7
63      0       2       4       6       28      7
64      0       2       4       6       29      7
65      0       2       4       6       29      6
66      0       2       6       7       33      6
67      0       2       6       8       33      6
68      1       2       6       8       34      6
69      1       2       6       7       34      6
70      1       2       6       7       35      6
71      1       2       5       7       34      6
72      1       2       5       6       34      6
73      1       2       5       6       34      6
74      1       2       6       6       33      6
75      1       2       6       7       33      5
76      1       2       6       7       34      4
77      1       2       6       7       34      4
78      1       2       6       7       34      4
79      1       2       6       7       33      4
80      1       2       6       7       33      6
81      1       2       6       7       33      5
82      1       2       6       7       32      6
83      1       2       6       7       32      6
84      1       2       6       7       32      6
85      1       2       6       6       30      6
86      1       1       6       6       30      6
87      1       1       6       6       30      6
88      1       1       6       6       30      7
89      1       1       4       7       30      7
90      1       1       4       4       28      7
91      1       1       4       4       28      7
92      1       1       4       4       28      8
93      1       1       5       4       28      9
94      3       1       5       4       26      9
95      3       1       5       6       26      9
96      4       1       6       6       24      10
97      4       1       6       6       24      10
98      4       1       6       6       24      10
99      5       1       7       6       24      8
100     6       1       7       6       24      8
101     6       1       7       6       21      8
102     6       1       8       6       22      8
103     6       1       8       7       21      8
104     8       1       8       8       20      8
105     8       1       8       8       20      8
106     8       1       8       8       20      8
107     8       1       8       8       19      8
108     8       1       10      8       19      8
109     8       1       10      9       18      8
110     8       1       12      9       17      8
111     8       1       12      9       17      8
112     7       1       12      9       17      8
113     8       1       12      8       17      8
114     8       1       13      8       18      8
115     8       1       14      8       17      8
116     8       1       14      7       15      8
117     8       1       17      7       12      7
118     8       1       17      8       12      7
119     7       1       17      8       14      7
120     7       1       17      8       15      7
121     8       1       17      8       15      8
122     8       1       17      8       15      7
123     8       1       17      7       15      9
124     8       1       15      7       15      10
125     8       1       15      7       12      10
126     8       1       15      7       11      11
127     8       1       15      7       12      11
128     9       1       15      7       12      11
129     9       1       14      8       12      12
130     9       1       14      8       12      12
131     10      1       14      10      12      12
132     10      1       13      11      12      12
133     10      1       12      10      12      12
134     10      1       9       10      12      12
135     10      1       9       11      12      12
136     10      1       9       11      12      13
137     10      1       9       11      12      13
138     11      1       9       12      13      14
139     11      1       9       13      11      15
140     11      1       9       13      9       15
141     11      1       9       13      10      15
142     10      1       7       13      10      15
143     10      1       7       13      9       15
144     10      1       7       13      9       15
145     10      1       6       13      9       14
146     9       1       6       13      10      13
147     10      1       6       13      11      14
148     12      1       6       13      11      14
149     12      1       6       12      11      13
150     10      1       6       12      11      13
151     10      1       5       12      11      12
152     11      1       5       12      12      11
153     11      1       5       12      11      12
154     11      1       5       11      10      12
155     11      1       5       11      10      12
156     11      1       5       11      11      12
157     11      1       5       11      12      12
158     11      1       5       10      12      12
159     11      0       5       10      12      12
160     10      0       5       10      13      12
161     10      0       5       10      14      12
162     10      0       5       9       14      11
163     10      0       5       9       14      10
164     10      0       5       9       13      10
165     10      0       5       8       13      11
166     10      0       5       8       13      12
167     9       0       4       8       13      11
168     9       0       4       8       13      11
169     9       0       5       8       13      11
170     9       0       5       7       14      11
171     9       0       6       7       14      10
172     10      0       6       7       14      9
173     10      0       6       7       14      9
174     10      0       5       7       14      9
175     10      0       5       7       14      8
176     10      0       5       8       14      8
177     9       1       5       8       14      8
178     8       1       6       8       14      8
179     8       1       6       6       16      8
180     7       1       6       7       16      8
181     5       1       9       6       16      8
182     5       1       9       6       16      8
183     5       1       9       7       16      8
184     6       1       9       6       17      6
185     6       1       9       6       17      5
186     6       1       9       6       16      4
187     6       1       9       6       16      4
188     6       1       9       6       16      4
189     6       1       9       6       16      3
190     6       1       9       6       15      3
191     8       1       9       6       15      3
192     8       1       10      5       15      3
193     7       1       10      5       14      3
194     8       1       10      4       14      3
195     8       1       10      4       14      3
196     8       1       10      4       14      3
197     8       1       10      4       13      3
198     8       1       9       4       12      3
199     8       1       9       4       12      1
200     8       1       9       4       12      1
201     8       1       9       3       12      1
202     8       1       10      3       10      1
203     9       1       9       3       10      1
204     9       0       9       3       9       1
205     9       0       9       3       9       0
206     9       0       9       2       9       0
207     9       0       9       1       8       0
208     10      0       9       1       8       0
209     10      0       9       0       8       0
210     10      0       9       0       9       0
211     10      0       9       0       8       0
212     9       0       9       0       7       0
213     9       0       9       0       7       0
214     9       0       9       0       6       0
215     8       0       9       0       6       0
216     8       0       9       0       5       0
217     8       0       9       0       3       0
218     8       0       9       0       3       0
219     8       0       9       0       3       0
220     8       0       9       0       3       0
221     8       0       9       0       3       0
222     7       0       9       0       3       0
223     7       0       9       0       3       0
224     7       0       9       0       3       0
225     7       0       8       0       3       0
226     7       0       8       0       3       0
227     7       0       8       0       2       1
228     6       0       7       0       1       1
229     6       0       5       0       1       1
230     6       0       5       0       2       1
231     6       0       5       0       2       1
232     6       0       5       0       2       1
233     5       0       5       0       2       1
234     5       0       6       0       1       1
235     5       0       6       0       1       1
236     5       0       6       0       1       1
237     5       0       7       0       1       1
238     5       0       8       0       1       1
239     5       0       8       0       1       3
240     5       0       8       0       1       3
241     5       0       8       0       1       3
242     4       0       8       1       1       3
243     4       0       8       1       1       3
244     3       0       8       1       1       3
245     3       0       8       1       1       3
246     3       0       8       1       1       3
247     3       0       8       1       1       4
248     3       0       8       1       1       4
249     3       0       9       1       1       4
250     3       0       9       2       1       4
251     3       0       9       2       1       4
252     3       0       9       2       1       5
253     3       0       9       2       1       5
254     3       0       9       2       1       6
255     3       0       9       2       1       7
256     3       0       9       2       1       7
257     3       0       10      2       1       7
258     3       0       7       3       1       8
259     3       0       7       3       1       8
260     3       0       7       3       1       8
261     3       0       7       3       0       8
262     3       0       7       4       0       9
263     3       0       7       4       0       9
264     3       0       7       4       0       11
265     3       0       7       5       0       11
266     3       0       7       5       0       11
267     3       0       6       5       0       13
268     3       0       6       5       0       13
269     2       0       6       5       0       14
270     2       0       6       5       0       14
271     2       0       6       5       0       15
272     0       0       6       5       0       15
273     0       1       6       5       0       15
274     0       1       6       5       0       15
275     0       1       6       6       0       17
276     0       1       6       6       0       17
277     0       1       6       6       0       17
278     0       1       6       6       0       18
279     0       1       6       6       0       19
280     0       1       6       6       0       18
281     0       1       6       6       0       18
282     0       1       6       6       0       19
283     0       1       6       6       0       19
284     0       1       6       6       0       19
285     0       1       6       6       0       20
286     0       1       5       5       0       20
287     0       1       5       5       0       19
288     0       1       5       4       0       18
289     0       1       5       4       0       18
290     0       1       5       4       0       18
291     0       1       5       4       0       19
292     0       0       5       4       0       18
293     0       0       5       4       1       16
294     0       0       5       4       1       16
295     0       0       4       4       1       15
296     0       0       4       4       1       15
297     1       0       4       3       1       16
298     1       0       4       3       1       25
299     1       0       4       3       1       26
300     2       0       3       3       1       26
301     2       0       2       3       1       24
302     2       0       2       3       1       25
303     2       0       2       3       2       24
304     2       0       2       4       2       24
305     3       0       2       4       2       24
306     3       0       2       4       2       24
307     3       0       2       4       2       24
308     3       0       2       4       2       23
309     3       0       2       4       3       23
310     4       0       2       4       3       23
311     4       0       2       4       3       23
312     5       0       2       4       3       22
313     5       0       2       4       3       21
314     5       0       2       4       3       21
315     5       0       2       4       3       20
316     5       0       2       4       3       20
317     5       0       2       5       3       19
318     5       0       2       5       3       19
319     5       0       2       5       4       21
320     5       0       2       5       4       13
321     5       0       2       4       4       12
322     6       0       2       4       4       12
323     6       0       2       4       4       12
324     6       0       2       3       4       12
325     6       0       0       3       5       12
326     7       0       0       3       5       11
327     7       0       1       3       5       11
328     6       0       1       2       5       11
329     5       0       2       2       5       10
330     5       0       2       2       4       10
331     5       0       2       2       4       10
332     5       0       2       1       4       10
333     5       0       2       1       4       9
334     5       0       3       1       4       9
335     5       0       3       1       4       8
336     5       0       3       1       4       7
337     5       0       3       0       4       7
338     5       0       3       0       4       7
339     5       0       3       0       4       6
340     5       0       3       0       4       6
341     5       0       4       0       4       6
342     4       0       5       0       4       6
343     3       0       6       0       4       6
344     2       0       6       0       3       6
345     2       0       6       0       3       5
346     1       0       6       0       3       5
347     1       0       6       0       4       5
348     1       0       7       0       3       6
349     1       0       8       0       3       6
350     1       0       8       0       3       7
351     1       0       9       0       2       8
352     0       0       10      0       2       8
353     0       0       10      0       2       8
354     0       0       10      0       2       8
355     0       0       10      0       2       8
356     0       0       10      0       2       8
357     0       0       12      0       2       8
358     0       0       13      0       2       8
359     0       0       13      0       2       7
360     0       0       13      0       2       7
361     0       0       14      0       2       7
362     0       0       15      0       3       7
363     0       0       17      0       5       7
364     0       0       17      0       5       7
365     0       0       22      0       5       6
366     0       0       23      0       5       6
367     0       0       25      0       6       6
368     0       0       29      0       6       5
369     1       0       33      0       6       5
370     5       0       35      0       6       4
371     6       0       36      0       6       4
372     6       0       38      0       6       4
373     7       0       43      0       6       4
374     7       0       45      0       6       4
375     7       0       46      0       6       4
376     8       0       47      0       7       4
377     8       0       48      0       9       4
378     8       0       49      0       9       4
379     8       0       53      0       9       4
380     9       0       55      0       9       5
381     10      0       57      0       9       3
382     10      0       59      0       10      1
383     10      0       61      0       11      1
384     10      0       64      0       11      1
385     11      0       65      0       11      1
386     11      0       65      0       11      1
387     11      0       65      0       11      1
388     11      0       64      1       11      1
389     12      0       65      3       10      1
390     13      0       66      3       10      1
391     13      0       66      5       10      1
392     13      0       69      5       10      1
393     14      0       69      6       13      1
394     13      0       70      6       13      1
395     14      0       69      6       14      1
396     13      0       70      7       17      2
397     13      0       71      9       19      2
398     13      0       72      12      21      2
399     12      0       71      12      21      2
400     12      0       70      13      23      2
401     13      0       70      13      25      2
402     13      0       71      15      26      2
403     14      0       71      16      27      2
404     14      0       70      16      27      2
405     13      0       72      16      27      2
406     14      0       73      16      27      2
407     14      0       72      17      28      2
408     14      0       73      18      29      2
409     15      0       74      19      29      2
410     15      0       72      18      30      2
411     16      0       70      24      31      2
412     16      0       70      27      31      3
413     18      0       69      27      31      3
414     18      0       68      28      31      3
415     19      0       70      29      31      3
416     19      0       69      29      30      3
417     19      0       68      29      31      3
418     19      0       72      29      31      3
419     19      0       71      28      32      3
420     19      0       71      29      32      5
421     19      0       70      29      32      5
422     19      0       70      29      33      5
423     19      0       69      30      34      5
424     20      0       69      32      36      5
425     19      0       67      32      35      8
426     19      0       66      32      37      8
427     18      0       66      32      37      8
428     18      0       66      32      37      8
429     18      1       65      32      38      8
430     18      1       63      33      38      8
431     18      1       62      33      39      8
432     17      1       62      33      41      8
433     18      1       62      33      40      8
434     18      1       58      35      43      8
435     17      1       60      34      44      8
436     16      1       59      37      47      9
437     16      1       57      38      48      10
438     15      1       55      41      48      10
439     15      1       53      41      49      10
440     16      1       51      41      51      9
441     16      1       52      41      52      10
442     16      1       50      44      49      11
443     16      1       49      44      50      11
444     12      1       48      44      50      10
445     12      1       46      45      51      10
446     12      1       44      46      51      10
447     12      3       43      43      49      10
448     12      3       43      40      48      10
449     12      3       43      41      48      10
450     12      3       42      40      47      10
451     10      3       38      40      46      10
452     10      3       36      41      46      10
453     10      3       36      41      45      10
454     10      3       37      41      43      9
455     9       3       33      41      43      8
456     8       3       32      42      43      8
457     7       3       32      43      41      8
458     6       3       33      42      37      8
459     6       3       33      42      37      8
460     6       3       30      42      35      8
461     4       3       29      42      33      8
462     4       3       28      41      32      8
463     4       3       26      42      29      7
464     4       3       25      42      26      8
465     4       3       24      41      23      8
466     4       3       23      42      21      8
467     4       3       23      42      21      8
468     4       3       23      41      22      7
469     4       3       23      41      22      7
470     3       3       23      38      21      7
471     3       3       23      37      22      7
472     3       3       22      36      21      8
473     3       3       21      36      21      8
474     3       3       20      34      20      8
475     3       3       19      31      20      9
476     3       3       18      30      20      9
477     3       3       18      30      20      9
478     3       3       17      28      20      9
479     3       3       16      28      21      11
480     3       3       15      28      23      12
481     3       3       12      28      23      11
482     3       27      11      28      23      11
483     3       36      11      28      23      10
484     3       52      11      28      23      10
485     3       69      7       30      24      10
486     2       86      7       31      24      8
487     2       98      7       31      24      8
488     2       102     7       31      23      7
489     2       106     8       32      24      6
490     1       110     8       32      24      6
491     1       112     8       33      24      6
492     1       115     7       32      22      6
493     1       119     7       31      22      5
494     1       125     7       32      22      5
495     1       128     7       32      22      6
496     1       138     6       32      22      6
497     1       144     5       32      24      6
498     1       145     5       30      24      6
499     1       147     5       25      23      6
500     1       151     4       25      23      6
501     0       165     4       25      23      6
502     0       172     4       25      22      6
503     0       175     3       25      22      6
504     0       178     3       24      21      6
505     0       181     3       21      22      6
506     0       182     3       21      22      6
507     1       182     3       22      21      6
508     1       182     3       21      21      6
509     1       182     3       20      22      6
510     1       184     3       21      22      5
511     1       184     2       20      22      4
512     1       186     2       19      22      4
513     1       188     2       19      20      4
514     1       189     2       17      19      4
515     1       192     2       17      20      4
516     1       197     2       17      20      5
517     1       202     2       16      20      6
518     1       204     2       15      20      6
519     1       210     2       15      20      6
520     1       210     2       15      20      6
521     1       209     2       15      20      7
522     1       209     2       15      20      6
523     1       210     1       14      20      6
524     1       209     1       14      18      6
525     0       210     1       11      18      6
526     0       212     1       10      17      8
527     0       213     1       10      16      9
528     0       214     1       10      16      9
529     0       214     0       10      15      9
530     0       211     0       10      21      10
531     0       211     0       11      21      10
532     0       211     0       10      19      10
533     0       210     0       11      19      10
534     0       208     0       11      20      10
535     0       206     0       14      20      10
536     0       204     0       14      20      10
537     0       199     0       13      20      10
538     0       198     0       13      20      10
539     0       195     0       13      20      10
540     0       189     0       13      20      10
541     0       189     0       13      20      10
542     0       182     0       13      20      11
543     0       176     0       14      20      9
544     0       170     0       13      18      9
545     0       169     0       13      18      9
546     0       167     0       13      18      9
547     0       167     0       13      18      10
548     0       165     0       13      18      10
549     0       162     0       14      18      10
550     0       159     0       14      19      10
551     0       159     0       14      18      10
552     0       159     0       14      18      10
553     0       155     0       15      18      10
554     0       148     0       14      18      10
555     0       137     0       14      18      10
556     0       126     0       14      11      10
557     0       118     0       13      11      10
558     0       106     0       13      11      10
559     0       97      0       13      10      10
560     0       95      0       13      8       11
561     0       91      0       14      9       11
562     0       90      0       14      9       12
563     0       88      1       12      9       12
564     0       87      1       12      9       12
565     0       86      1       12      9       14
566     0       84      1       12      9       13
567     0       81      1       12      9       13
568     0       76      1       11      9       13
569     0       76      1       11      8       13
570     0       74      1       12      8       12
571     0       69      3       12      8       13
572     0       64      3       10      8       12
573     0       61      3       10      8       13
574     0       57      3       12      8       13
575     0       52      3       12      8       13
576     0       47      4       14      7       12
577     0       45      4       14      4       11
578     1       44      4       14      4       11
579     1       41      4       14      4       11
580     1       40      4       14      4       10
581     1       40      4       14      4       10
582     1       39      4       14      4       10
583     1       40      4       14      3       11
584     1       39      5       14      3       12
585     1       40      5       14      3       11
586     1       40      5       15      2       11
587     1       40      5       16      1       11
588     1       39      6       16      0       11
589     1       39      7       13      0       11
590     1       38      7       13      0       11
591     1       37      7       14      0       11
592     1       37      8       14      0       11
593     1       37      8       14      0       11
594     1       37      8       14      0       11
595     1       35      8       14      0       11
596     1       35      9       13      0       13
597     1       33      10      14      0       13
598     1       32      10      14      0       13
599     1       32      10      14      0       15
600     1       31      10      14      0       14
601     1       30      10      15      0       14
602     1       30      10      15      0       14
603     1       30      11      16      0       15
604     1       30      11      16      0       16
605     1       30      11      15      0       17
606     1       30      11      15      0       20
607     1       30      11      14      1       20
608     1       30      11      14      1       20
609     1       30      11      15      1       20
610     1       28      12      15      1       22
611     2       28      12      15      1       22
612     2       28      12      16      1       22
613     2       28      11      16      1       22
614     2       28      11      16      1       22
615     2       27      11      16      1       21
616     2       27      11      16      1       20
617     2       27      11      16      1       20
618     2       26      11      16      1       20
619     1       26      11      16      1       20
620     1       26      12      16      1       20
621     1       21      12      16      1       20
622     1       19      13      14      1       18
623     1       3       12      15      1       18
624     2       2       15      14      1       18
625     2       2       16      14      1       18
626     2       2       17      14      2       17
627     1       2       19      14      2       17
628     1       2       18      14      2       17
629     1       2       18      14      2       18
630     1       2       18      14      3       18
631     1       2       18      14      3       18
632     1       3       18      13      4       16
633     1       3       17      12      5       16
634     1       3       16      10      5       14
635     1       3       16      10      5       14
636     1       3       16      10      5       11
637     1       3       16      10      5       11
638     1       3       16      10      5       10
639     1       3       16      10      5       10
640     1       3       15      10      5       9
641     1       3       14      9       5       7
642     1       3       14      12      5       7
643     1       3       13      12      5       7
644     1       3       12      12      5       6
645     1       3       12      11      5       5
646     1       3       12      10      5       5
647     1       3       10      10      5       5
648     1       3       10      9       4       3
649     1       3       8       9       4       3
650     1       3       8       9       3       3
651     1       3       8       7       3       2
652     1       3       8       7       3       1
653     1       3       7       7       2       1
654     1       3       5       7       2       1
655     1       3       5       7       2       1
656     1       2       5       7       2       1
657     1       2       1       7       2       0
658     1       2       1       7       1       0
659     1       2       1       6       1       0
660     1       2       1       6       1       0
661     1       0       0       6       0       0
662     0       0       0       6       0       0
663     0       0       0       6       0       0
664     0       0       0       5       0       0
665     0       0       0       5       0       0
666     0       0       0       4       0       0
667     0       0       0       4       0       0
668     0       0       0       4       0       0
669     0       0       0       4       0       0
670     0       0       0       3       1       0
671     0       0       0       3       1       0
672     0       0       0       3       1       0
673     0       0       0       3       1       0
674     0       0       0       3       1       0
675     0       0       0       3       1       0
676     0       0       0       3       1       0
677     0       0       0       2       1       0
678     0       0       0       2       1       0
679     0       0       1       1       1       0
680     0       0       1       1       1       0
681     0       0       1       1       1       0
682     0       0       1       1       1       0
683     0       0       1       1       1       0
684     0       0       1       1       1       0
685     0       0       1       1       1       0
686     0       0       1       2       1       0
687     0       0       1       1       1       0
688     0       0       1       1       1       0
689     0       0       1       1       1       0
690     0       0       1       1       1       0
691     0       0       1       1       1       0
692     0       0       1       1       3       0
693     0       0       1       1       3       0
694     0       0       1       1       3       0
695     0       0       1       1       3       0
696     0       0       1       1       3       0
697     0       0       1       1       3       0
698     0       0       1       1       3       0
699     0       0       2       1       3       0
700     0       0       2       1       3       0
701     0       0       2       1       3       0
702     0       0       2       1       3       0
703     0       0       2       1       3       0
704     0       1       2       1       3       0
705     0       1       2       1       3       0
706     0       1       2       1       3       0
707     0       1       2       1       3       0
708     0       1       7       1       3       0
709     0       1       9       1       3       0
710     0       1       10      1       3       0
711     0       1       12      1       3       0
712     0       1       16      1       3       0
713     0       1       16      2       3       0
714     0       1       16      2       3       0
715     0       1       16      2       3       0
716     0       1       17      2       3       0
717     0       1       18      3       3       0
718     0       1       18      3       3       0
719     0       1       18      3       3       0
720     0       1       18      3       3       0
721     0       1       18      3       3       0
722     0       1       18      3       3       0
723     0       1       18      3       1       0
724     0       1       18      3       0       0
725     0       1       16      3       0       0
726     0       1       9       3       0       0
727     0       1       8       3       0       0
728     0       1       5       3       0       0
729     0       1       5       3       0       0
730     0       1       5       3       0       0
731     0       1       5       3       0       0
732     0       1       5       2       0       0
733     0       1       5       3       0       0
734     0       1       5       3       0       0
735     0       1       4       3       0       0
736     0       1       5       3       0       0
737     0       1       5       3       0       0
738     0       1       5       3       0       1
739     0       1       5       3       0       1
740     0       0       5       3       0       1
741     0       0       5       3       0       1
742     0       0       5       3       0       1
743     0       0       7       3       0       1
744     0       0       7       3       0       1
745     0       0       7       3       0       1
746     0       0       7       3       0       1
747     0       0       7       2       0       1
748     0       0       7       2       0       2
749     1       0       7       2       0       2
750     1       0       7       2       0       2
751     1       0       7       2       0       3
752     1       0       7       2       0       4
753     1       0       7       2       0       4
754     1       0       7       1       0       5
755     1       0       7       1       0       5
756     1       0       6       1       0       5
757     1       0       6       1       0       5
758     1       0       6       1       0       6
759     1       0       7       1       0       6
760     1       0       7       1       0       6
761     1       0       9       2       0       6
762     2       0       11      2       0       6
763     2       0       11      2       0       6
764     2       0       11      2       0       7
765     2       0       11      3       0       7
766     2       0       11      3       0       7
767     2       0       11      4       0       7
768     2       0       11      4       1       7
769     2       0       11      4       1       8
770     2       0       11      4       1       8
771     2       0       11      4       1       8
772     2       0       11      4       1       8
773     2       0       10      4       1       8
774     2       0       9       4       1       8
775     2       0       9       5       1       8
776     2       0       9       5       1       9
777     3       0       9       5       1       10
778     3       0       9       5       1       10
779     3       0       9       4       1       10
780     3       0       9       4       1       10
781     3       0       9       4       1       10
782     3       0       8       4       1       10
783     3       0       8       4       1       10
784     3       0       8       4       2       11
785     3       0       8       4       2       11
786     3       0       7       4       2       11
787     3       0       6       4       2       11
788     3       0       6       4       2       11
789     3       0       6       4       2       11
790     3       0       6       5       2       11
791     3       0       6       5       2       11
792     3       0       6       5       2       11
793     2       0       6       5       2       11
794     2       0       6       5       2       11
795     2       0       6       5       2       10
796     2       0       6       5       2       10
797     2       0       6       5       2       10
798     2       0       4       5       2       9
799     2       0       4       6       2       9
800     3       0       4       7       2       9
801     3       0       4       7       2       8
802     3       0       3       7       2       8
803     3       0       2       6       2       9
804     3       0       2       6       2       9
805     3       0       2       6       2       9
806     3       0       1       6       5       8
807     3       0       0       6       5       8
808     3       0       0       6       6       9
809     3       0       0       6       6       9
810     3       0       0       6       6       9
811     3       0       0       6       6       9
812     3       0       0       6       6       9
813     3       0       0       6       7       9
814     3       0       0       6       9       9
815     3       0       0       6       9       9
816     2       0       0       6       9       9
817     2       0       0       6       10      9
818     3       0       0       6       11      8
819     3       0       0       7       11      8
820     3       0       0       7       11      8
821     3       0       0       7       13      8
822     3       0       0       7       13      8
823     3       0       0       6       13      8
824     3       0       0       6       13      5
825     3       0       0       6       13      5
826     3       0       0       7       12      4
827     3       0       0       7       12      4
828     3       0       0       7       12      4
829     3       0       0       7       12      4
830     3       0       0       7       12      4
831     3       0       0       6       12      3
832     4       0       0       6       12      3
833     4       0       0       6       12      3
834     4       0       0       6       12      3
835     4       0       0       6       12      3
836     4       1       0       7       11      3
837     4       1       0       7       12      3
838     4       1       0       7       12      3
839     4       1       0       7       12      3
840     4       1       0       7       12      3
841     4       1       0       7       13      2
842     4       1       0       7       14      2
843     4       1       0       7       14      2
844     4       1       0       7       13      2
845     4       1       0       7       13      1
846     4       1       0       7       13      1
847     4       1       0       7       13      1
848     5       1       0       7       13      1
849     5       1       0       7       12      1
850     5       1       0       6       12      1
851     5       1       0       6       13      1
852     5       1       0       6       13      1
853     6       1       0       6       13      1
854     8       1       0       5       13      1
855     8       1       0       5       13      1
856     8       1       0       5       12      1
857     9       1       0       5       12      1
858     10      1       0       5       12      0
859     11      1       0       4       12      0
860     23      1       0       4       12      0
861     23      1       0       4       11      0
862     23      1       0       4       11      0
863     25      1       0       4       10      0
864     25      1       0       4       8       0
865     25      1       0       4       7       0
866     26      1       0       4       7       0
867     27      1       0       4       6       0
868     26      1       0       4       6       0
869     28      1       0       4       7       0
870     28      1       0       4       7       0
871     28      1       0       4       7       0
872     29      1       0       4       7       0
873     29      1       0       5       6       0
874     29      1       0       5       6       0
875     30      1       0       5       6       1
876     30      1       0       5       6       1
877     30      1       0       5       6       1
878     30      1       0       5       6       2
879     30      1       0       5       6       3
880     30      1       0       5       6       4
881     30      1       0       5       6       4
882     30      1       0       6       6       4
883     30      1       1       7       6       5
884     30      1       2       7       7       5
885     30      1       2       7       7       5
886     30      1       2       7       8       8
887     16      1       3       7       8       8
888     18      1       3       7       9       8
889     19      1       3       7       9       8
890     18      1       3       7       9       8
891     19      1       3       7       9       8
892     20      1       3       7       9       8
893     20      1       3       7       10      8
894     19      1       3       7       10      8
895     19      1       3       7       10      8
896     19      1       3       7       10      8
897     19      1       3       7       10      8
898     19      1       4       8       10      8
899     18      1       4       8       9       8
900     17      1       4       8       9       8
901     17      1       4       9       9       10
902     16      1       4       10      9       10
903     17      1       4       11      9       10
904     17      1       4       11      9       10
905     18      1       4       11      9       10
906     18      1       4       11      9       10
907     18      1       4       17      8       10
908     18      1       5       17      8       10
909     18      1       6       17      8       10
910     18      1       6       17      6       10
911     20      0       6       17      7       10
912     20      0       6       18      8       10
913     20      0       6       19      8       10
914     21      0       6       19      8       10
915     21      0       7       19      7       8
916     21      0       7       20      7       8
917     22      0       7       22      7       8
918     22      0       7       22      7       8
919     21      0       7       22      7       8
920     21      0       7       23      7       7
921     18      0       7       24      8       7
922     18      0       5       26      9       7
923     19      0       5       25      9       7
924     18      0       5       25      8       7
925     18      0       5       26      8       7
926     17      0       5       25      8       7
927     15      0       5       24      8       6
928     16      0       5       24      8       6
929     15      0       5       23      8       6
930     14      0       5       23      8       6
931     14      0       6       23      8       6
932     14      0       5       24      8       6
933     14      0       5       24      8       3
934     14      0       5       23      8       2
935     14      0       5       23      8       2
936     13      0       5       23      9       2
937     14      0       5       24      9       2
938     14      0       5       23      9       2
939     15      0       5       23      9       1
940     16      0       5       23      9       0
941     15      0       5       23      9       0
942     15      0       5       24      9       0
943     15      0       5       20      9       0
944     14      0       5       20      9       0
945     14      0       5       18      9       0
946     14      0       5       17      9       0
947     14      0       5       17      9       0
948     14      0       5       18      9       0
949     14      0       5       18      8       0
950     15      0       4       17      8       0
951     15      0       4       17      8       0
952     15      0       4       17      9       0
953     15      0       4       17      9       0
954     15      0       4       16      8       0
955     15      0       4       17      8       0
956     15      0       5       16      8       1
957     13      0       6       17      7       2
958     13      0       6       19      7       2
959     13      0       6       19      5       4
960     13      0       6       19      5       4
961     13      0       6       19      5       6
962     13      0       6       19      5       7
963     13      0       6       20      5       7
964     12      0       6       20      5       7
965     12      0       6       19      5       7
966     12      0       7       19      4       7
967     11      0       7       19      4       7
968     10      0       7       19      4       7
969     10      0       6       18      4       7
970     10      0       9       19      4       7
971     10      0       9       18      4       7
972     10      0       9       17      3       7
973     10      0       9       17      3       7
974     10      0       9       17      3       9
975     9       0       9       17      3       10
976     9       0       9       16      3       10
977     9       0       9       15      3       10
978     8       0       9       15      3       10
979     8       0       9       15      3       10
980     8       0       9       15      3       10
981     8       0       9       15      3       10
982     8       0       9       15      3       11
983     6       0       9       14      3       11
984     6       0       9       12      3       12
985     6       0       9       12      3       12
986     6       0       9       11      3       12
987     6       0       9       10      3       14
988     4       0       8       10      2       14
989     4       0       7       11      2       14
990     4       0       7       12      2       14
991     4       0       6       12      2       14
992     4       0       6       12      1       14
993     4       0       6       12      0       14
994     4       0       6       11      0       14
995     2       0       6       10      0       14
996     2       0       6       9       0       14
997     2       0       6       9       0       14
998     2       0       6       9       0       14
999     1       0       6       9       0       14
1000    1       0       6       9       0       14
1001    1       0       7       9       0       14
1002    1       0       7       9       0       14
1003    1       0       7       8       0       14
1004    1       0       7       8       0       14
1005    0       0       5       8       0       13
1006    0       0       5       9       0       13
1007    0       0       5       9       0       13
1008    0       0       5       7       0       14
1009    0       0       5       7       0       15
1010    0       0       5       7       0       16
1011    0       0       5       7       0       15
1012    0       0       5       7       0       16
1013    0       0       5       6       0       14
1014    0       0       5       4       0       14
1015    0       0       5       4       0       15
1016    0       0       4       4       0       15
1017    0       0       4       4       0       15
1018    0       0       4       4       0       15
1019    0       0       4       5       0       16
1020    0       0       4       5       0       15
1021    0       0       4       5       0       15
1022    0       0       4       5       0       14
1023    0       0       4       5       0       14
1024    1       0       4       5       0       14
1025    1       0       4       5       0       14
1026    1       0       4       5       0       13
1027    1       0       4       5       0       13
1028    1       0       4       5       0       12
1029    1       0       4       5       0       12
1030    1       0       4       6       0       13
1031    1       0       4       6       0       13
1032    1       0       4       6       0       13
1033    1       0       4       6       0       13
1034    1       0       5       6       0       13
1035    1       0       5       6       0       12
1036    1       0       5       6       0       12
1037    1       0       5       6       0       12
1038    1       0       5       6       0       12
1039    1       0       5       6       0       11
1040    1       0       5       6       0       11
1041    1       0       5       5       0       11
1042    2       0       5       5       0       11
1043    2       0       5       5       0       11
1044    2       0       5       4       0       9
1045    2       0       5       4       0       9
1046    2       0       5       4       0       10
1047    2       0       5       5       0       12
1048    2       0       5       5       0       12
1049    2       0       5       5       0       12
1050    3       0       5       5       0       11
1051    3       0       5       5       0       11
1052    3       0       5       5       0       12
1053    3       0       5       5       0       14
1054    3       0       6       5       0       15
1055    3       0       6       5       0       15
1056    3       0       6       5       0       16
1057    3       0       6       5       0       16
1058    8       0       6       5       0       16
1059    9       0       5       4       0       16
1060    9       0       5       4       0       16
1061    9       0       5       4       0       16
1062    11      0       5       4       0       16
1063    11      0       6       5       1       15
1064    14      0       6       7       1       15
1065    15      0       6       8       2       16
1066    16      0       6       8       2       16
1067    16      0       6       8       2       16
1068    16      0       6       8       2       15
1069    16      0       6       8       2       15
1070    17      0       6       8       3       14
1071    17      0       6       8       3       13
1072    17      0       5       8       3       13
1073    17      0       5       8       3       13
1074    17      0       7       8       3       13
1075    17      0       7       8       3       13
1076    17      0       7       8       3       13
1077    17      0       7       7       3       13
1078    17      0       7       7       3       12
1079    17      0       6       7       3       12
1080    17      0       7       7       5       12
1081    17      0       6       7       5       11
1082    17      0       6       7       5       11
1083    17      0       6       7       5       11
1084    17      0       6       7       5       11
1085    17      0       6       7       5       11
1086    16      0       6       7       5       10
1087    16      0       6       8       6       10
1088    15      0       6       9       6       9
1089    14      0       6       9       6       7
1090    14      0       6       9       6       7
1091    14      0       6       9       6       6
1092    14      0       5       9       6       6
1093    14      0       5       9       6       6
1094    13      0       4       10      6       5
1095    13      0       4       10      6       4
1096    12      0       4       10      6       4
1097    12      0       4       11      6       3
1098    12      0       4       11      5       3
1099    12      0       4       12      4       3
1100    11      0       4       12      4       2
1101    11      0       4       13      4       0
1102    8       0       4       14      3       0
1103    8       0       4       13      3       0
1104    8       0       4       13      4       0
1105    3       0       4       13      4       0
1106    0       0       4       12      4       0
1107    0       0       4       12      4       0
1108    0       0       3       12      4       0
1109    0       0       3       14      4       0
1110    0       0       2       14      4       0
1111    0       0       2       14      4       0
1112    0       0       2       14      4       0
1113    0       0       2       14      5       0
1114    0       0       2       14      7       0
1115    0       0       2       14      7       0
1116    0       0       2       14      7       0
1117    0       0       2       14      7       0
1118    1       0       2       14      7       0
1119    1       0       2       14      7       0
1120    2       0       2       14      7       0
1121    3       0       2       14      7       0
1122    3       0       2       13      7       0
1123    3       0       2       13      7       0
1124    3       0       2       13      7       0
1125    3       0       2       12      8       0
1126    3       0       2       12      8       0
1127    3       0       2       12      9       0
1128    3       0       2       12      9       0
1129    4       0       2       12      9       0
1130    4       0       2       11      9       0
1131    4       0       2       11      9       0
1132    4       0       2       11      9       0
1133    5       0       2       8       9       0
1134    7       0       2       8       8       0
1135    8       0       2       8       8       0
1136    8       0       2       8       8       0
1137    8       0       2       7       8       0
1138    8       0       2       7       7       0
1139    9       0       2       4       8       0
1140    9       0       2       4       8       0
1141    10      0       2       4       8       0
1142    10      0       2       4       8       0
1143    10      0       2       4       8       0
1144    10      0       1       1       7       0
1145    11      0       1       1       8       0
1146    11      0       1       1       8       0
1147    10      0       0       0       8       0
1148    10      0       0       0       8       0
1149    10      0       0       0       8       0
1150    10      0       0       0       8       0
1151    10      0       0       0       9       0
1152    10      0       0       0       9       0
1153    10      0       0       0       9       0
1154    10      0       0       0       9       0
1155    10      0       0       0       9       0
1156    10      0       0       0       9       0
1157    10      0       0       0       9       0
1158    10      0       0       0       9       0
1159    10      0       0       0       9       0
1160    9       0       0       0       9       0
1161    9       0       0       0       9       0
1162    8       0       0       0       9       0
1163    7       0       0       0       9       0
1164    5       0       0       0       8       0
1165    5       0       0       0       8       0
1166    5       0       0       0       8       0
1167    5       0       0       0       8       0
1168    4       0       0       0       7       0
1169    3       0       0       0       7       0
1170    3       0       0       0       7       0
1171    3       0       0       0       7       0
1172    3       0       0       0       7       0
1173    3       0       0       0       6       0
1174    2       0       0       0       6       0
1175    2       0       0       0       6       0
1176    1       0       0       0       6       0
1177    1       0       0       0       4       0
1178    1       0       0       0       3       0
1179    1       0       0       0       3       0
1180    1       0       0       0       3       0
1181    0       0       0       0       3       0
1182    0       0       0       0       3       0
1183    0       0       0       0       3       0
1184    0       0       0       0       3       0
1185    0       0       0       0       3       0
1186    0       0       0       0       3       0
1187    0       0       0       0       3       0
1188    0       0       0       0       2       0
1189    0       0       0       0       2       0
1190    0       0       0       0       2       0
1191    0       0       0       0       2       0
1192    0       0       0       0       2       0
1193    0       0       0       0       2       0
1194    0       0       0       0       2       0
1195    0       0       0       0       1       0
1196    0       0       0       0       1       0
1197    0       0       0       0       0       0
1198    0       0       0       0       0       0
1199    0       0       0       0       0       0
1200    0       0       0       0       0       0
1201    0       0       0       0       0       0
1202    0       0       0       0       0       0
1203    0       0       0       0       0       0
1204    0       0       0       0       0       0
1205    0       0       0       0       0       0
1206    0       0       0       0       0       0
1207    0       0       0       0       0       0
1208    0       0       0       0       0       0
1209    0       0       0       0       0       0
1210    0       0       0       0       0       0
1211    0       0       0       0       0       0
1212    0       0       0       0       0       0
1213    0       0       0       0       0       0
1214    0       0       0       0       0       0
1215    0       0       0       0       0       0
1216    0       0       0       1       0       0
1217    0       1       0       1       0       0
1218    0       1       0       1       0       0
1219    0       1       0       1       0       0
1220    0       1       0       1       0       0
1221    0       1       0       1       0       0
1222    0       1       0       1       0       0
1223    0       1       0       1       0       0
1224    0       1       0       1       0       0
1225    0       1       0       1       0       0
1226    0       1       0       1       0       0
1227    0       1       0       1       0       0
1228    0       1       0       1       0       0
1229    1       1       0       1       0       0
1230    1       1       0       1       0       0
1231    1       1       0       1       0       0
1232    1       1       0       1       0       0
1233    1       1       0       1       0       0
1234    2       1       0       1       0       0
1235    2       1       0       1       0       0
1236    2       1       0       1       0       0
1237    2       1       0       1       0       0
1238    2       1       0       1       0       0
1239    2       1       0       1       0       0
1240    2       1       0       1       0       0
1241    2       1       0       1       0       0
1242    2       1       0       1       0       0
1243    2       1       0       1       0       0
1244    2       1       0       1       0       0
1245    2       1       0       1       0       0
1246    2       1       0       1       0       0
1247    2       1       0       1       0       0
1248    2       1       0       1       0       0
1249    2       1       0       1       0       0
1250    2       1       0       1       0       0
1251    1       1       0       1       0       0
1252    1       1       0       1       0       0
1253    1       1       0       1       0       0
1254    1       1       0       0       0       0
1255    1       1       0       0       0       0
1256    1       1       0       0       0       0
1257    1       1       1       0       0       0
1258    1       1       1       0       0       0
1259    1       1       1       0       0       0
1260    1       1       1       0       0       0
1261    1       1       1       0       0       0
1262    1       1       1       0       0       0
1263    1       1       1       0       0       0
1264    1       1       1       0       0       0
1265    1       1       1       0       0       0
1266    1       1       1       1       0       1
1267    1       1       1       1       0       1
1268    1       1       1       1       1       1
1269    1       1       1       1       1       1
1270    1       1       1       1       1       1
1271    1       1       1       1       1       1
1272    1       1       1       1       1       1
1273    1       1       1       1       1       1
1274    1       0       1       1       1       1
1275    0       0       1       1       1       1
1276    0       0       1       1       1       1
1277    0       0       1       1       1       1
1278    0       0       1       1       1       1
1279    0       0       1       1       1       1
1280    0       0       1       1       1       1
1281    0       0       1       1       1       1
1282    0       0       1       1       1       2
1283    0       0       1       1       1       2
1284    0       0       1       1       1       2
1285    0       0       1       1       0       2
1286    0       0       1       1       0       2
1287    0       0       1       1       0       2
1288    0       0       1       1       0       2
1289    0       0       1       1       0       2
1290    0       0       1       1       0       2
1291    0       0       1       1       0       2
1292    0       0       1       0       0       2
1293    0       0       1       0       0       2
1294    0       0       1       0       0       2
1295    0       0       1       0       0       2
1296    0       0       1       0       0       1
1297    0       0       1       0       0       1
1298    1       0       1       0       0       1
1299    1       0       1       0       0       1
1300    1       0       0       0       0       1
1301    1       0       0       0       0       1
1302    2       0       0       0       0       1
1303    2       0       0       0       0       1
1304    2       0       0       0       0       1
1305    2       0       0       0       0       1
1306    2       0       0       0       0       1
1307    2       0       0       0       0       1
1308    2       0       0       0       0       1
1309    2       0       0       0       0       2
1310    2       0       0       0       0       2
1311    2       0       0       0       0       2
1312    2       0       0       0       0       2
1313    2       0       0       1       0       2
1314    3       0       0       1       2       2
1315    3       0       0       1       2       2
1316    3       0       0       1       2       2
1317    3       0       0       1       2       2
1318    3       0       0       1       2       2
1319    3       0       0       1       4       2
1320    4       0       0       1       4       2
1321    4       0       0       1       4       2
1322    4       0       0       1       5       2
1323    4       0       0       1       5       2
1324    4       0       0       2       5       2
1325    4       0       0       2       5       2
1326    4       0       0       2       5       3
1327    4       0       0       2       6       3
1328    4       0       0       2       6       3
1329    4       0       0       2       6       4
1330    3       0       0       2       6       4
1331    3       0       0       3       6       4
1332    3       0       0       3       6       4
1333    2       0       0       3       6       4
1334    2       0       0       3       7       4
1335    2       0       1       3       8       4
1336    2       0       1       4       8       4
1337    2       0       1       4       8       4
1338    2       0       1       4       8       4
1339    2       0       1       4       8       4
1340    2       0       1       4       9       4
1341    2       0       1       4       9       4
1342    2       0       1       4       9       4
1343    1       0       1       4       9       4
1344    0       0       1       4       9       4
1345    0       0       1       4       10      4
1346    0       0       1       4       10      4
1347    0       0       1       4       10      4
1348    0       0       1       4       10      4
1349    0       0       1       4       10      4
1350    0       0       1       5       10      4
1351    0       0       1       6       9       4
1352    0       0       1       7       9       4
1353    0       0       1       7       9       4
1354    0       0       0       7       9       4
1355    0       1       0       7       9       4
1356    0       1       0       7       9       4
1357    0       1       0       7       8       4
1358    0       1       0       7       7       4
1359    0       1       0       8       7       4
1360    1       1       0       8       7       4
1361    1       1       0       8       7       4
1362    2       1       0       9       6       4
1363    2       1       0       9       6       4
1364    2       1       0       9       6       4
1365    2       1       0       9       6       6
1366    2       1       0       9       6       7
1367    2       1       0       9       6       7
1368    2       1       0       9       6       7
1369    2       1       0       9       6       7
1370    2       1       0       9       6       7
1371    4       1       0       8       6       7
1372    4       1       0       8       6       7
1373    4       1       0       8       6       7
1374    5       1       0       8       6       8
1375    4       1       0       8       6       8
1376    4       1       0       7       6       8
1377    5       1       0       6       6       8
1378    5       1       0       5       5       8
1379    6       1       0       5       5       8
1380    6       1       0       5       5       9
1381    6       1       0       3       5       9
1382    8       1       0       3       5       9
1383    8       1       0       3       4       10
1384    8       1       0       2       3       10
1385    8       1       0       2       5       11
1386    8       1       0       2       5       11
1387    8       1       0       1       5       12
1388    8       1       0       1       5       12
1389    8       1       0       1       5       11
1390    9       1       0       1       5       11
1391    10      1       0       1       6       11
1392    10      1       0       1       6       11
1393    11      1       0       1       6       11
1394    11      1       0       1       6       10
1395    11      1       0       1       6       10
1396    11      1       0       1       6       10
1397    12      1       0       1       6       11
1398    12      1       0       1       6       11
1399    13      1       0       1       6       11
1400    12      1       0       1       6       12
1401    12      1       0       1       6       11
1402    12      1       0       1       6       11
1403    12      1       0       1       6       11
1404    12      1       0       1       6       11
1405    12      1       0       1       6       11
1406    13      1       0       1       6       12
1407    13      1       0       1       8       12
1408    13      1       0       1       8       12
1409    14      1       0       0       8       12
1410    17      1       0       0       8       12
1411    17      1       0       0       7       12
1412    18      1       0       0       7       12
1413    18      1       0       0       6       11
1414    18      0       0       0       6       10
1415    19      0       0       0       6       10
1416    19      0       0       0       6       10
1417    19      0       0       0       6       11
1418    19      0       0       0       6       11
1419    19      0       0       0       6       11
1420    19      0       0       0       6       11
1421    19      0       0       0       6       12
1422    20      0       0       0       6       12
1423    20      0       0       0       6       12
1424    20      0       0       0       5       12
1425    21      0       0       0       5       10
1426    21      0       0       0       5       10
1427    21      0       0       0       5       10
1428    22      0       0       0       4       10
1429    22      0       0       0       4       11
1430    22      0       0       0       4       11
1431    22      0       0       0       4       13
1432    21      0       0       0       4       13
1433    21      0       0       0       4       12
1434    20      0       0       0       4       12
1435    20      0       0       0       4       12
1436    20      0       0       0       4       12
1437    21      0       0       0       5       12
1438    22      0       0       0       5       12
1439    23      0       0       0       5       12
1440    23      0       0       0       5       12
1441    22      0       0       0       5       12
1442    22      0       0       0       5       12
1443    22      0       0       0       5       12
1444    21      0       0       0       4       12
1445    22      0       0       0       4       12
1446    24      0       0       0       4       12
1447    25      0       0       0       4       12
1448    25      0       0       0       4       13
1449    26      0       0       0       4       12
1450    26      0       0       0       3       11
1451    27      0       0       0       3       11
1452    27      0       0       0       3       11
1453    25      0       0       0       3       11
1454    25      0       0       0       3       11
1455    25      0       0       0       3       11
1456    25      0       0       0       3       11
1457    24      0       0       0       2       11
1458    24      0       0       0       2       10
1459    24      0       0       0       2       10
1460    20      0       0       0       2       10
1461    20      0       0       0       2       10
1462    20      0       0       0       2       10
1463    19      0       0       0       2       12
1464    19      0       0       0       2       10
1465    19      0       0       0       2       10
1466    19      0       0       0       2       10
1467    17      0       0       0       2       10
1468    17      0       0       0       2       10
1469    17      0       0       0       2       9
1470    17      0       0       0       2       9
1471    17      0       0       0       2       10
1472    17      0       0       0       2       10
1473    17      0       0       0       2       11
1474    19      0       0       0       2       12
1475    22      0       0       0       2       13
1476    22      0       0       0       1       13
1477    22      0       0       0       1       14
1478    23      0       0       0       1       14
1479    24      0       1       0       1       14
1480    26      0       1       0       1       14
1481    26      0       1       1       1       14
1482    28      0       1       1       1       14
1483    28      0       1       2       1       15
1484    28      0       1       3       1       14
1485    26      0       1       3       1       14
1486    25      0       1       3       1       15
1487    25      0       1       3       1       15
1488    25      0       2       3       1       15
1489    25      0       2       3       1       15
1490    25      0       2       5       1       15
1491    25      0       4       5       1       15
1492    24      0       4       5       1       15
1493    24      0       4       6       1       17
1494    24      0       4       7       1       17
1495    25      0       4       7       1       17
1496    24      0       4       7       1       17
1497    24      0       4       7       1       17
1498    24      0       5       7       1       15
1499    23      0       5       9       1       13
1500    21      0       6       10      1       13
1501    19      0       9       11      1       13
1502    19      0       9       11      1       15
1503    22      0       9       11      0       16
1504    22      0       9       11      0       16
1505    23      0       10      11      0       16
1506    24      0       10      12      0       17
1507    24      0       12      12      0       16
1508    25      0       12      12      0       16
1509    24      0       12      12      0       17
1510    23      0       12      12      0       19
1511    22      0       13      13      0       19
1512    21      0       13      13      0       19
1513    21      0       15      15      0       19
1514    20      0       15      15      0       20
1515    20      0       15      15      0       20
1516    19      0       15      15      0       20
1517    19      0       16      15      0       20
1518    19      0       17      15      0       20
1519    19      0       17      17      0       23
1520    19      0       17      17      1       25
1521    19      0       17      17      2       25
1522    16      0       19      17      2       26
1523    15      0       19      18      2       26
1524    15      0       19      18      2       24
1525    15      0       19      17      2       24
1526    15      0       19      17      2       24
1527    15      0       21      17      2       22
1528    14      0       21      17      2       20
1529    14      0       20      17      2       20
1530    15      0       19      17      3       20
1531    14      0       18      18      3       21
1532    14      0       18      18      5       21
1533    14      0       18      18      5       21
1534    15      0       20      18      5       21
1535    17      0       21      18      5       21
1536    17      0       24      18      5       21
1537    18      0       24      18      5       21
1538    17      0       23      17      5       21
1539    18      0       23      18      5       21
1540    18      0       23      18      5       21
1541    19      0       23      18      5       19
1542    19      0       23      18      5       19
1543    20      0       23      17      5       19
1544    20      0       23      17      5       19
1545    20      0       23      17      5       19
1546    19      0       23      17      5       19
1547    20      0       23      16      5       20
1548    20      0       23      16      5       20
1549    20      0       23      15      5       19
1550    20      0       23      14      5       19
1551    20      0       23      14      5       20
1552    20      0       23      15      4       21
1553    20      0       23      15      4       21
1554    19      0       23      15      4       21
1555    19      0       23      15      4       21
1556    18      0       23      15      5       20
1557    18      0       23      15      5       17
1558    16      0       22      15      5       17
1559    14      0       22      15      5       17
1560    13      0       21      15      5       15
1561    13      0       19      14      8       14
1562    12      0       19      14      9       14
1563    11      0       19      15      9       14
1564    11      0       20      15      9       15
1565    11      0       20      15      9       16
1566    11      0       20      14      8       16
1567    13      0       20      13      7       14
1568    13      0       18      13      7       14
1569    13      0       18      12      7       14
1570    12      0       18      12      7       14
1571    12      0       18      11      7       14
1572    11      0       18      10      7       14
1573    11      0       18      10      7       14
1574    11      0       19      10      7       13
1575    10      0       18      10      7       13
1576    10      0       18      10      7       13
1577    10      0       18      11      7       13
1578    10      0       18      11      7       12
1579    10      0       18      11      7       12
1580    10      0       18      10      7       10
1581    10      0       17      10      7       9
1582    10      0       16      10      7       9
1583    9       0       16      10      7       9
1584    8       0       16      10      7       9
1585    8       0       16      10      7       9
1586    8       0       15      10      6       8
1587    7       0       14      10      7       8
1588    6       0       14      10      8       7
1589    6       0       13      10      10      6
1590    6       0       13      9       10      5
1591    6       0       13      9       10      5
1592    6       0       11      9       10      5
1593    6       1       8       9       10      4
1594    5       1       8       8       10      4
1595    5       1       7       6       9       4
1596    5       1       7       6       9       4
1597    5       1       5       4       9       4
1598    5       1       5       4       9       3
1599    4       1       5       4       9       3
1600    3       1       4       4       9       2
1601    2       1       2       2       9       2
1602    2       1       2       2       9       2
1603    2       1       2       2       9       2
1604    2       1       2       0       9       1
1605    2       1       2       0       7       0
1606    0       1       2       0       7       0
1607    0       1       1       0       7       0
1608    0       1       0       0       7       0
1609    0       1       0       0       7       0
1610    0       1       0       0       7       0
1611    0       1       0       0       7       0
1612    0       1       0       0       7       0
1613    0       1       0       0       7       0
1614    0       1       0       0       6       0
1615    0       1       0       0       5       0
1616    0       1       0       0       5       0
1617    0       1       0       0       5       0
1618    0       1       0       0       5       0
1619    0       1       0       0       3       0
1620    0       1       0       0       3       0
1621    0       1       0       0       0       0
1622    0       0       0       0       0       0
1623    0       0       0       0       0       0
1624    0       0       0       0       0       0
1625    0       0       0       0       0       0
1626    0       0       0       0       0       0
1627    0       0       0       0       0       0
1628    0       0       0       0       0       0
1629    0       0       0       0       0       0
1630    0       0       0       0       0       0
1631    0       0       0       0       0       0
1632    0       0       0       0       0       0
1633    0       0       0       0       0       0
Coloreado en 0.005 segundos, usando GeSHi 1.0.8.4


Código que llevo (le he incluido un umbral, para que sólo tome picos cuyos 'valores > 10' (en realidad, Z-score significativo) sean al menos 30 ($W) consecutivos:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1.   # ...
  2.   # Each phase
  3.   foreach (my $ph = 1; $ph <= 6; $ph++) {
  4.     my @list = @{$profile[$ph]};
  5.  
  6.     # Búsqueda de picos
  7.     my $posiciones = Range::Object::Serial->new();
  8.     for my $pos (0 .. $#list) {
  9.       my $z = ($list[$pos] - $M{"TOTAL_-"}) / $D{"TOTAL_-"};
  10.       $posiciones->add($pos)         # añadimos un valor de posición de pico encontrada
  11.         if $z >= $T;
  12.     }
  13.     #print "Picos encontrados: [", $posiciones->stringify_collapsed, "] - $ph\n";
  14.  
  15.     # 1 - Simplificación: quitar los picos que están aislados
  16.     my @picos = grep { /-/ } split /,/, $posiciones->stringify_collapsed;
  17.    
  18.     next unless (@picos); # phase without peaks
  19.     $posiciones = Range::Object::Serial->new( join ',', @picos );
  20.  
  21.     # 2 - Arreglo: volvemos a añadir los picos que están en los extremos
  22.     for my $pos (0, $#list) {
  23.       my $z = ($list[$pos] - $M{"TOTAL_-"}) / $D{"TOTAL_-"};
  24.       $posiciones->add($pos)
  25.         if $z >= $T;
  26.     }
  27.  
  28.     # 3 - Ampliación de la base de cada pico
  29.     my @posiciones_finales;
  30.     for my $zona_ref ($posiciones->collapsed) {
  31.  
  32.       my($limite_bajo, $limite_alto)
  33.         = (ref $zona_ref)               # la zona puede ser una referencia o no
  34.         ? @$zona_ref{'start','end'}     # caso de zona normal
  35.         : ($zona_ref, $zona_ref)        # caso de pico solitario
  36.         ;
  37.      
  38.       my $length_w = $limite_alto - $limite_bajo + 1;
  39.       next unless ($length_w >= $W);                       # significant window minimal length
  40.       $limite_bajo = final_pico($limite_bajo, -1, \@list); # buscamos la base, por la izquierda
  41.       $limite_alto = final_pico($limite_alto,  1, \@list); # buscamos la base, por la derecha
  42.  
  43.       push @posiciones_finales, "$limite_bajo-$limite_alto";
  44.     }
  45.  
  46.     # Informar
  47.     for my $pico (@posiciones_finales) {
  48.         #print "Pico en [$pico] $ph\n";
  49.         my ($pico1, $pico2) = split /-/, $pico;
  50.         push @peaks, {ph=>$ph, p1=>$pico1, p2=>$pico2};
  51.     }    
  52.   }
  53.   # ...
  54.  
Coloreado en 0.003 segundos, usando GeSHi 1.0.8.4
ptahotep
Perlero nuevo
Perlero nuevo
 
Mensajes: 8
Registrado: 2013-07-26 13:21 @598

Re: Búsqueda de picos significativos

Notapor explorer » 2013-07-29 09:31 @438

ptahotep escribiste:Desde luego, te pondré en los créditos del trabajo, si se llega a publicar en el futuro.
Pues... te agradecería que cuando eso ocurra, me mandases alguna copia o referencia del trabajo, para adjuntarlo a mi currículo.

ptahotep escribiste:En realidad los número que tengo a veces suben y bajan significativamente en un mismo pico y querría considerar eso como el mismo pico. Así, picos cercanos (usando un umbral) los consideraría uno solo.
Una solución podría ser hacer un suaviazado de los datos, pero entonces, quizás sea más difícil calcular el umbral de corte.

ptahotep escribiste:De esta forma, obtendría picos más amplios.
En una primera solución que encontré, unía picos que compartían frontera o valor mínimo, pero lo deseché porque eliminaba muchos picos.

ptahotep escribiste:Código que llevo
Humm... sospecho que se puede reducir o simplificar algo más...

Por ejemplo: por cada elemento realizas el cálculo ($list[$pos] - $M{"TOTAL_-"}) / $D{"TOTAL_-"}. Se podría meter después de la línea 4, para no tener que hacerlo más que una sola vez, pero quizás eso afecte a la forma de trabajo de final_pico().

Otro: cambiar esta línea:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1.         push @posiciones_finales, [ $limite_bajo, $limite_alto ];
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4
y quedaría la línea 49 así:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1.         my ($pico1, $pico2) = @$pico;
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14486
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Siguiente

Volver a Bioinformática

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 0 invitados