Assembling genes from predicted exons in linear time with dynamic programming

In a number of programs for gene structure prediction in higher eukaryotic genomic sequences, exon prediction is decoupled from gene assembly: a large pool of candidate exons is predicted and scored from features located in the query DNA sequence, and candidate genes are assembled from such a pool as sequences of nonoverlapping frame-compatible exons. Genes are scored as a function of the scores of the assembled exons, and the highest scoring candidate gene is assumed to be the most likely gene encoded by the query DNA sequence. Considering additive gene scoring functions, currently available algorithms to determine such a highest scoring candidate gene run in time proportional to the square of the number of predicted exons. Here, we present an algorithm whose running time grows only linearly with the size of the set of predicted exons. Polynomial algorithms rely on the fact that, while scanning the set of predicted exons, the highest scoring gene ending in a given exon can be obtained by appending the exon to the highest scoring among the highest scoring genes ending at each compatible preceding exon. The algorithm here relies on the simple fact that such highest scoring gene can be stored and updated. This requires scanning the set of predicted exons simultaneously by increasing acceptor and donor position. On the other hand, the algorithm described here does not assume an underlying gene structure model. Indeed, the definition of valid gene structures is externally defined in the so-called Gene Model. The Gene Model specifies simply which gene features are allowed immediately upstream which other gene features in valid gene structures. This allows for great flexibility in formulating the gene identification problem. In particular it allows for multiple-gene two-strand predictions and for considering gene features other than coding exons (such as promoter elements) in valid gene structures.

Gérard Grisey : la cuantificación temporal deducida de los procesos perceptivos

En el presente trabajo, tratamos diferentes perspectivas sobre la poética, estrategias compositivas y repercusión perceptiva del tiempo en la música de Gérard Grisey. En el primer capítulo, abordamos la concepción del tiempo como unidad y proporcionalidad duracional y su relación con otros parámetros musicales. A continuación, presentamos tres enfoques sobre el tiempo que emergen de la poética de Grisey y del análisis de sus obras: la ruptura con la proporcionalidad duracional y la relación entre tiempo y sonido, el concepto de cambio de escala temporal y la analogía entre tiempo y cosmos. En el segundo capítulo, proponemos tres categorías temporales basadas principalmente en el concepto de previsibilidad: tiempo no lineal, tiempo lineal y tiempo procesual. En el tercer y último capítulo, exponemos los fundamentos de la Teoría de la Información, su relación con el discurso de Grisey y su método de aplicación.

Approximating subtree distances between Phylogenies

We give a 5-approximation algorithm to the rooted Subtree-Prune-and-Regraft (rSPR) distance between two phylogenies, which was recently shown to be NP-complete by Bordewich and Semple [5]. This paper presents the first approximation result for this important tree distance. The algorithm follows a standard format for tree distances such as Rodrigues et al. [24] and Hein et al. [13]. The novel ideas are in the analysis. In the analysis, the cost of the algorithm uses a \cascading" scheme that accounts for possible wrong moves. This accounting is missing from previous analysis of tree distance approximation algorithms. Further, we show how all algorithms of this type can be implemented in linear time and give experimental results.

Propagation connectivity of random hypergraphs

We study the concept of propagation connectivity on random 3-uniform hypergraphs. This concept is inspired by a simple linear time algorithm for solving instances of certain constraint satisfaction problems. We derive upper and lower bounds for the propagation connectivity threshold, and point out some algorithmic implications.

Modeling of hybrid systems by piecewise decomposition

Piecewise linear models systems arise as mathematical models of systems in many practical applications, often from linearization for nonlinear systems. There are two main approaches of dealing with these systems according to their continuous or discrete-time aspects. We propose an approach which is based on the state transformation, more particularly the partition of the phase portrait in different regions where each subregion is modeled as a two-dimensional linear time invariant system. Then the Takagi-Sugeno model, which is a combination of local model is calculated. The simulation results show that the Alpha partition is well-suited for dealing with such a system

Subsampling the mean of heavy-tailed dependent observations

We establish the validity of subsampling confidence intervals for themean of a dependent series with heavy-tailed marginal distributions.Using point process theory, we study both linear and nonlinear GARCH-liketime series models. We propose a data-dependent method for the optimalblock size selection and investigate its performance by means of asimulation study.

Planning under partial observability by classical replanning: theory and experiments

Planning with partial observability can be formulated as a non-deterministic search problem in belief space. The problem is harder than classical planning as keeping track of beliefs is harder than keeping track of states, and searching for action policies is harder than searching for action sequences. In this work, we develop a framework for partial observability that avoids these limitations and leads to a planner that scales up to larger problems. For this, the class of problems is restricted to those in which 1) the non-unary clauses representing the uncertainty about the initial situation are nvariant, and 2) variables that are hidden in the initial situation do not appear in the body of conditional effects, which are all assumed to be deterministic. We show that such problems can be translated in linear time into equivalent fully observable non-deterministic planning problems, and that an slight extension of this translation renders the problem solvable by means of classical planners. The whole approach is sound and complete provided that in addition, the state-space is connected. Experiments are also reported.

A Gradient based algorithm for blind inversion of Wiener System using multi-variate score functions

A Wiener system is a linear time-invariant filter, followed by an invertible nonlinear distortion. Assuming that the input signal is an independent and identically distributed (iid) sequence, we propose an algorithm for estimating the input signal only by observing the output of the Wiener system. The algorithm is based on minimizing the mutual information of the output samples, by means of a steepest descent gradient approach.

Exact temporal evolution for some non-linear diffusion process

Exact solutions to FokkerPlanck equations with nonlinear drift are considered. Applications of these exact solutions for concrete models are studied. We arrive at the conclusion that for certain drifts we obtain divergent moments (and infinite relaxation time) if the diffusion process can be extended without any obstacle to the whole space. But if we introduce a potential barrier that limits the diffusion process, moments converge with a finite relaxation time.

A test of the predictive validity of non-linear QALY models using time trade-off utilities

This paper presents a test of the predictive validity of various classes ofQALY models (i.e., linear, power and exponential models). We first estimatedTTO utilities for 43 EQ-5D chronic health states and next these states wereembedded in health profiles. The chronic TTO utilities were then used topredict the responses to TTO questions with health profiles. We find that thepower QALY model clearly outperforms linear and exponential QALY models.Optimal power coefficient is 0.65. Our results suggest that TTO-based QALYcalculations may be biased. This bias can be avoided using a power QALY model.

Planificación de aplicaciones best-effort y soft real-time en NOWs

La aparición de nuevos tipos de aplicaciones, como vídeo bajo demanda, realidad virtual y videoconferencias entre otras, caracterizadas por la necesidad de cumplir sus deadlines. Este tipo de aplicaciones, han sido denominadas en la literatura aplicaciones soft-real time (SRT) periódicas. Este trabajo se centra en el problema de la planificación temporal de este nuevo tipo de aplicaciones en clusters no dedicados.

Scene classifier for real time road detection

L’objectiu principal del projecte és el de classificar escenes de carretera en funció del contingut de les imatges per així poder fer un desglossament sobre quin tipus de situació tenim en el moment. És important que fixem els paràmetres necessaris en funció de l’escenari en què ens trobem per tal de treure el màxim rendiment possible a cada un dels algoritmes. La seva funcionalitat doncs, ha de ser la d’avís i suport davant els diferents escenaris de conducció. És a dir, el resultat final ha de contenir un algoritme o aplicació capaç de classificar les imatges d’entrada en diferents tipus amb la màxima eficiència espacial i temporal possible. L’algoritme haurà de classificar les imatges en diferents escenaris. Els algoritmes hauran de ser parametritzables i fàcilment manejables per l’usuari. L’eina utilitzada per aconseguir aquests objectius serà el MATLAB amb les toolboxs de visió i xarxes neuronals instal·lades.

Gaussian estimates for the density of the non-linear stochastic heat equation in any space dimension

In this paper, we establish lower and upper Gaussian bounds for the probability density of the mild solution to the stochastic heat equation with multiplicative noise and in any space dimension. The driving perturbation is a Gaussian noise which is white in time with some spatially homogeneous covariance. These estimates are obtained using tools of the Malliavin calculus. The most challenging part is the lower bound, which is obtained by adapting a general method developed by Kohatsu-Higa to the underlying spatially homogeneous Gaussian setting. Both lower and upper estimates have the same form: a Gaussian density with a variance which is equal to that of the mild solution of the corresponding linear equation with additive noise.

Mètodes algebraics i de teoria de la prova per a la formalització del raonament vague

Projecte de recerca elaborat a partir d’una estada a la Università degli studi di Siena, Italy , entre 2007 i 2009. El projecte ha consistit en un estudi de la formalització lògica del raonament en presència de vaguetat amb els mètodes de la Lògica Algebraica i de la Teoria de la Prova. S'ha treballat fonamental en quatre direccions complementàries. En primer lloc, s'ha proposat un nou plantejament, més abstracte que el paradigma dominant fins ara, per l'estudi dels sistemes de lògica borrosa. Fins ara en l'estudi d'aquests sistemes l'atenció havia recaigut essencialment en l'obtenció de semàntiques basades en tnormes contínues (o almenys contínues per l'esquerra). En primer nivell de major abstracció hem estudiat les propietats de completesa de les lògiques borroses (tant proposicionals com de primer ordre) respecte de semàntiques definides sobre qualsevol cadena de valors de veritat, no necessàriament només sobre l'interval unitat dels nombres reals. A continuació, en un nivell encara més abstracte, s’ha pres l'anomenada jerarquia de Leibniz de la Lògica Algebraica Abstracta que classifica tots els sistemes lògics amb un bon comportament algebraic i s'ha expandit a una nova jerarquia (que anomenem implicacional) que permet definir noves classes de lògiques borroses que contenen quasi totes les conegudes fins ara. En segon lloc, s’ha continuat una línia d'investigació iniciada els darrers anys consistent en l'estudi de la veritat parcial com a noció sintàctica (és a dir, com a constants de veritat explícites en els sistemes de prova de les lògiques borroses). Per primer cop, s’ha considerat la semàntica racional per les lògiques proposicionals i la semàntica real i racional per les lògiques de primer ordre expandides amb constants. En tercer lloc, s’ha tractat el problema més fonamental del significat i la utilitat de les lògiques borroses com a modelitzadores de (part de) els fenòmens de la vaguetat en un darrer article de caràcter més filosòfic i divulgatiu, i en un altre més tècnic en què defensem la necessitat i presentem l'estat de l'art de l'estudi de les estructures algèbriques associades a les lògiques borroses. Finalment, s’ha dedicat la darrera part del projecte a l'estudi de la complexitat aritmètica de les lògiques borroses de primer ordre.

Time-series regression models to study the short-term effects of environmental factors on health

Time series regression models are especially suitable in epidemiology for evaluating short-term effects of time-varying exposures on health. The problem is that potential for confounding in time series regression is very high. Thus, it is important that trend and seasonality are properly accounted for. Our paper reviews the statistical models commonly used in time-series regression methods, specially allowing for serial correlation, make them potentially useful for selected epidemiological purposes. In particular, we discuss the use of time-series regression for counts using a wide range Generalised Linear Models as well as Generalised Additive Models. In addition, recently critical points in using statistical software for GAM were stressed, and reanalyses of time series data on air pollution and health were performed in order to update already published. Applications are offered through an example on the relationship between asthma emergency admissions and photochemical air pollutants