On the number of higher order Delaunay triangulations

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

Estudio sobre la extracción de puntos característicos en imágenes y sus aplicaciones

En aquest treball realitzem un estudi sobre la detecció y la descripció de punts característics, una tecnologia que permet extreure informació continguda en les imatges. Primerament presentem l'estat de l'art juntament amb una avaluació dels mètodes més rellevants. A continuació proposem els nous mètodes que hem creat de detecció i descripció, juntament amb l'algorisme òptim anomenat DART, el qual supera l'estat de l'art. Finalment mostrem algunes aplicacions on s'utilitzen els punts DART. Basant-se en l'aproximació de l'espai d'escales Gaussià, el detector proposat pot extreure punts de distint tamany invariants davant canvis en el punt de vista, la rotació i la iluminació. La reutilització de l'espai d'escales durant el procés de descripció, així com l'ús d'estructures simplificades i optimitzades, permeten realitzar tot el procediment en un temps computacional menor a l'obtingut fins al moment. Així s'aconsegueixen punts invariants i distingibles de forma ràpida, el qual permet la seva utilització en aplicacions com el seguiment d'objectes, la reconstrucció d'escenaris 3D i en motors de cerca visual.

Paraphrasing : scope and typology : a computational approach

This PhD project aims to study paraphrasing, initially understood as the different ways in which the same content is expressed linguistically. We will go into that concept in depth trying to define and delimit its scope more accurately. In that sense, we also aim to discover which kind of structures and phenomena it covers. Although there exist some paraphrasing typologies, the great majority of them only apply to English, and focus on lexical and syntactic transformations. Our intention is to go further into this subject and propose a paraphrasing typology for Spanish and Catalan combining lexical, syntactic, semantic and pragmatic knowledge. We apply a bottom-up methodology trying to collect evidence of this phenomenon from the data. For this purpose, we are initially using the Spanish Wikipedia as our corpus. The internal structure of this encyclopedia makes it a good resource for extracting paraphrasing examples for our investigation. This empirical approach will be complemented with the use of linguistic knowledge, and by comparing and contrasting our results to previously proposed paraphrasing typologies in order to enlarge the possible paraphrasing forms found in our corpus. The fact that the same content can be expressed in many different ways presents a major challenge for Natural Language Processing (NLP) applications. Thus, research on paraphrasing has recently been attracting increasing attention in the fields of NLP and Computational Linguistics. The results obtained in this investigation would be of great interest in many of these applications.

Bioinformática: identificar genes en una interfaz gráfica vía web para la comparación de genomas

Este trabajo desarrolla el proceso de diseño e implementación de una interfaz web que permite la exploración en detalle de las relaciones entre genomas completos. La interfaz permite la comparación simultánea de nueve genomas, representando en cada gráfica las relaciones entre cada par de genomas junto los genes identificados de cada uno de ellos. Es capaz de trabajar con genomas del dominio Eukaryota y se adapta a la capacidad de cómputo de la máquina cliente. La información representada son MUMs (Maximal Unique Matching, secuencia máxima y única encontrada en ambos genomas) y SuperMUMs (agrupación de MUMs mediante Approximate String Matching). Los datos son previamente calculados y accesibles desde un servidor web.

Aplicacions de reconeixement de la parla: sistemes de respeaking III

En aquest projecte es fa una introducció als reconeixedors de la parla, el seu funcionament i la seva base matemàtica. Un cop tots els conceptes han quedat clars, es mostra el mètode de creació que hem seguit per obtenir el nostre propi reconeixedor de la parla, utilitzant les eines HTK, en català. S’avaluen les seves virtuts i els seus defectes a través de diferents proves realitzades als seus components. A més a més, el projecte arrodoneix la feina implementant un sistema de dictat automàtic que explota el reconeixedor de la parla utilitzant Julius.

Eina gràfica per la creació d'autòmats per a la representació del llenguatge natural

Aquest projecte tracta la implementació d’una eina gràfica multiplataforma de creació i edició de gramàtiques electròniques per representar el Llenguatge Natural. És una eina per lingüistes i projectes com Spanish FrameNet Project amb la quan poden representar fàcilment transductors en un format més visual, les transicions es representen en forma de “caixes”, i guardar els resultats. S’han implementat varies opcions per crear una eina còmode i personalitzable per l’usuari amb funcionalitats enfocades a les seves necessitats com importar/exportar autòmats des d’una Expressió Regular. Es tracta l’implementació de tots els components que s’han necessitat per crear la GUI així com la seva funcionalitat.

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.