Doctor en Ciencias, Mención Computación / Este trabajo de tesis presenta soluciones para al problema de detección de anomalı́as en flujo de datos multivariantes. Dado una subsequencia de serie temporal (una pequeña parte de la serie original) como entrada, uno quiere conocer si este corresponde a una observación normal o es una anomalı́a, con respecto a la información histórica. Pueden surgir dificultades debido principalmente a que los tipos de anomalı́a son desconocidos. Además, la detección se convierte en una tarea costosa debido a la gran cantidad de datos y a la existencia de variables de dominios heterogéneos. En este contexto, se propone un enfoque de detección de anomalı́as basado en Discord Discovery, que asocia la anomalı́a con la subsecuencia más inusual utilizando medidas de similitud. Tı́picamente, los métodos de reducción de la dimensionalidad y de indexación son elaborados para restringir el problema resolviéndolo eficientemente. Adicionalmente, se propone técnicas para generar modelos representativos y consisos a partir de los datos crudos con el fin de encontrar los patrones inusuales. Estas técnicas también mejoran la eficiencia en la búsqueda mediante la reducción de la dimensionalidad. Se aborda las series multivariantes usando técnicas de representación sobre subsequencias no- normalizadas, y se propone nuevas técnicas de discord discovery basados en ı́ndices métricos. El enfoque propuesto es comparado con técnicas del estado del arte. Los resultados ex- perimentales demuestran que aplicando la transformación de translación y representación de series temporales pueden contribuir a mejorar la eficacia en la detección. Además, los métodos de indexación métrica y las heurı́sticas de discord discovery pueden resolver eficien- temente la detección de anomalı́as en modo offline y online en flujos de series temporales multivariantes. / Este trabajo ha sido financiado por beca CONICYT - CHILE / Doctorado para Extranjeros, y apoyada parcialmente por el Proyecto FONDEF D09I1185 y el Programa de Becas de NIC Chile

No description available.

No description available.

Una de las operaciones más importantes en datos multimedia es la de buscar objetos similares entre sí. Para realizar esta búsqueda, es que se recurre al concepto de espacio métrico, el cual permite modelar la relación de similitud por medio de una función de distancia, que cumple la desigualdad triangular, entre otras propiedades. Esta distancia, resulta, generalmente, costosa de calcular, por lo que es necesario la construcción de índices para resolver las búsquedas de manera eficiente. El tema de la eficacia es también un aspecto muy importante, cuando se trabaja con búsquedas por similitud, ya que no solamente es necesario poder responder las consultas rápidamente, sino que también es necesario entregar resultados relevantes. Para mejorar este aspecto, es que se utiliza un espacio multimétrico, el que define dinámicamente la distancia a utilizar, ponderando en mayor medida aquellas características que sean más relevantes para la consulta. El problema de esta estrategia es que existen pocos índices que permitan trabajar con espacios multimétricos y los índices de espacios métricos no pueden ser usados directamente, pues la distancia de éstos es fija. Es por esta razón que en esta memoria se busca contribuir con nuevas técnicas de indexamiento para espacios multimétricos. Para esto se estudia y propone una metodología que permite adaptar índices métricos para ser utilizados en un contexto de espacios multimétricos. Se muestra también cómo esta técnica puede ser utilizada para modificar las estructuras List of Clusters y GNAT, así como también el hecho que las estructuras previamente existentes también resultan de utilizar la metodología propuesta. Finalmente se realiza una evaluación experimental, comparando los índices propuestos con los ya existentes, obteniendo que unos de los índices propuestos, MMGNAT, muestra un mejor desempeño que el estado del arte.

El presente trabajo está enfocado en las bases de datos multimedia, área importante de investigación en los últimos años. Por objetos multimedia se entiende contenido como audio, imágenes, objetos 3D, etc. A diferencia de las bases de datos tradicionales, en una base de datos multimedia no se buscan los objetos que cumplan una condición exacta, sino los más parecidos a un objeto conocido de antemano, llamado objeto de consulta. Por esta razón, la búsqueda por similitud es uno de los temas principales de estudio en las bases de datos multimedia. Para reflejar la similitud entre objetos multimedia, en general existen distintos métodos para calcular una distancia entre dos objetos multimedia, los cuales intentan reflejar el parecido entre dichos objetos (a mayor distancia, más disímiles son). Se ha comprobado empíricamente que algunos métodos funcionan mejor que otros ante distintos tipos de objetos de consulta, y que combinar varios de ellos a la vez entrega generalmente mejores resultados que utilizar cada uno en forma separada. Sin embargo, aún no existe una forma clara de decidir la forma de combinarlos en el momento de la consulta, y muchas veces se termina utilizando el mejor método en promedio, lo cual no siempre es la mejor opción. En este trabajo se estudia un método formal para combinar estos métodos, realizando una consulta previa en un conjunto de objetos conocido como conjunto de entrenamiento, que permite estimar en forma dinámica la calidad de cada método ante un objeto de consulta dado. Como primera tarea, se implementó un entorno de trabajo que permite realizar experimentos de manera masiva, incorporar fácilmente distintos tipos de bases de datos y definir los tipos de experimentos a ejecutar. El entorno de trabajo implementado permitió estudiar cómo afecta la selección de un conjunto de entrenamiento en determinar la calidad de un método de transformación de objetos multimedia. De los resultados experimentales obtenidos, se concluye que un conjunto de entrenamiento adecuado es de un tamaño bastante pequeño en relación a la base de datos original, lo que permite estimar la calidad de un método de cálculo de similitud con poco esfuerzo adicional. Adicionalmente, se observó que el cálculo dinámico de esta información permite aproximarse bastante a mejores combinaciones de métodos, las cuales sólo pueden ser obtenidas mediante fuerza bruta. Se muestra también que algunos resultados tienden a ser independientes de la base de datos, mientras que otros son exclusivos de la forma en que ésta haya sido construida, y que en general todos los resultados poseen un buen grado de robustez, lo que permite reproducirlos fácilmente en bases de datos con distintos tipos de información multimedia.

El objetivo principal de la tesis gira en torno a la búsqueda de imágenes por similitud y, en concreto, a la evaluación y propuesta de técnicas para la recuperación y clasificación de imágenes de marcas similares. Hasta llegar al desarrollo del sistema presentado para evaluar la similitud de logos se ha realizado un estudio de las técnicas existentes para búsqueda de imágenes similares, implementando y comparando varias técnicas basadas en descriptores tradicionales y características neuronales que se describen en esta tesis. Para ello se ha usado MirBot, una app colaborativa de etiquetado de imágenes que ha permitido aplicar descriptores tradicionales y aproximaciones neuronales, sirviendo de ejemplo para ilustrar el recorrido realizado por las diferentes técnicas existentes y su evolución en el estado del arte. Adicionalmente se ha desarrollado un método de verificación geométrica sobre puntos de interés locales. Por último, se presenta un sistema de búsqueda de similitud de logos. Para ello se ha usado un conjunto de datos de la EUIPO (Oficina de Propiedad Intelectual de la Unión Europea) llamado EUTM (European Union Trademark), que, además de las imágenes, contiene metadatos con información sobre colores, formas, sectores y elementos figurativos. En base a este tipo de datos se propone un método de búsqueda por similitud multi-etiqueta de imagen de marca. Para ello se combinan técnicas de pre-procesamiento con redes neuronales convolucionales especializadas en la detección de características concretas de logotipos. Se han estudiado topologías aplicables a la imagen de marca y su relación con los metadatos de la base de datos utilizada. Para evaluar el sistema, y puesto que la semántica de marcas puede resultar muchas veces subjetiva, se han verificado los resultados mediante encuestas a estudiantes y profesionales del diseño, demostrando que el sistema propuesto mejora los resultados de los sistemas manuales incluso entre personas con conocimientos de diseño gráfico y composición de imágenes. Por tanto, el método propuesto también puede contribuir a mejorar el proceso de etiquetado de imagen, ya que ofrece una propuesta de clasificación con la probabilidad de pertenencia a cada una de las clases. El método propuesto permite obtener un ranking de los logos más similares permitiendo a los usuarios seleccionar las características a considerar en el proceso de búsqueda. Hasta donde sabemos no existen métodos en la literatura que aborden estos dos objetivos, por lo que consideramos que una propuesta de este tipo es de gran interés tanto metodológicamente como de forma práctica para ayudar en múltiples tareas, como pueden ser el etiquetado de logos, la detección de plagios o la búsqueda por similitud de imagen de marca.

Els inhibidors d'entrada del VIH han sorgit recentment com una nova generació de fàrmacs antiretrovirals, els quals bloquegen la unió del virus als co-receptors de membrana CXCR4 i CCR5. S'han desenvolupat diverses molècules petites antagonistes d'aquests co-receptors, algunes de les quals estan actualment en fase d'assaig clínic. No obstant això, donat que no existeixen estructures cristal·logràfiques per aquests co-receptors proteics, és necessari analitzar els modes d'unió d'inhibidors coneguts a la cavitat d'unió extracel·lular dels co-receptors mitjançant experiments de mutagènesi dirigida i estudis computacionals. En general, l'objectiu d'aquestes aproximacions computacionals és cribar un gran nombre de compostos candidats a fàrmacs ràpidament. El cribatge virtual s'ha convertit recentment en un complement útil dels mètodes de cribatge experimentals high-throughput screening per a grans llibreries de compostos. Per tant, en aquesta tesi s'ha portat a terme un protocol de cribatge virtual, mitjançant aproximacions basades en el receptor i en lligands actius coneguts, amb la finalitat de trobar antagonistes de CXCR4 i CCR5 que puguin servir com a potencials inhibidors d'entrada del VIH.Per al cribatge virtual basat en el receptor, s'han millorat els models dels co-receptors CXCR4 i CCR5 construïts a la secció de disseny molecular de l'IQS, i s'han portat a terme assajos preliminars de mode d'unió utilitzant aquests models i lligands coneguts d'elevada afinitat. Així mateix, s'ha analitzat el comportament en el cribatge virtual i en el post-processat de resultats de docking de diferents fingerprints d'interacció en comparació amb els resultats obtinguts per un nou fingerprint d'interacció (APIF) desenvolupat a la secció de disseny molecular de l'IQS.Per al cribatge virtual basat en lligands, s'han comparat models farmacofòrics i diverses aproximacions basades en la forma i propietats moleculars utilitzant lligands d'elevada afinitat com a molècules de referència. A més, s'ha desenvolupat una nova aproximació basada en la forma molecular, la qual s'ha utilitzat per a estudiar en profunditat la hipòtesi de la multi-regió d'unió de la cavitat d'unió extracel·lular del co-receptor CCR5.Tots els mètodes, ja siguin basats en el receptor o en lligands coneguts, s'han aplicat en primer lloc de manera retrospectiva utilitzant una extensa base de dades d'inhibidors de CXCR4/CCR5 i suposats inactius, similars en propietats als actius, recopilada en aquesta tesi. Per a cada receptor, la quimioteca ha estat cribada utilitzat inhibidors coneguts, S'han analitzat els factors d'enriquiment i la diversitat a les llistes finals de hits. A més, s'han portat a terme anàlisis ROC per a ambdós inhibidors de CXCR4 i CCR5 amb la finalitat de comparar l'habilitat del nou algoritme basat en la igualtat de formes de lligands amb la resta d'aproximacions de cribatge utilitzades.Una vegada validades les diferents aproximacions de cribatge i seleccionats els millors paràmetres per a cadascuna d'elles, s'han aplicat les eines de cribatge virtual de manera prospectiva sobre una quimioteca combinatòria dissenyada a la secció de disseny molecular de l'IQS, així com tècniques de disseny de novo de lligands per tal d'identificar nous bloquejadors de l'entrada del VIH a les cèl·lules. / Los inhibidores de entrada del VIH han surgido recientemente como una nueva generación de fármacos antiretrovirales, los cuales bloquean la unión del virus con los co-receptores de membrana CXCR4 y CCR5. Se han desarrollado diversas moléculas pequeñas antagonistas de estos co-receptores, algunas de las cuales están actualmente en fase de ensayo clínico. Sin embargo, dado que no existen estructuras cristalográficas para estos co-receptores proteicos, es necesario analizar los modos de unión de inhibidores conocidos a la cavidad de unión extracelular de los co-receptores mediante experimentos de mutagénesis dirigida y estudios computacionales. En general, el objetivo de estas aproximaciones computacionales es cribar un gran número de compuestos candidatos a fármacos rápidamente. El cribado virtual se ha convertido recientemente en un complemento útil de los métodos de cribado experimentales high-throughput screening para grandes librerías de compuestos. Por lo tanto, en esta tesis se ha llevado a cabo un protocolo de cribado virtual, mediante aproximaciones basadas en el receptor y en ligandos activos conocidos, con el fin de encontrar antagonistas de CXCR4 y CCR5 que puedan servir como potenciales inhibidores de entrada del VIH.Para el cribado virtual basado en el receptor, se han mejorado los modelos de los co-receptores CXCR4 y CCR5 construidos en la sección de diseño molecular del IQS, y se han llevado a cabo ensayos preliminares de modo de unión utilizando estos modelos y ligandos conocidos de elevada afinidad. Asimismo, se ha analizado el comportamiento en el cribado virtual y en el post-procesado de resultados de docking de diferentes fingerprints de interacción en comparación con los resultados obtenidos por un nuevo fingerprint de interacción (APIF) desarrollado en la sección de diseño molecular del IQS.Para el cribado virtual basado en ligandos, se han comparado modelos farmacofóricos y diversas aproximaciones basadas en la forma y propiedades moleculares utilizando ligandos de elevada afinidad como moléculas de referencia. Además, se ha desarrollado una nueva aproximación basada en la forma molecular, la cual se ha utilizado para estudiar en profundidad la hipótesis de la multi-región de unión de la cavidad de unión extracelular del co-receptor CCR5.Todos los métodos, ya sean basados en el receptor o en ligandos conocidos, se han aplicado en primer lugar de manera retrospectiva utilizando una extensa base de datos de inhibidores de CXCR4/CCR5 y supuestos inactivos, similares en propiedades a los activos, recopilada en esta tesis. Para cada receptor, la quimioteca ha sido cribada utilizando inhibidores conocidos, Se han analizado los factores de enriquecimiento y la diversidad en las listas finales de hits. Además, se han llevado a cabo análisis ROC para ambos inhibidores de CXCR4 y CCR5 con el fin de comparar la habilidad del nuevo algoritmo basado en la igualdad de formas de ligandos con el resto de aproximaciones de cribado utilizadas.Una vez validadas las diferentes aproximaciones de cribado y seleccionados los mejores parámetros para cada una de ellas, se han aplicado las herramientas de cribado virtual de manera prospectiva sobre una quimioteca combinatoria diseñada en la sección de diseño molecular del IQS, así como técnicas de diseño de novo de ligandos para identificar nuevos bloqueadores de la entrada del VIH a las células. / HIV entry inhibitors have emerged as a new generation of antiretroviral drugs that block viral fusion with the CXCR4 and CCR5 membrane co-receptors. Several small molecule antagonists for these co-receptors have been developed, some of which are currently in clinical trials. However, because no crystal structures for the co-receptor proteins are available, the binding modes of the known inhibitors within the co-receptor extracellular pockets need to be analyzed by means of site-directed mutagenesis and computational experiments. Generally, the objective of these computational approaches is to screen large numbers of candidate drug compounds rapidly. Virtual screening has recently become a useful complement to laboratory-based high-throughput screening methods for large libraries of compounds. Hence, in this thesis, a virtual screening protocol, using several receptor-based and ligand-based approaches, has been performed to find CXCR4 and CCR5 antagonists that could potentially serve as HIV entry inhibitors.For receptor-based virtual screening, homology models of CXCR4 and CCR5 co-receptors built in our research group have been improved, and preliminary binding mode analyses using these models and high affinity known ligands have been carried out. Also, the performance in virtual screening and docking post-processing of different interaction fingerprints, compared to the results obtained with a new interaction fingerprint (APIF) developed in our research group, has been analysed.For ligand-based virtual screening, pharmacophore modelling and several shape-based and property-based molecular comparison approaches have been compared, using high-affinity ligands as query molecules. Also, a novel consensus shape-based virtual screening approach has been developed and used to investigate and add further evidence for multiple binding sites within the CCR5 extracellular pocket hypothesis.All the receptor-based and ligand-based methods have been firstly applied in a retrospective virtual screening, using a large database of known CXCR4/CCR5 inhibitors and similar presumed inactive molecules assembled in this thesis. For each receptor, the library has been queried using known binders, and the enrichment factors and diversity of the resulting virtual hit lists have been analyzed. Moreover, receiver-operator-characteristic analyses for both CXCR4 and CCR5 inhibitors have been carried out in order to compare the performance of the new consensus shape matching algorithm with the other screening approaches used. Once the different virtual screening approaches have been validated and the best parameters for each one have been selected, prospective virtual screening of a combinatorial library designed by our research group and de novo design methods have been applied to identify new HIV entry blockers.