[TEORÍA DE LA INFORMACIÓN] Resumen

Accelerating Protein Classification Using Suffix Trees

Bogdan Dorohonceanu and C.G. Nevill-Manning

Introducción

Las matrices de búsqueda de posición específica han sido usadas extensamente para reconocer regiones altamente conservadas de proteinas. Dorohonceanu y Nevill-Manning presentan un método para acelerar las búsquedas usando estructura de arboles de sufijos calculada desde las secuencias que se buscarán.

Estas matrices de búsqueda capturan la distribución característica de aminoácidos. Son más sensitivas que los métodos basados en expresión regular coo PROSITE y EMOTIF pero requieren menos información que los modelos ocultos de Markov.

Su principal desventaja contra PROSITE y EMOTIF es su velocidad. Debido a que en esos métodos permiten hacer saltos en cualquier discrepancia, en una matriz de búsqueda siempre se acierta con la misma probabilidad, por lo que hacer saltos es algo problemático.

La desventaja de usar arboles de sufijos es que es muy caro en términos de memoria; requiere 37 bytes por símbolo de entrada. Sin embargo los autores lograron reducir esto a 17 bytes.

Matices de búsqueda

Una matriz de búsqueda de posición específica S representa un alineamiento local sin pausas de una familia de secuencias. El alineamiento consiste en varias posiciones contiguas, cada posición representada por una columna en la matriz. Cada columna j consiste en un vector Sj(r), un resultado por cada posible residuo r.

Una matriz de búsqueda puede ser usada en análisis de secuencias, pasando la matriz por la secuencia y calculando el resultado del segmento. Cada resultado es la suma de las entradas apropiadas de la matriz, donde cada residuo corresponde a un resultado en una columna de la matriz.

Intuitivamente, un resultado del segmento mayor indica un mayor probabilidad de que la secuencia sea igual que la matriz de búsqueda.

Muchas implementaciones de PSSM's para funciones de predicción de proteínas aplican la matriz a cada segmento de cada proteína en la entrada. ordenan los segmentos por sus resultados y presentan los mejores resultados.

Arboles de sufijos

Un árbol de sufijos es un árbol compacto de sufijos en una cadena, para cada sufijo de una cadena hay un camino en su árbol correspondiente desde la raíz hasta las hojas que contengan la cadena.

La imagen anterior muestra un árbol de sufijos para la cadena "abab$". Este árbol es compactado de la siguiente manera. Donde sea que dos aristas inicien en el mismo nodo que comparta un prefijo, una nueva arista y un nodo son creados, y la arista tendrá la misma cadena. Por lo que las aristas anteriores ya no comparten el prefijo. Esto se hace hasta que ninguna arista comparta prefijos.

Para encontrar un segmento de buenos resultados en un set de secuencias de proteínas, primero se crea un arreglo de secuencias. Después se hace un DFT (búsqueda de profundidad) del árbol, calculando los resultados para las cadenas de las aristas.

Donde sea que el resultado alcance el umbral, todas las subcadenas representadas por las hojas de ese nodo deben también alcanzarlo, y pueden ser reportadas.

Esa es la llave para la aceleración, muchas subcadenas pueden ser descontinuadas basado en un simple camino. La siguiente imagen muestra dos casos: un subarbol que acierta y uno que no lo hace.

Arboles de sufijos compactos

Un problema significante es que los arboles son su tamaño en memoria primaria. Los aminoacidos consisten en 20 elementos, en la base de datos se registran 20 millones de aminoacidos y con aproximadamente 30 millones de nodos. Esto es 30,000,000 nodos x 22 punteros por nodo x 4 bytes por puntero dando como resultado 2.6 Gb. Pero no todos los nodos cuentan con almentos 20, se puede ahorrar memoria al usar listas enlazadas a sus hijos.

Esto da a un total de 30,000,000 nodos x 4 bytes por nodo x 4 bytes por puntero dando resultado a 480 Mb.

Fuente:
http://www.aaai.org/Papers/ISMB/2000/ISMB00-013.pdf

[VISIÓN COMPUTACIONAL] Lab 4: Diagonales

Siguiendo la entrada anterior sobre detección de lineas, esta vez haré lo mismo pero sobre diagonales. Básicamente lo que le decía al programa era que si encontraba una linea a 0º o a 90º, las pintara en colores distintos. Ahora el programa busca todas las lineas y separa las diagonales de las rectas.

En lugar de solo buscar diferencias en los gradientes, ahora utilizo la función arctan de python (math.atan) que dependiendo de los gradientes x o y se emplea de una o de otra manera.

La imagen de prueba la creé utilizando paint online usando lineas negras.

Para poder trabajar con la imagen, primero le apliqué un fondo rojo, las diagonales las pinté en blanco y las rectas en negro, aunque las lineas ya son negras solo detectaré el contorno de ellas.

La imagen queda de la siguiente mantera:

Se puede observar como las diagonales no son perfectas, esto es debido a que en realidad las diagonales son secuencias de lineas horizontales o verticales apiladas.

Ahora hay que separar las lineas, debido a que por ahora no sabemos si se trata de segmentos separados.

Para eso se utiliza BFS que ya había utilizado en entregas anteriores, con la ayuda de un poco de dilatación. El resultado es el siguiente:

Despues de eso solo pinté en la imagen original los pixeles pertenecientes al contorno de cada linea que estan en la imagen modificada:

El programa no detecta las lineas en si, sino que detecta el borde de ellas, ya que técnicamente una linea recta es un rectángulo de un pixel de grosor. por lo tanto hay 4 lineas que detectar. Para las diagonales es distinto, ya que el BFS las une, aún así se logran pintar los bordes de distinto color.

Código:
Liga al proyecto:
https://github.com/victoralex911/vision-computacional

[REDES DE TELECOMUNICACIONES] Resumen NS-2 (Network Simulator)

Usando el Simulador de Redes NS-2 para Evaluar la Red en Chips (NoC)

Muhammad Ali, Michael Welzl, Awais Adnan, Farrukh Nadeem

1. Introducción:

En estos días, la tecnología de los chips ha llegado a un nivel en el que sistemas completos pueden ser integrados en ellos, son arquitecturas con diseños llamados VLSI (Very-large-scale integration). Estos chips son llamados SoC (System on a Chip) primariamente usados en sistemas integrados.

De acuerdo con la ITRS (International Technology Roadmap for Semiconductors) antes del fin de la década, los chips serán diseñados con millones de transistores. En el futuro cercano los chips serán de Circuitos Integrados para Aplicaciones Especificas (ASIC) que comprometerán miles de componentes heterogeneos integrados todos juntos para proveer funcionalidad completa a una aplicación.

Sin embargo, desarrollar estos chips no es una tarea fácil, debido a que el numero de transistores crece por chip, integran una gran complejidad.

La idea es conectar diferentes recursos en un chip a través de una red donde la comunicación toma lugar en lugar de conectar recursos usando cables dedicados.

NS-2 es un simulador open source orientado a objetos y eventos discretos, escrito en C++ y PTcl. Es una herramienta muy usada para simular pequeñas y grandes redes Debido a que los chips NoC presentan muchas similitudes con las redes, NS-2 ha sido de elección para simular redes NoC.

2. Network on a Chip (NoC)

NoC ha sido una propuesta alternativa viable para los buses ineficientes de los SoC's de hoy en dia. Los NoC son vistos como una colección de recursos computacionales conectados a través de una red donde se comunican usando paquetes. Muchas topologías se han `propuesto para los NoC's incluyendo ""D mesh", "fat tree", "honeycomb".

Debido a que NoC está compuesto por diferentes marcas con sus propias propiedades intelectuales, una interface de red (NI) para este tipo de infraestructura necesita actuar como una capa media que transforme flujos de datos de los recursos en paquetes antes de ser enviados al "router" y viceversa. Cuando un recurso necesita enviar algo, inicia transmitiendo la información al NI, que crea los paquetes de tamaños predefinidos. Los routers verifican las direcciones de destino y envían el paquete de acuerdo a esos datos.

3. NoC's y Redes: Similitudes

Es difícil mantener la sincronia global con varios componentes en un chip usando un solo reloj. Para eso, se utilizarán GALS (Globally Asynchronous Local Synchronous) que son modelos de reloj para realizar comunicaciones entre componentes.

Antes de empezar en el desafio, se propone un protocolo de 5 capas para gobernar la comunicación en un NoC, en comparación con el modelo OSI.

Las características de los NoC están influenciadas por las redes computacionales.

Los autores han realizado simulaciones con NS-2 y "chpsim" para varias topologías y patrones de trafico. Su argumento está basado en el hecho de que dibido a la escalabilidad de los chips, los SOC's son asíncronos, y por lo tanto operaciones "on-chip" pueden ser de eventos direccionados en lugar de controlados por una sola señal de reloj.

4. NoC's y Redes: Diferencias

La diferencia primaria entre redes y los NoC's es el tamaño. Las redes pueden alcanzar un tamaño desde un pequeño cuarto hasta una ciudad entera, además de el mundo entero (internet). Los NoC's son de unos 50 a 60 nanómetros hechos de silicón Lo que da pequeños problemas, por ejemplo, un buffer tiene que ser de tamaño limitado en estos chips

Mientras que las redes pueden llegar a consumir grandes cantidades de energía, los chips solo podrían consumir pequeñas cantidades de energía.

5. Simulando NoC's con NS-2

Un diseño de SoC involucra tres estados; Diseño de comportamiento, Diseño estructural, Diseño físico.

El diseño de comportamiento especifica la funcionalidad de el sistema a un alto nivel de abstracción, mientras que el diseño estructural y el diseño físico reduce la misma a un nivel de "compuertas lógicas" y nivel de transistores.

En el diseño de comportamiento, un SoC está realizado como una colección de componentes que son modelados como bloques y conexiones junto con los protocolos que gobiernan la comunicación.

6. Limitacones

Mientras que NS-2 es mejor para simular un NoC a nivel de comportamiento, no es posible obtener una vista del diseño estructural y físico.

Sin embargo existe software como VHDL que se ha utilizado para sintetizar chips y hacer casos de estudio de estos a un nivel de compuertas lógicas.

Este modelo aún esta en experimentación y cada vez hay mas propuestas para protocolos de comunicación a este nivel. Por ahora solo queda seguir con las simulaciones y perfeccionarlas.

Fuente:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4136934

[VISIÓN COMPUTACIONAL] Detección de lineas

Para esta tarea, se encargó realizar detección de lineas horizontales y verticales. Para los ejemplos utilizaré las siguientes imagenes.

Primero que nada, calcularemos los gradientes horizontal y vertical por separado para cada imagen. Esto se hace utilizando alguna mascara de convolución para bordes. Se utiliza tanto su forma horizontal como su forma vertical por que de ahí se sacaran las lineas.

Una vez teniendo los gradientes, se calcula el ángulo para cada pixel en cada gradiente. Si gx = 0 y gy = 0, entonces no se toma el ángulo. Si gx = 0 y gy = 255, entonces el ángulo es 90º. Si gx = 255 y gy = 0, entonces el ángulo es 0º.

Con esas condiciones podemos obtener las lineas horizontales y verticales.

Para ello es necesario calcular rho:

Este se guarda en un diccionario junto con un valor para cada pixel, si el pixel es igual al anterior, su rho será aparentemente igual. por lo tanto se trata de una posible linea.

Los resultados son los siguientes:

Código:
Liga al proyecto:
https://github.com/victoralex911/vision-computacional

[REDES DE TELECOMUNICACIONES] Calidad de servicio de YouTube

Para esta entrada haré algunas pruebas de calidad de servicio a YouTube. Las pruebas son:

• Retardo.
• Perdida de paquetes.
• Jitter. 
• Ancho de banda.

Las pruebas consisten en analizar el comportamiento de los datos para 4 calidades de video de YouTube; 360p, 480p, 720p y 1080p. Las ultimas 2 pruebas (Jitter y Ancho de banda) las realizaré en forma general para un video en 480p ya que Wireshark no responde bien mientras se reproduce un video en HD.

Retardo:

Para esto utilizaré Wiresharck y capturaré los paquetes que corresponden al video.

Obtengo la información de tiempo, mi referencia es el "Epoch Time" que es el momento en que nació el paquete, solo tomaré las décimas, y se lo restare a las décimas del "Time since reference or first frame" que es la hora de llegada del paquete.

Después de promediar varios paquetes el retardo aproximado promedio es de 0.05 segundos entre paquetes al reproducir un video a 360p.

Ahora haré el de cada calidad de video:

360p:    0.05s
480p:    0.055s
720p:    0.07s
1080p:  0.06s

Los retardos se mantienen en un mismo rango para las 4 calidades de video.

Pérdida de paquetes:

Esta vez utilizaré la herramienta IO Graph para los paquetes recibidos con el filtro para analizar la perdida de paquetes "tcp.analysis.lost_segment".

Al reproducir un video en 360p este fue el resultado de la gráfica:

De izquierda a derecha se inicia la descarga y se detiene la misma, cabe destacar que durante algunas subidas de perdida de paquetes el video dejaba de hacer buffering.

Al reproducir un video a 480p:

Aunque esta vez se reprodujo un video de menor tiempo, se puede notar que las subidas son mayores. Los efectos de buffering son igual de aplicables, pausándose en algunas subidas.

Al reproducir un video a 720p:

Aunque no parece una perdida diferente a las demás, debo destacar que solo se muestra lo equivalente a   7 segundos de reproducción de video en 720p, mientras que en los demás logré reproducir al menos 1 minuto. El buffering se pausaba a cada momento durante la prueba.

Al reproducir un video a 1080p:

Sin palabras, después de eso Wireshark no respondió. El video nunca cargó.

Jitter:

Utilizando una de las gráficas de Wireshark pude analizar el jittering de un video, la pregunta es, ¿realmente hay jittering?

La gráfica es la siguiente:

Durante una descarga de un video, se capturo lo que se ve en la imagen. Es interesante ver como los primeros 4 segundos los paquetes llegaron (quizá con perdidas) agrupados uno detrás de otro. Pero a partir del segundo 5 los paquetes empezaron a agruparse. Cada punto contiene varios paquetes. Mi teoría es que las zonas vacías donde pudiera haber paquetes no hubo recepción debido al jittering. La recepción del paquete falla debido a que la lectura se realiza entre la llegada de un nuevo paquete y la salida del anterior.

Ancho de banda:

YouTube tiene una herramiente basica para la medición de mi ancho de banda, al dar click derecho sobre el video y seleccionar "Realizar prueba de velocidad" me dará información sore mi ancho de banda y otros datos interesantes.

Mi ancho de banda me permite reproducir cualquier video con una velocidad de descarga de 5.46 Mbps, es algo raro ver que el nivel mundial está por encima de los niveles locales, y ver mi gráfica (en negro) me hace pensar que la calidad de servicio con mi actual compañía proveedora de internet deja demaciado que desear.

Por último mencionar que todas las pruebas se hicieron con videos distintos, muchos de los resultados pueden variar en función al formato original del video.

Fuentes:

http://wiki.wireshark.org/

http://en.wikipedia.org/wiki/Quality_of_service

[REDES DE TELECOMUNICACIONES] Lab 4: Calidad de servicio (QoS)

Para este laboratorio mencionaré algunas medidas QoS. QoS o Calidad de servicio (Quality of Service, en inglés) es la capacidad de dar un buen servicio. Es especialmente importante para ciertas aplicaciones tales como la transmisión de vídeo o voz.

Muchas cosas le ocurren a los paquetes desde su origen al destino, resultando los siguientes problemas vistos desde el punto de vista del transmisor y receptor:

Retardos:

Los retardos son causa de demoras en el tiempo de transmisión y procesamiento de la información además del tiempo de ejecución y procesamiento de las aplicaciones que usan los usuarios.

Este parámetro es también conocido en el ámbito de las telecomunicaciones como latencia. La causa de este retardo es que cuando la información es procesada esta fluye a través de una gran cantidad de componentes y subsistemas de comunicación, situados en el sistema receptor así como en la red. Cada uno de esos componentes pueden ser caracterizados por su velocidad de procesamiento y por la capacidad de almacenamiento (buffers) donde los datos esperan para ser procesados.

La suma de todas las contribuciones de retardos individuales vista como un todo es lo que genera el parámetro reconocido como retardo. El máximo retardo que es el que ocurre de extremo a extremo conocido como mouth-to-ear (de boca a oído) recomendado para conversaciones en tiempo real no debe exceder los 150 ms. Los retardos impactan en el tiempo en que el usuario debe esperar para establecer la conexión y, una vez establecida, en las demoras temporales de la comunicación misma.

Pérdida de paquetes:

La perdida de paquetes ocurre cuando uno o mas paquetes de datos que viajan en una red IP fallan en alcanzar su destino. La causa de la perdida de paquetes es debida varios factores, entre los que se puede nombrar, degradación de la señal al viajar por el medio, interconexiones de la red sobresaturadas, paquetes con error rechazados en el transito, falla en el hardware de la red, o rutinas normales de enrutamiento.

Cuando la perdida de paquetes es causada por problemas en la red, los paquetes perdidos pueden resultar en problemas de desempeño que causen fallas notables en el desempeño de la red, sin embargo la perdida de paquetes no siempre es tan dañina, como por ejemplo cuando es usada para contrarrestar la latencia.

Se considera que la pérdida de paquetes de entre un 5% y un 10% del total de flujo de datos llega a ser percetible.

Cuando existen condiciones de red de cuello de botella, se deben descartar paquetes. Para esto, los protocolos de red como TCP tienen un control de congestion conocido como slow start, en que se evita que el emisor de la información reenvie aquellos paquetes que no fueron recepcionados para no colapsar la red sino hasta un cierto periodo.

Jitter:

El retardo por jitter o simplemente jitter es usualmente definida como la variación en el tiempo de llegada al punto receptor, sufrida entre paquetes de datos sucesivos. Los paquetes deberían llegar igualmente espaciados entre si para permitir una conversión trasparente. La medición del jitter se
realiza en segundos y expresa la distorsión que ocurre en el patrón original de datos enviados, o dicho de otra manera la degradación que ocurre en tiempo sobre la calidad de data. El jitter solo tiene sentido cuando es medido a un set de datos y no a datos individuales.

Una de las soluciones más típicas es considerar un buffer en la recepción de manera de dar una ventana más amplia al tiempo de recepción y poder ordenar los paquetes que no han llegado en el orden normal. La única desventaja es que agrega un retardo adicional al inicio y durante la operación de un servicio de  videos mientras que la rapidez de reproducción de video sea menor a la tasa de los datos que están siendo descargados.

Ancho de banda:

El ancho de banda es la cantidad de información o de datos que se puede enviar a través de una conexión de red en un período dado. El ancho de banda se indica generalmente en bits por segundo (bps), kilobits por segundo (Kbps), o megabits por segundo (Mbps).

Significa el rango neto de bits o la máxima salida de una huella de comunicación lógico o físico en un sistema de comunicación digital. La razón de este uso es que el rango máximo de tranferencia de datos de un enlace físico de comunicación es proporcional a su ancho de banda.

Fuentes:

http://saber.ucv.ve/jspui/bitstream/123456789/731/3/Anexo%202.pdf
http://www.tesis.uchile.cl/bitstream/handle/2250/111980/cf-segura_cv.pdf?sequence=1
http://en.wikipedia.org/wiki/Quality_of_service

[CÓMPUTO UBICUO] Lab 4: Recomendaciones y comentarios

Automóvil Seguro

• Algo que ya se mencionó durante la clase y de menor importancia, es el uso de "radio buttons" en lugar de "checkboxes" para las encuestas, que aunque no influya en gran medida en el proyecto, quizá algunos de los datos tengan más de una opción señalada.
• No seleccionaron las preguntas "obligatorias" tal cual, si bien muchas de las preguntas "opcionales" parecen de mayor o igual importancia.
• Entrando a lo que es el proyecto, muchas de las características que mencionan como posibles adiciones, podrian encajar perfectamente en el mismo proyecto, como la forma de controlar la alarma; las opciones son vía móvil, vía internet, vía control remoto, cuando en realidad controlar la alarma remotamente vía internet a través del móvil es posible.
• En si hay poca planeación, sus conclusiones solo muestran una especie de idea general de lo que recolectaron de los usuarios, y no una idea de lo que ahora harán en base a esos resultados.

Seguridad en Computadora

• La encuesta está a un nivel de lenguaje un poco elevado para un usuario común, podría causar un poco de confusión al encuestado y hacer a que responda solo por responder. Quizá enfocar las preguntas un poco más al proyecto.
• No muestran gráficos muy detallados, solo muestran unos cuantos, quizá debieron mostrar gráficos para preguntas de importancia mayor como el inicio de sesión ideal o problemas frecuentes de privacidad.
• El proyecto suena muy bien, pero hablan de una aplicación grande, es decir, abarcan cuestiones de seguridad y de entretenimiento, la idea no es mala, pero si podrían dividir un poco cada cosa. Además tiene mucho potencial no solo para esas cuestiones, facilmente se podría hablar de cosas como autentificación en sitios web, cajeros automáticos, etc.

Oficina Personalizada

• La parte de la encuesta me parece muy buena, se cubrieron varios aspectos de lo que pretenden hacer, sin embargo no concluyen, o al menos no recuerdo unas palabras acerca de lo que ahora implementarán como siguiente paso.
• Lo de las luces automáticas son cosas que ya existen y son ampliamente personalizables, cosa que les ahorraría mucho trabajo, sin embargo imagino que harán su propia versión. Deben de tomar en cuenta cosas como ahorro energético, ya que la luz de los focos es lo que generalmente gasta más energía. Se les sugiere utilizar energía renobable, pues utilizar un sistema de recarga solar no es mala idea (Claro está que hablamos de una versión a escala por ahora).

Localizador

• Como se mencionó en clase, creo que utilizan un lenguaje un poco elevado para un usuario común, y eso causaría confusiones. Sin embargo logran entenderse.
• La idea creo que es mejor que la enfoquen a alguna aplicación móvil, ya que es igual de fiable. Imaginando un escenario, una persona prefiere comprar un smartphone a cada uno de los de su familia, ya que ofrece mucho más, y existen API's que ayudarían mucho en este proyecto. Google Code ofrece la mayoría de lo que necesitan si deciden ir por el rumbo de smartphone.
• Si deciden irse por el rumbo de un dispositivo de localización, aun así pueden integrar servicios como Twitter y Facebook para estar más en contacto.

Galería Inteligente

• Una idea muy buena pero la opinión de sus encuestados no es lo que esperaba (en especial por lo de los dinosaurios). Creo que la encuesta debió ser a personas que están más en contacto con estos lugares. No estoy seguro si fue así, pero se debió encuestar a gente que trabaja en los museos o a personas que salen de ellos.
• La idea de interacción con el smartphone ya existe, pero es muy básica, en mi opinión pueden hacer algo mejor de los que ya lo intentaron. Además no solo dar soporte a un museo o galería en específico, sino tratar de "vender" el producto a varios museos.

Cama Inteligente

• Todo está bien, pero pienso que si tuviera algo así en días que estoy enfermo entonces sufriría unos minutos. Imagino que planean alguna clase de panel de control que diera la opción de suspender la alarma por las próximas horas y que al finalizar el tiempo pregunte al usuario si desea reanudar o suspender por otro periodo de tiempo.

Casa Inteligente

• La idea del simulador de presencia es excelente y algo inesperado, la verdad nunca había pensado en algo parecido, quizá la idea existía pero nunca la he visto en marcha. Tomen en cuenta cosas como ahorro energético si continúan con esa idea.
• Deberían tener en mente implementar un panel de control en linea para ver el estado de las cerraduras, por si al usuario se le olvida.

CarNXP

• Solo en cuanto a la perdida de dispositivo, seria fatal que descubrieran el uso del smartphone. Creo que se debería de contar con un sistema de apagado. Es decir, que en caso de perder el smartphone llave, acceder vía internet a la configuración y dar de baja el dispositivo, de esa manera permitir utilizar el vehículo sin el dispositivo, mas que con su propia llave de fábrica.