Extra Points - Bioinformatics

Teoría de la Información y 

Métodos de Codificación

Para esta entrada se nos encargo el elegir un articulo acerca de aplicaciones de la Bioinformatica enfocados a los temas que hemos visto en las clases.

El elegido fue el siguiente:

Lossless Compression of DNA Microarray Images

Autores: Yong Zhang, Rahul Parthe, and Don Adjeroh

Dirección: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1540570

Microarray experiments are characterized by a massive amount of data, usually in the form of an image.

In the point 2 describe the special nature of microarray  images, and propose a component-based model for microarray images.

In the point 3 describes our proposed schemes for compressing microarray images.

Point 4 presents experimental results on compression using real microarray images.

Conclusions



Reference

Yong Zhang, Rahul Parthe, and Don Adjeroh, "Lossless Compression of DNA Microarray Images", IEEE Computational Systems Bioinformatics Conference Workshops, year 2005, Pages 1 - 5. [In line]. Date of Consult: 27 May 2013. Available: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1540570

Entrada # 6

Teoría de la Información Y 

Métodos de Codificación

 
Image Compressor

The process effected was as follows:

• Get an image .jpg what is asked the user.
• Convert this image a gray scale.
• It loads in an array one of variables rgb (As in each rgb the elements are equal, you take only one).
• Decomposes the array using the library wavedec2 of pywt, the result gives us three variables, the first 2 are used only to rebuild the array. The last is applied one process (this is the coefficient variable).
• Make new array of coefficient using the variable coefficient, sweep every element of the array and compares with the threshol, if data success the condition the value of the array is 0. All data (success the condition or not) save in the array.
• Add in the new list the 2 variable and the array and aplied the method waverec2 and get one array, this array can change to integer for continue. This array is used to create the new image.
• Sweep the array get every pixel of the image with your rgb (every element x 3) and create the new image.
• Compare the weight of the image in gray scale with the compress for obtain the compress percentage.

Code Used

Código

Make Test

We have the image:

Size 308 x 328

Aplied the Code

Image to gray scale:

Compress the image with threshold of 230. 

Test with different threshold:

Threshold 10

Threshold 159

As see in the images, while the threshold is high the quality of the image decreases so the compression become greater.

This can be rectify in the picture of below, which shows the result of the execution:

References

http://www.pybytes.com/pywavelets/ref/2d-dwt-and-idwt.html

Puntos Extra

Teoría de la Información y 

Métodos de Codificación

Puntos Extra

Reed-Solomon Code

Código cíclico no binario usado para la detección y corrección de errores, creado en el año de 1960 por Irving S. Reed y Gustave Solomon.

La corrección de errores a aplica a la información en el momento de la transmisión de datos sobre un canal de comunicaciones.

El funcionamiento del código es el siguiente:

Toma un bloque de datos digitales y le añade bits produciendo el encriptado. Se transmite la información y el decodificador de la red toma esta información y procesa cada bloque intentando corregir los errores y recuperar los datos originales.

Al momento de la transmisión puede haber errores esto se debe a ruido, daños en los dispositivos de almacenamiento o interferencia.

En esta liga pueden encontrar el este método codificado en Python:

https://pypi.python.org/pypi/reedsolo#downloads

Aplicaciones

Este código es utilizado en varias áreas las mas conocidas en los siguientes:

Dispositivos de Almacenamiento



En este la información se transmite a los dispositivos de almacenamiento, el codificador y decodificador esta en los dispositivos que leen estos.

Teléfonos Móviles

La codificación se hace en la llamada.

Comunicación por Satélite

Se hace en las señales que transmiten al satélite.

Televisión Digital



Se aplica igual que al anterior.

Módem de Alta Velocidad

Referencias

http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/reedsolomon/reed_solomon_codes.html
http://es.slideshare.net/bonnzai/reed-solomon-397239

Entrada # 5

Teoría de la Información Y Métodos de Codificación

Código Hamming

Lo que llevo de Código

Referencias:

Entrada # 3

Teoría de la Información y 

Métodos de Codificación

Algoritmo de Huffman

Para esta ocasión haremos uso del algoritmo de huffman para realizar la compresión en forma binaria de una frase.

Primeramente que es Algoritmo de Huffman

Este algoritmo fue creado por David A. Huffman con el propósito de la compresión de frases demasiado grandes.

El propósito de algoritmo es crear un árbol binario, a fin de obtener un código, la gran ayuda del árbol es que al seguir la raíz de arriba hacia abajo se obtiene el código de una manera fácil y gráfica.

Los pasos del Algoritmo:

• Se crean varios arboles uno por cada letra de la frase, a estas se le coloca su letra respectiva y la cantidad de veces que aparece.

• Se eligen los dos que tengan la menor frecuencia, estos se unen para crear un nuevo árbol (nodo) y los dos arboles que se unieron se unen mediante ramas (líneas) para indicar que son raíces del árbol que se acaba de crear. A este árbol que se creo, al igual que los anteriores, debe de tener su letra y la cantidad de repeticiones ... Estas se obtienen uniendo las dos letras  y se suman la frecuencia de estas letras.

• Se repite el paso anterior hasta que solo quede un solo árbol el cuál contendrá todas las letras y el tamaño de la frase (o la suma de las frecuencias de los arboles).

El proceso del programa es el siguiente:

• Te pide la frase a la que se le aplicara el algoritmo

• Se obtiene la cantidad de veces que se encuentra un carácter en la frase, por ejemplo: en la frase 'perro' nos detectaría 1 p, 1 e, 2 r, 1 o

• Después se ordena de menor a mayor en base a la cantidad de veces que esta cada carácter.

• La parte siguiente seria aplicar el Algoritmo.

• Teniendo lo que vale cada letra solo se sustituye el binario con la palabra y se obtendría la frase.

• Para regresar la frase solo se lee cada parte del binario y se compara si esta existe en la lista, si no existe se incrementa lo que va ahorita con el siguiente y se vuelve a aplicar el proceso

Código Realizado en Python

Imágenes del Resultado

Como ven en la imagen, nos pide la frase a comprimir; después obtiene la cantidad de veces que aparece cada letra y las ordena en base de menor a mayor según la cantidad de veces que aparece.

Una vez aplica el proceso del árbol y obtenemos una lista la cuál se barrera para obtener el binario de cada letra y para obtener el grafo.

Se obtiene la frase en binario y después se descomprime.

Imagen del grafo:

Corriendo con otra frase:

El único problema que tuve fue que no encontré el como acomodar la imagen a fin de que tenga una mejor presentación ya que mientras existían mas letras la imagen se veía mas horrible.

Referencias

http://networkx.github.io/documentation/latest/tutorial/tutorial.html
http://networkx.lanl.gov/pygraphviz/tutorial.html
http://www.danielmunoz.com.ar/blog/2010/07/07/el-algoritmo-de-huffman/
http://es.wikipedia.org/wiki/Algoritmo_de_Huffman

Entrada # 2

Teoría de la Información y Métodos de Codificación

Para esta entrada se nos encargo una simulación utilizando los métodos de búsqueda para palabras.

El primer método es el de Boyer-Moore.

Es un Algoritmo de búsqueda de cadenas desarrollado por Bob Boyer y J Strother Moore en 1977.

El algoritmo funciona de esta manera:

• Teniendo una frase o cadena de caracteres se pretende buscar una palabra en esta cadena.

• La palabra se pre procesada  primero invierte la palabra: si la palabra es "perro" se convierte a "orrep".

• Teniendo la palabra pre procesada se elimina el primer carácter de este.

• Después se genera una especie de patrón, el cuál contiene la palabra y las letras de la frase que no están en la palabra.

• Teniendo estos datos el proceso del algoritmo seria un ciclo repetitivo del siguiente paso hasta que se haya encontrado la palabra en la frase o ya se halla pasado por toda la frase.

• Se colocan la palabra al principio de la frase y se hace una comparación de derecha a izquierda, si el ultimo elemento de la palabra es diferente a la letra de la frase que se encuentra en la misma posición 

Generalmente el algoritmo es más rápido cuanto más grande es la clave que es buscada, usa la información conseguida desde un intento para descartar tantas posiciones del texto como sean posibles en donde la cadena no coincida.

Solo tengo un mugrero de código.

Entrada # 1

Teoría de la Información y 

Métodos de Codificación

Para esta entrega se nos pidió realizar un programa para generar y transmitir palabras y mostrar de forma gráfica.

Explicación de lo realizado (Cabe resaltar que este proceso que se explicara a continuación se realizo varias veces).

Las palabras del generador y el transmisor consisten en listas de 0 y 1, para generar estas palabras utilizan ciertas variables.

Generador:

• Porcentaje de Ceros que puede llevar
• Tamaño de la palabra

Transmisor:

• Frecuencia de Ceros
• Frecuencia de Unos
• El Generador
• Tamaño de la palabra

Después estos son comparados si son iguales el éxito es 1 si no es 0.

Para ver una mejor explicación del Generador y el Transmisor muestro la siguiente imagen:

En esta imagen se muestra que cuando se corre el python le indicamos que las variables tendrán tamaño 5 el porcentaje de 0 para el Generador sera 0.3, La frecuencia de 0 y 1 para el transmisor sera 0.9 y el ultimo 8 indica la cantidad de veces que se hará este proceso.

En este mismo código se determino un porcentaje de éxito el cuál sera una comparación del generador y el transmisor, en la imagen el primer dato es el Generador y la otra es la del Transmisor el dato siguiente es 0 si son distintos y 1 si son iguales.

Después estos éxitos se suman y se saca un promedio que seria el porcentaje de éxito que se menciono anteriormente.

Este dato es tratado por AWK para obtener el promedio de este.

Y el resultado es guardado en un archivo el cuál sera gráficado con Gnuplot.

Código de la Ejecución:

Código de Bash

Este es el encargado de realizar todo el proceso; este primeramente revisa si los archivos que se utilizaran en el proceso si existen los borra, después crea el cuál utilizara gnuplot, el siguiente punto son los for aninados la cantidad de for es igual a la cantidad de variables que recibe Python.

En el transcurso de los for se obtiene el promedio de éxitos el cuál sera agregado al archivo Promedios.puddi que sera utilizado por el AWK para obtener el promedio de todos los promedios del archivo.

Ese dato obtenido en conjunto con los de los for's (A excepción del último) son enviados al archivo Canales.puddi el cuál sera graficado.

Código de Python

Esté obtiene un ciclo en el cuál se realiza el siguiente proceso varias veces: nos da el Generador y la Transmisión; los compara si son iguales, la variable éxito es igual a uno si no cero.

Terminando todo el ciclo se saca el promedio de todos los éxitos del ciclo y este dato sera utilizado mas adelante.

Código de AWK

Nos da el promedio de todos los elementos del Archivo Promedios.puddi

Código de Gnuplot

Gráfica el archivo Canales.puddi

Imágenes de la ejecución

Probando con otros tipos de tamaño:

A continuación la liga al repositorio donde se encuentra el código: Liga

Prueba

dndns