La privacitat de les connexions dels usuaris d'una xarxa social

Aquest projecte mostra com les connexions dels usuaris d'una xarxa social suposen un risc afegit per a la privacitat dels usuaris que hi formen part. Aquestes connexions ofereixen informació suficient per a poder dur a terme processos d'agregació d'informació entre diferents xarxes socials, permetent a un atacant millorar el seu coneixement inicial sobre les xarxes. El projecte és un recorregut per totes les fases necessàries per dur a terme aquest procés, des de la recollida de la informació fins a l'agregació de les dades obtingudes.

MR MAQ: algorisme de Read Mapping utilitzant la plataforma Hadoop

L’èxit del Projecte Genoma Humà (PGH) l’any 2000 va fer de la “medicina personalitzada” una realitat més propera. Els descobriments del PGH han simplificat les tècniques de seqüenciació de tal manera que actualment qualsevol persona pot aconseguir la seva seqüència d’ADN complerta. La tecnologia de Read Mapping destaca en aquest tipus de tècniques i es caracteritza per manegar una gran quantitat de dades. Hadoop, el framework d’Apache per aplicacions intensives de dades sota el paradigma Map Reduce, resulta un aliat perfecte per aquest tipus de tecnologia i ha sigut l’opció escollida per a realitzar aquest projecte. Durant tot el treball es realitza l’estudi, l’anàlisi i les experimentacions necessàries per aconseguir un Algorisme Genètic innovador que utilitzi tot el potencial de Hadoop.

Alineamiento de secuencias genéticas en procesadores multicore

Este trabajo analiza el rendimiento del algoritmo de alineamiento de secuencias conocido como Needleman-Wunsch, sobre 3 sistemas de cómputo multiprocesador diferentes. Se analiza y se codifica el algoritmo serie usando el lenguaje de programación C y se plantean una serie de optimizaciones con la finalidad de minimizar el volumen y el tiempo de cómputo. Posteriormente, se realiza un análisis de las prestaciones del programa sobre los diferentes sistemas de cómputo. En la segunda parte del trabajo, se paraleliza el algoritmo serie y se codifica ayudándonos de OpenMP. El resultado son dos variantes del programa que difieren en la relación entre la cantidad de cómputo y la de comunicación. En la primera variante, la comunicación entre procesadores es poco frecuente y se realiza tras largos periodos de ejecución (granularidad gruesa). En cambio, en la segunda variante las tareas individuales son relativamente pequeñas en término de tiempo de ejecución y la comunicación entre los procesadores es frecuente (granularidad fina). Ambas variantes se ejecutan y analizan en arquitecturas multicore que explotan el paralelismo a nivel de thread. Los resultados obtenidos muestran la importancia de entender y saber analizar el efecto del multicore y multithreading en el rendimiento.

Sistema de reconeixement de cares basat en múltiples vistes

En aquest projecte es proposa un algorisme de detecció de pell que introdueix el veïnatge a l’hora de classificar píxels. Partim d’un espai de color invariant après a partir de múltiples vistes i introduïm la influència del veïnatge mitjançant camps aleatoris de Markov. A partir dels experiments realitzats podem concloure que la inclusió del veïnatge en el procés de classificació de píxels millora significativament els resultats de detecció.

Optimizador de operarios industriales

Este es un proyecto orientado hacia la optimización de actividades productivas en plantas industriales de empresas pymes (pequeñas y medianas empresas) mediante entornos de programación. Más concretamente la idea es realizar una aplicación que permita realizar planificaciones eficientes de cómo distribuir el trabajo a los operarios de producción dentro de una planta industrial convencional. Dichas plantas disponen de una serie de recursos, máquinas, que junto a su plantilla de trabajadores deben realizar las diferentes órdenes de fabricación. Estas tareas se han de poder realizar dentro de un marco de tiempo aceptable y a la vez adecuado al servicio que desea dar la planta a sus clientes. Por tal de abarcar de forma correcta este problema se distribuye el proyecto final de carrera en tres bloques principales: El primero de ellos es buscar un algoritmo/s que permita encontrar una solución aceptable, una buena solución. En segundo lugar realizar un estudio de los datos necesarios para poder llevar a cabo dicho algoritmo y diseñar una base de datos que disponga de la información adecuada para la organización de los recursos. Seguidamente, el programa que ejecutará la planificación del conjunto de órdenes de fabricación de la planta y su evaluación del nivel de eficiencia de la solución propuesta. El programa será realizado en el lenguaje de programación Java. Y finalmente, la presentación de los resultados y la bondad de la heurística desarrollada.

Intercanvi d'energia intel·ligent

El projecte d’intercanvi d’energia intel·ligent defensa la idea que és possible un nou model energètic. Aquest nou model pretén aprofitar al màxim possible els recursos energètics que provenen de fonts d’energies renovables i consisteix en la integració de xarxa elèctrica i telecomunicacions en la que usuaris són consumidors i a l’hora productors d’energia elèctrica mitjançant els seus propis sistemes de generació basats en energies renovables, amb la finalitat d’adaptar la demanda a l’oferta. El projecte desenvolupa la part que s’encarrega de fer aquesta gestió de repartiment i intercanvi d’electricitat entre els usuaris, utilitzant les politiques de gestió de processos per una CPU. Per això s’ha fet una adaptació dels algorismes que utilitzen els sistemes operatius a l’àmbit de la xarxa d’intercanvi. Per comprovar els resultats d’aquest estudi, s’han fet les simulacions del model proposat en un entorn web (www.energiainteligent.com) per tal de poder fer una anàlisi dels resultats.

Singling out individual inventors from patent data

An increasing number of studies have sprung up in recent years seeking to identify individual inventors from patent data. Different heuristics have been suggested to use their names and other information disclosed in patent documents in order to find out “who is who” in patents. This paper contributes to this literature by setting forth a methodology to identify them using patents applied to the European Patent Office (EPO hereafter). As in the large part of this literature, we basically follow a three-steps procedure: (1) the parsing stage, aimed at reducing the noise in the inventor’s name and other fields of the patent; (2) the matching stage, where name matching algorithms are used to group possible similar names; (3) the filtering stage, where additional information and different scoring schemes are used to filter out these potential same inventors. The paper includes some figures resulting of applying the algorithms to the set of European inventors applying to the EPO for a large period of time.

Hard instances of algorithms and proof systems

"Vegeu el resum a l'inici del document del fitxer adjunt."

Programació d'aplicacions bioinformàtiques

Avui en dia la biologia aporta grans quantitats de dades que només la informàtica pot tractar. Les aplicacions bioinformàtiques són la més important eina d’anàlisi i comparació que tenim per entendre la vida i aconseguir desxifrar aquestes dades. Aquest projecte centra el seu esforç en l’estudi de les aplicacions dedicades a l’alineament de seqüències genètiques, i més concretament a dos algoritmes, basats en programació dinàmica i òptims: el Needleman&Wunsch i el Smith&Waterman. Amb l’objectiu de millorar el rendiment d’aquests algoritmes per a alineaments de seqüències grans, proposem diferents versions d’implementació. Busquem millorar rendiments en temps i espai. Per a aconseguir millorar els resultats aprofitem el paral·lelisme. Els resultats dels anàlisis de les versions els comparem per obtenir les dades necessàries per valorar cost, guany i rendiment.

Bioinformática: interfaz web para estudiar el efecto de diferentes condiciones sobre la expresión de los genes

El trabajo realizado se divide en dos bloques bien diferenciados, ambos relacionados con el análisis de microarrays. El primer bloque consiste en agrupar las condiciones muestrales de todos los genes en grupos o clústers. Estas agrupaciones se obtienen al aplicar directamente sobre la microarray los siguientes algoritmos de agrupación: SOM,PAM,SOTA,HC y al aplicar sobre la microarray escalada con PC y MDS los siguientes algoritmos: SOM,PAM,SOTA,HC y K-MEANS. El segundo bloque consiste en realizar una búsqueda de genes basada en los intervalos de confianza de cada clúster de la agrupación activa. Las condiciones de búsqueda ajustadas por el usuario se validan para cada clúster respecto el valor basal 0 y respecto el resto de clústers, para estas validaciones se usan los intervalos de confianza. Estos dos bloques se integran en una aplicación web ya existente, el applet PCOPGene, alojada en el servidor: http://revolutionresearch.uab.es.

An approximation algorithm for #k-SAT

"Vegeu el resum a l'inici del document del fitxer adjunt"

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics) in graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the innite d-regular tree. ore recently Sly [8] (see also [1]) showed that this is optimal in the sense that if here is an FPRAS for the hard-core partition function on graphs of maximum egree d for activities larger than the critical activity on the innite d-regular ree then NP = RP. In this paper we extend Weitz's approach to derive a deterministic fully polynomial approximation scheme for the partition function of general two-state anti-ferromagnetic spin systems on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. his in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al [7] to the case of general two-state anti-ferromagnetic spin systems.

Textural classification of land cover using support vector machines: an empirical comparison with parametric, non parametric and hybrid classifiers in the Bolivian Amazon

Land cover classification is a key research field in remote sensing and land change science as thematic maps derived from remotely sensed data have become the basis for analyzing many socio-ecological issues. However, land cover classification remains a difficult task and it is especially challenging in heterogeneous tropical landscapes where nonetheless such maps are of great importance. The present study aims to establish an efficient classification approach to accurately map all broad land cover classes in a large, heterogeneous tropical area of Bolivia, as a basis for further studies (e.g., land cover-land use change). Specifically, we compare the performance of parametric (maximum likelihood), non-parametric (k-nearest neighbour and four different support vector machines - SVM), and hybrid classifiers, using both hard and soft (fuzzy) accuracy assessments. In addition, we test whether the inclusion of a textural index (homogeneity) in the classifications improves their performance. We classified Landsat imagery for two dates corresponding to dry and wet seasons and found that non-parametric, and particularly SVM classifiers, outperformed both parametric and hybrid classifiers. We also found that the use of the homogeneity index along with reflectance bands significantly increased the overall accuracy of all the classifications, but particularly of SVM algorithms. We observed that improvements in producer’s and user’s accuracies through the inclusion of the homogeneity index were different depending on land cover classes. Earlygrowth/degraded forests, pastures, grasslands and savanna were the classes most improved, especially with the SVM radial basis function and SVM sigmoid classifiers, though with both classifiers all land cover classes were mapped with producer’s and user’s accuracies of around 90%. Our approach seems very well suited to accurately map land cover in tropical regions, thus having the potential to contribute to conservation initiatives, climate change mitigation schemes such as REDD+, and rural development policies.

Búsqueda de ancentros comunes entre genomas de diferentes especies

La cerca de similituds entre regions de diferents genomes ofereix molta informació sobre les relaciones entre les especies d’aquest genomes. Es molt útil per a l’estudi de la conservació de gens d’una especia a un altre, de com les propietats d’un gen son assignades a un altre gen o de com es creen variacions en genomes diferents durant l’evolució d’aquestes especies. La finalitat d’aquest projecte es la creació d’una eina per a la cerca d’ancestres comuns de diferents especies basada en la comparació de la conservació entre regions dels genomes d’aquestes especies. Per a una comparació entre genomes mes eficaç una part important del projecte es destinarà a la creació d’una nova unitat de comparació. Aquestes noves unitats seran superestructures basades en agrupació dels MUMs existent per la mateixa comparació que anomenarem superMUMs. La aplicació final estarà disponible al servidor: http://revolutionresearch.uab.es