Strong isomorphism reductions in complexity theory

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees.

Obtenció de jerarquies d'estats cel·lulars via web

Hi ha diversos mètodes d'anàlisi que duen a terme una agrupació global de la sèries de mostres de microarrays, com SelfOrganizing Maps, o que realitzen agrupaments locals tenint en compte només un subconjunt de gens coexpressats, com Biclustering, entre d'altres. En aquest projecte s'ha desenvolupat una aplicació web: el PCOPSamplecl, és una eina que pertany als mètodes d'agrupació (clustering) local, que no busca subconjunts de gens coexpresats (anàlisi de relacions linials), si no parelles de gens que davant canvis fenotípics, la seva relació d'expressió pateix fluctuacions. El resultats del PCOPSamplecl seràn les diferents distribucions finals de clusters i les parelles de gens involucrades en aquests canvis fenotípics. Aquestes parelles de gens podràn ser estudiades per trobar la causa i efecte del canvi fenotípic. A més, l'eina facilita l'estudi de les dependències entre les diferents distribucions de clusters que proporciona l'aplicació per poder estudiar la intersecció entre clusters o l'aparició de subclusters (2 clusters d'una mateixa agrupació de clusters poden ser subclusters d'altres clusters de diferents distribucions de clusters). L'eina és disponible al servidor: http://revolutionresearch.uab.es/

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.

Factores de rendimiento en aplicaciones híbridas

En el entorno actual, diversas ramas de las ciencias, tienen la necesidad de auxiliarse de la computación de altas prestaciones para la obtención de resultados a relativamente corto plazo. Ello es debido fundamentalmente, al alto volumen de información que necesita ser procesada y también al costo computacional que demandan dichos cálculos. El beneficio al realizar este procesamiento de manera distribuida y paralela, logra acortar los tiempos de espera en la obtención de los resultados y de esta forma posibilita una toma decisiones con mayor anticipación. Para soportar ello, existen fundamentalmente dos modelos de programación ampliamente extendidos: el modelo de paso de mensajes a través de librerías basadas en el estándar MPI, y el de memoria compartida con la utilización de OpenMP. Las aplicaciones híbridas son aquellas que combinan ambos modelos con el fin de aprovechar en cada caso, las potencialidades específicas del paralelismo en cada uno. Lamentablemente, la práctica ha demostrado que la utilización de esta combinación de modelos, no garantiza necesariamente una mejoría en el comportamiento de las aplicaciones. Por lo tanto, un análisis de los factores que influyen en el rendimiento de las mismas, nos beneficiaría a la hora de implementarlas pero también, sería un primer paso con el fin de llegar a predecir su comportamiento. Adicionalmente, supondría una vía para determinar que parámetros de la aplicación modificar con el fin de mejorar su rendimiento. En el trabajo actual nos proponemos definir una metodología para la identificación de factores de rendimiento en aplicaciones híbridas y en congruencia, la identificación de algunos factores que influyen en el rendimiento de las mismas.

The nature of the Cr-C bond: direct estimation of aromaticity in Fischer carbenes

Report for the scientific sojourn at the the Philipps-Universität Marburg, Germany, from september to december 2007. For the first, we employed the Energy-Decomposition Analysis (EDA) to investigate aromaticity on Fischer carbenes as it is related through all the reaction mechanisms studied in my PhD thesis. This powerful tool, compared with other well-known aromaticity indices in the literature like NICS, is useful not only for quantitative results but also to measure the degree of conjugation or hyperconjugation in molecules. Our results showed for the annelated benzenoid systems studied here, that electron density is more concentrated on the outer rings than in the central one. The strain-induced bond localization plays a major role as a driven force to keep the more substituted ring as the less aromatic. The discussion presented in this work was contrasted at different levels of theory to calibrate the method and ensure the consistency of our results. We think these conclusions can also be extended to arene chemistry for explaining aromaticity and regioselectivity reactions found in those systems.In the second work, we have employed the Turbomole program package and density-functionals of the best performance in the state of art, to explore reaction mechanisms in the noble gas chemistry. Particularly, we were interested in compounds of the form H--Ng--Ng--F (where Ng (Noble Gas) = Ar, Kr and Xe) and we investigated the relative stability of these species. Our quantum chemical calculations predict that the dixenon compound HXeXeF has an activation barrier for decomposition of 11 kcal/mol which should be large enough to identify the molecule in a low-temperature matrix. The other noble gases present lower activation barriers and therefore are more labile and difficult to be observable systems experimentally.

Desenvolupament de codis numèrics per a la resolució de fluxos turbulents en ordinadors paral·lels emprant discretitzacions tipus symmetry-preserving

Projecte de recerca elaborat a partir d’una estada a la University of Groningen, Holanda, entre 2007 i 2009. La simulació directa de la turbulència (DNS) és una eina clau dins de la mecànica de fluids computacional. Per una banda permet conèixer millor la física de la turbulència i per l'altra els resultats obtinguts són claus per el desenvolupament dels models de turbulència. No obstant, el DNS no és una tècnica vàlida per a la gran majoria d'aplicacions industrials degut al elevats costos computacionals. Per tant, és necessari cert grau de modelització de la turbulència. En aquest context, s'han introduïts importants millores basades en la modelització del terme convectiu (no lineal) emprant symmetry-preserving regularizations. En tracta de modificar adequadament el terme convectiu a fi de reduir la producció d'escales més i més petites (vortex-stretching) tot mantenint tots els invariants de les equacions originals. Fins ara, aquest models s'han emprat amb èxit per nombres de Rayleigh (Ra) relativament elevats. En aquest punt, disposar de resultats DNS per a configuracions més complexes i nombres de Ra més elevats és clau. En aquest contexte, s'han dut a terme simulacions DNS en el supercomputador MareNostrum d'una Differentially Heated Cavity amb Ra=1e11 i Pr=0.71 durant el primer any dels dos que consta el projecte. A més a més, s'ha adaptat el codi a fi de poder simular el fluxe al voltant d'un cub sobre una pared amb Re=10000. Aquestes simulacions DNS són les més grans fetes fins ara per aquestes configuracions i la seva correcta modelització és un gran repte degut la complexitat dels fluxes. Aquestes noves simulacions DNS estan aportant nous coneixements a la física de la turbulència i aportant resultats indispensables per al progrés de les modelitzacións tipus symmetry-preserving regularization.

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

High ACSL5 transcript levels associate with systemic lupus erythematosus and apoptosis in Jurkat T lymphocytes and peripheral blood cells

BACKGROUND: Systemic lupus erythematosus (SLE) is a prototypical autoimmune disease in which increased apoptosis and decreased apoptotic cells removal has been described as most relevant in the pathogenesis. Long-chain acyl-coenzyme A synthetases (ACSLs) have been involved in the immunological dysfunction of mouse models of lupus-like autoimmunity and apoptosis in different in vitro cell systems. The aim of this work was to assess among the ACSL isoforms the involvement of ACSL2, ACSL4 and ACSL5 in SLE pathogenesis. FINDINGS: With this end, we determined the ACSL2, ACSL4 and ACSL5 transcript levels in peripheral blood mononuclear cells (PBMCs) of 45 SLE patients and 49 healthy controls by quantitative real time-PCR (q-PCR). We found that patients with SLE had higher ACSL5 transcript levels than healthy controls [median (range), healthy controls =16.5 (12.3-18.0) vs. SLE = 26.5 (17.8-41.7), P = 3.9x10 E-5] but no differences were found for ACSL2 and ACSL4. In in vitro experiments, ACSL5 mRNA expression was greatly increased when inducing apoptosis in Jurkat T cells and PBMCs by Phorbol-Myristate-Acetate plus Ionomycin (PMA+Io). On the other hand, short interference RNA (siRNA)-mediated silencing of ACSL5 decreased induced apoptosis in Jurkat T cells up to the control levels as well as decreased mRNA expression of FAS, FASLG and TNF. CONCLUSIONS: These findings indicate that ACSL5 may play a role in the apoptosis that takes place in SLE. Our results point to ACSL5 as a potential novel functional marker of pathogenesis and a possible therapeutic target in SLE

Differential epipolar constraint in mobile robot egomotion estimation

The estimation of camera egomotion is a well established problem in computer vision. Many approaches have been proposed based on both the discrete and the differential epipolar constraint. The discrete case is mainly used in self-calibrated stereoscopic systems, whereas the differential case deals with a unique moving camera. The article surveys several methods for mobile robot egomotion estimation covering more than 0.5 million samples using synthetic data. Results from real data are also given

A survey addressing the fundamental matrix estimation problem

Epipolar geometry is a key point in computer vision and the fundamental matrix estimation is the only way to compute it. This article surveys several methods of fundamental matrix estimation which have been classified into linear methods, iterative methods and robust methods. All of these methods have been programmed and their accuracy analysed using real images. A summary, accompanied with experimental results, is given

Shape complexity based on mutual information

Shape complexity has recently received attention from different fields, such as computer vision and psychology. In this paper, integral geometry and information theory tools are applied to quantify the shape complexity from two different perspectives: from the inside of the object, we evaluate its degree of structure or correlation between its surfaces (inner complexity), and from the outside, we compute its degree of interaction with the circumscribing sphere (outer complexity). Our shape complexity measures are based on the following two facts: uniformly distributed global lines crossing an object define a continuous information channel and the continuous mutual information of this channel is independent of the object discretisation and invariant to translations, rotations, and changes of scale. The measures introduced in this paper can be potentially used as shape descriptors for object recognition, image retrieval, object localisation, tumour analysis, and protein docking, among others

Error and complexity of random walk Monte Carlo radiosity

The author studies the error and complexity of the discrete random walk Monte Carlo technique for radiosity, using both the shooting and gathering methods. The author shows that the shooting method exhibits a lower complexity than the gathering one, and under some constraints, it has a linear complexity. This is an improvement over a previous result that pointed to an O(n log n) complexity. The author gives and compares three unbiased estimators for each method, and obtains closed forms and bounds for their variances. The author also bounds the expected value of the mean square error (MSE). Some of the results obtained are also shown

Estudi hidrodinàmic per elements finits de diferents pales simètriques per a la impulsió a rem en banc fix

Actualment l’esport del rem només s’entén com a activitat de lleure o esport de competició.Dins del rem, hi ha una gran varietat de disciplines esportives; totes coincideixen en l’impuls d’una embarcació mitjançant un sistema de palanques simple. Es diferencien en dos grans grups: el banc mòbil i el banc fix. El banc mòbil disposa d’un seient sobre rodes que permet aprofitar la força de les cames per la impulsió, en canvi, en el banc fix, no hi ha desplaçament del seient, el que implica el treball del tors i braços. Un dels punts que tenen en comú tot el banc fix, és el disseny del seu rem; a diferènciadel banc mòbil on la pala pot tenir el disseny que es vulgui. En banc fix la pala del rem ha de ser simètrica i alineada amb la canya del rem. L’objectiu d’aquest projecte és l’anàlisi hidrodinàmic de diferents models de pales simètriques per tal de determinar el model més eficient, des del punt de vista hidrodinàmic, per a la impulsió de l’embarcació de banc fix. Així, es simularan virtualment diferents models de pales simètriques disponibles en el mercat com models prototipus amb un programa de dinàmica de fluids computacional. L’anàlisi dels resultats determinarà el model més eficient. En la realització del projecte, l’estudi hidrodinàmic es realitzarà de manera virtual a partir de la utilització de programes comercials de dinàmica de fluids. Així com també programes de disseny 3D i programes de mallat que siguin compatibles amb el programa de simulació a utilitzar. En el disseny s’utilitzaran programes com Autocad i Rhinoceros, després, en funció del disseny, utilitzarem un programa d’elements finits anomenat ICEM ANSYS que mallarà la geometria emprada. Finalment, la simulació s’efectuarà amb el programa ANSYS CFX. L’estudi no preveu el càlcul de resistència mecànica dels models ni la seva construcció

Disseny d’un programa que assisteix en la seqüenciació de peces de taller basats en mètodes heurístics

El GREP (grup de recerca de producte, procés i producció) de la UdG actualmentdisposa d’una eina informàtica desenvolupada en un PFC del 2003 que li permet fer la seqüenciació de la producció d’un taller mecànic amb un màxim de cinc productes, un nombre definit de possibles rutes de fabricació per a cada producte i tres màquines. Aquesta eina és molt resolutiva per a aquests casos, ja que estudia totes les possibilitats i les comprova una per una. No obstant aquest fet presenta una sèrie de limitacions com són el temps d’execució doncs al comprovar totes les seqüències té un elevat cost computacional i la rigidesa del sistema doncs no ens permet seqüenciar més productes ni més màquines. Per tal de donar solució a aquest problema es planteja generar una nova eina informàtica a partir de l’actual però que permeti seqüenciar més peces sense ocupar tanta memòria per així implementar-hi futures millores com el temps de preparació etc... Per a desenvolupar l’eina informàtica s’han utilitzat mètodes heurístics, concretament dos que són: algoritmes genètics i cerca TABU. Aquests mètodes destaquen perquè no busquen totes les combinacions possibles sinó que estudien una sèrie de combinacions i utilitzant mètodes de creuament i generació d’entorns busquen una solució