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ó.

Activin enhances skin tumourigenesis and malignant progression by inducing a pro-tumourigenic immune cell response.

Activin is an important orchestrator of wound repair, but its potential role in skin carcinogenesis has not been addressed. Here we show using different types of genetically modified mice that enhanced levels of activin in the skin promote skin tumour formation and their malignant progression through induction of a pro-tumourigenic microenvironment. This includes accumulation of tumour-promoting Langerhans cells and regulatory T cells in the epidermis. Furthermore, activin inhibits proliferation of tumour-suppressive epidermal γδ T cells, resulting in their progressive loss during tumour promotion. An increase in activin expression was also found in human cutaneous basal and squamous cell carcinomas when compared with control tissue. These findings highlight the parallels between wound healing and cancer, and suggest inhibition of activin action as a promising strategy for the treatment of cancers overexpressing this factor.

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.

Aplicación de la ingeniería del software sobre la herramienta MATE: Common y DMLib

Aquest projecte intenta implantar una metodologia de treball sobre MATE. MATE es una eina de sintonització d'aplicacions paral·leles sorgida de la tesis doctoral d'Anna Sikora a 2003. Vistos els resultats obtinguts, es va decidir donar un pas endavant i convertir-la en un producte software Open Source. Per fer-ho ha sigut necessari aplicar una serie d'estàndards i fer un proces de tests. En aquest treball s'ha creat part de la metodologia i s'han modificat dos dels mòduls principals.

Mutational analysis of cysteine-rich domains of the epithelium sodium channel (ENaC). Identification of cysteines essential for channel expression at the cell surface.

One of the characteristic features of the structure of the epithelial sodium channel family (ENaC) is the presence of two highly conserved cysteine-rich domains (CRD1 and CRD2) in the large extracellular loops of the proteins. We have studied the role of CRDs in the functional expression of rat alphabetagamma ENaC subunits by systematically mutating cysteine residues (singly or in combinations) into either serine or alanine. In the Xenopus oocyte expression system, mutations of two cysteines in CRD1 of alpha, beta, or gamma ENaC subunits led to a temperature-dependent inactivation of the channel. In CRD1, one of the cysteines of the rat alphaENaC subunit (Cys158) is homologous to Cys133 of the corresponding human subunit causing, when mutated to tyrosine (C133Y), pseudohypoaldosteronism type 1, a severe salt-loosing syndrome in neonates. In CRD2, mutation of two cysteines in alpha and beta but not in the gamma subunit also produced a temperature-dependent inactivation of the channel. The main features of the mutant cysteine channels are: (i) a decrease in cell surface expression of channel molecules that parallels the decrease in channel activity and (ii) a normal assembly or rate of degradation as assessed by nondenaturing co-immunoprecipitation of [35S]methionine-labeled channel protein. These data indicate that the two cysteines in CRD1 and CRD2 are not a prerequisite for subunit assembly and/or intrinsic channel activity. We propose that they play an essential role in the efficient transport of assembled channels to the plasma membrane.