Derivation of Context-free Stochastic L-Grammar Rules for Promoter Sequence Modeling Using Support Vector Machine

Formal grammars can used for describing complex repeatable structures such as DNA sequences. In this paper, we describe the structural composition of DNA sequences using a context-free stochastic L-grammar. L-grammars are a special class of parallel grammars that can model the growth of living organisms, e.g. plant development, and model the morphology of a variety of organisms. We believe that parallel grammars also can be used for modeling genetic mechanisms and sequences such as promoters. Promoters are short regulatory DNA sequences located upstream of a gene. Detection of promoters in DNA sequences is important for successful gene prediction. Promoters can be recognized by certain patterns that are conserved within a species, but there are many exceptions which makes the promoter recognition a complex problem. We replace the problem of promoter recognition by induction of context-free stochastic L-grammar rules, which are later used for the structural analysis of promoter sequences. L-grammar rules are derived automatically from the drosophila and vertebrate promoter datasets using a genetic programming technique and their fitness is evaluated using a Support Vector Machine (SVM) classifier. The artificial promoter sequences generated using the derived L- grammar rules are analyzed and compared with natural promoter sequences.

Context-free and context-sensitive dynamics in recurrent neural networks

Continuous-valued recurrent neural networks can learn mechanisms for processing context-free languages. The dynamics of such networks is usually based on damped oscillation around fixed points in state space and requires that the dynamical components are arranged in certain ways. It is shown that qualitatively similar dynamics with similar constraints hold for a(n)b(n)c(n), a context-sensitive language. The additional difficulty with a(n)b(n)c(n), compared with the context-free language a(n)b(n), consists of 'counting up' and 'counting down' letters simultaneously. The network solution is to oscillate in two principal dimensions, one for counting up and one for counting down. This study focuses on the dynamics employed by the sequential cascaded network, in contrast to the simple recurrent network, and the use of backpropagation through time. Found solutions generalize well beyond training data, however, learning is not reliable. The contribution of this study lies in demonstrating how the dynamics in recurrent neural networks that process context-free languages can also be employed in processing some context-sensitive languages (traditionally thought of as requiring additional computation resources). This continuity of mechanism between language classes contributes to our understanding of neural networks in modelling language learning and processing.

Structured RNAs in the ENCODE selected regions of the human genome.

Functional RNA structures play an important role both in the context of noncoding RNA transcripts as well as regulatory elements in mRNAs. Here we present a computational study to detect functional RNA structures within the ENCODE regions of the human genome. Since structural RNAs in general lack characteristic signals in primary sequence, comparative approaches evaluating evolutionary conservation of structures are most promising. We have used three recently introduced programs based on either phylogenetic-stochastic context-free grammar (EvoFold) or energy directed folding (RNAz and AlifoldZ), yielding several thousand candidate structures (corresponding to approximately 2.7% of the ENCODE regions). EvoFold has its highest sensitivity in highly conserved and relatively AU-rich regions, while RNAz favors slightly GC-rich regions, resulting in a relatively small overlap between methods. Comparison with the GENCODE annotation points to functional RNAs in all genomic contexts, with a slightly increased density in 3'-UTRs. While we estimate a significant false discovery rate of approximately 50%-70% many of the predictions can be further substantiated by additional criteria: 248 loci are predicted by both RNAz and EvoFold, and an additional 239 RNAz or EvoFold predictions are supported by the (more stringent) AlifoldZ algorithm. Five hundred seventy RNAz structure predictions fall into regions that show signs of selection pressure also on the sequence level (i.e., conserved elements). More than 700 predictions overlap with noncoding transcripts detected by oligonucleotide tiling arrays. One hundred seventy-five selected candidates were tested by RT-PCR in six tissues, and expression could be verified in 43 cases (24.6%).

La formació permanent en el context de l'Espai Europeu de la Formació Permanent

La importància de la formació permanent és indiscutible en qualsevol context laboral i molt especialment en les actuals circumstàncies de crisi econòmica mundial. Però en l'actual espai europeu d'educació superior (EEES), les tendències i els plans de formació contínua adquireixen una dimensió global, que supera o, millor dit, hauria de superar els plantejaments reduccionistes. Per això, la construcció i el desenvolupament de l'espai europeu de formació permanent, EEFP (Comissió de les Comunitats Europees, 2001a), ha d'entendre's com un procés que està immers en un teixit més ampli. Es tracta d'una acció en xarxa on és necessària la implicació de molts agents actius professionals i on la convergència, el reconeixement i la cohesió han de ser els seus màxims elements qualitatius

Defining Contexts in Context-Free Grammars

This thesis introduces an extension of Chomsky’s context-free grammars equipped with operators for referring to left and right contexts of strings.The new model is called grammar with contexts. The semantics of these grammars are given in two equivalent ways — by language equations and by logical deduction, where a grammar is understood as a logic for the recursive definition of syntax. The motivation for grammars with contexts comes from an extensive example that completely defines the syntax and static semantics of a simple typed programming language. Grammars with contexts maintain most important practical properties of context-free grammars, including a variant of the Chomsky normal form. For grammars with one-sided contexts (that is, either left or right), there is a cubic-time tabular parsing algorithm, applicable to an arbitrary grammar. The time complexity of this algorithm can be improved to quadratic,provided that the grammar is unambiguous, that is, it only allows one parsefor every string it defines. A tabular parsing algorithm for grammars withtwo-sided contexts has fourth power time complexity. For these grammarsthere is a recognition algorithm that uses a linear amount of space. For certain subclasses of grammars with contexts there are low-degree polynomial parsing algorithms. One of them is an extension of the classical recursive descent for context-free grammars; the version for grammars with contexts still works in linear time like its prototype. Another algorithm, with time complexity varying from linear to cubic depending on the particular grammar, adapts deterministic LR parsing to the new model. If all context operators in a grammar define regular languages, then such a grammar can be transformed to an equivalent grammar without context operators at all. This allows one to represent the syntax of languages in a more succinct way by utilizing context specifications. Linear grammars with contexts turned out to be non-trivial already over a one-letter alphabet. This fact leads to some undecidability results for this family of grammars

Quantification de la relation séquence-activité de l’ARN par prédiction de structure tridimensionnelle

Dans un premier temps, nous avons modélisé la structure d’une famille d’ARN avec une grammaire de graphes afin d’identifier les séquences qui en font partie. Plusieurs autres méthodes de modélisation ont été développées, telles que des grammaires stochastiques hors-contexte, des modèles de covariance, des profils de structures secondaires et des réseaux de contraintes. Ces méthodes de modélisation se basent sur la structure secondaire classique comparativement à nos grammaires de graphes qui se basent sur les motifs cycliques de nucléotides. Pour exemplifier notre modèle, nous avons utilisé la boucle E du ribosome qui contient le motif Sarcin-Ricin qui a été largement étudié depuis sa découverte par cristallographie aux rayons X au début des années 90. Nous avons construit une grammaire de graphes pour la structure du motif Sarcin-Ricin et avons dérivé toutes les séquences qui peuvent s’y replier. La pertinence biologique de ces séquences a été confirmée par une comparaison des séquences d’un alignement de plus de 800 séquences ribosomiques bactériennes. Cette comparaison a soulevée des alignements alternatifs pour quelques unes des séquences que nous avons supportés par des prédictions de structures secondaires et tertiaires. Les motifs cycliques de nucléotides ont été observés par les membres de notre laboratoire dans l'ARN dont la structure tertiaire a été résolue expérimentalement. Une étude des séquences et des structures tertiaires de chaque cycle composant la structure du Sarcin-Ricin a révélé que l'espace des séquences dépend grandement des interactions entre tous les nucléotides à proximité dans l’espace tridimensionnel, c’est-à-dire pas uniquement entre deux paires de bases adjacentes. Le nombre de séquences générées par la grammaire de graphes est plus petit que ceux des méthodes basées sur la structure secondaire classique. Cela suggère l’importance du contexte pour la relation entre la séquence et la structure, d’où l’utilisation d’une grammaire de graphes contextuelle plus expressive que les grammaires hors-contexte. Les grammaires de graphes que nous avons développées ne tiennent compte que de la structure tertiaire et négligent les interactions de groupes chimiques spécifiques avec des éléments extra-moléculaires, comme d’autres macromolécules ou ligands. Dans un deuxième temps et pour tenir compte de ces interactions, nous avons développé un modèle qui tient compte de la position des groupes chimiques à la surface des structures tertiaires. L’hypothèse étant que les groupes chimiques à des positions conservées dans des séquences prédéterminées actives, qui sont déplacés dans des séquences inactives pour une fonction précise, ont de plus grandes chances d’être impliqués dans des interactions avec des facteurs. En poursuivant avec l’exemple de la boucle E, nous avons cherché les groupes de cette boucle qui pourraient être impliqués dans des interactions avec des facteurs d'élongation. Une fois les groupes identifiés, on peut prédire par modélisation tridimensionnelle les séquences qui positionnent correctement ces groupes dans leurs structures tertiaires. Il existe quelques modèles pour adresser ce problème, telles que des descripteurs de molécules, des matrices d’adjacences de nucléotides et ceux basé sur la thermodynamique. Cependant, tous ces modèles utilisent une représentation trop simplifiée de la structure d’ARN, ce qui limite leur applicabilité. Nous avons appliqué notre modèle sur les structures tertiaires d’un ensemble de variants d’une séquence d’une instance du Sarcin-Ricin d’un ribosome bactérien. L’équipe de Wool à l’université de Chicago a déjà étudié cette instance expérimentalement en testant la viabilité de 12 variants. Ils ont déterminé 4 variants viables et 8 létaux. Nous avons utilisé cet ensemble de 12 séquences pour l’entraînement de notre modèle et nous avons déterminé un ensemble de propriétés essentielles à leur fonction biologique. Pour chaque variant de l’ensemble d’entraînement nous avons construit des modèles de structures tertiaires. Nous avons ensuite mesuré les charges partielles des atomes exposés sur la surface et encodé cette information dans des vecteurs. Nous avons utilisé l’analyse des composantes principales pour transformer les vecteurs en un ensemble de variables non corrélées, qu’on appelle les composantes principales. En utilisant la distance Euclidienne pondérée et l’algorithme du plus proche voisin, nous avons appliqué la technique du « Leave-One-Out Cross-Validation » pour choisir les meilleurs paramètres pour prédire l’activité d’une nouvelle séquence en la faisant correspondre à ces composantes principales. Finalement, nous avons confirmé le pouvoir prédictif du modèle à l’aide d’un nouvel ensemble de 8 variants dont la viabilité à été vérifiée expérimentalement dans notre laboratoire. En conclusion, les grammaires de graphes permettent de modéliser la relation entre la séquence et la structure d’un élément structural d’ARN, comme la boucle E contenant le motif Sarcin-Ricin du ribosome. Les applications vont de la correction à l’aide à l'alignement de séquences jusqu’au design de séquences ayant une structure prédéterminée. Nous avons également développé un modèle pour tenir compte des interactions spécifiques liées à une fonction biologique donnée, soit avec des facteurs environnants. Notre modèle est basé sur la conservation de l'exposition des groupes chimiques qui sont impliqués dans ces interactions. Ce modèle nous a permis de prédire l’activité biologique d’un ensemble de variants de la boucle E du ribosome qui se lie à des facteurs d'élongation.

On Alternating Non-Context-Free Grammars

We study several extensions of the notion of alternation from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. Thereby new grammatical characterizations are obtained for the class of languages that are accepted by alternating pushdown automata.

Offline grammar-based recognition of handwritten sentences

This paper proposes a sequential coupling of a Hidden Markov Model (HMM) recognizer for offline handwritten English sentences with a probabilistic bottom-up chart parser using Stochastic Context-Free Grammars (SCFG) extracted from a text corpus. Based on extensive experiments, we conclude that syntax analysis helps to improve recognition rates significantly.

On learning context-free and context-sensitive languages

The long short-term memory (LSTM) is not the only neural network which learns a context sensitive language. Second-order sequential cascaded networks (SCNs) are able to induce means from a finite fragment of a context-sensitive language for processing strings outside the training set. The dynamical behavior of the SCN is qualitatively distinct from that observed in LSTM networks. Differences in performance and dynamics are discussed.

Avaluació alternativa de l'assignatura "Geografia Humana" en el context de l'Espai Europeu d'Educació Superior

Aquest projecte ha aplicat algunes noves metodologies docents que seran imprescindibles per a la integració en l'EEES i, en particular, sistemes d'avaluació alternatius que puguin formar la base d'un sistema d'avaluació continuada per als continguts i adquisició d'habilitats que fins ara s'han aplegat en l'assignatura "Geografia Humana" de la llicenciatura de Geografia de la Universitat de Barcelona. A partir de la reflexió conjunta entre els membres de l’equip integrant del projecte sobre les competències i continguts que es desitja que adquireixi l'estudiant s'han dissenyat un conjunt de recursos per a l’avaluació: 1. exercicis individuals, destinats a valorar la capacitat d’estructurar idees, expressió escrita i gràfica, presentació etc. 2. treballs en equip, destinats a fomentar l’esperit de divisió del treball i de cooperació entre els estudiants i a mostrar el guany individual del treball col·lectiu. 3. proves objectives (tipus test), destinades a valorar l’adquisició de conceptes i de continguts bàsics. 4. preguntes d'autoavaluació, amb la finalitat que l’estudiant pugui fer el seu propi seguiment de l’adquisició de Coneixements. 5. qüestionaris d’autovaloració dels exercicis individuals i dels treballs en equip, amb l’objectiu que els alumnes reflexionin sobre el treball realitzat i que serveixin de base per a contrastar amb la valoració del professor. L’objectiu final és que l’estudiant pugui ser avaluat de manera contínua en el portafoli que recull el treball acumulat al llarg del curs. Tot i que el projecte s’ha basat en l’ús de l’eina dels “dossiers electrònics” de la UB, en el futur immediat els resultats obtinguts passaran a integrar-se en el Campus Virtual de la UB que utilitza la plataforma Moodle, les posibilitats tècniques de la qual permetran afegir una dimensió cooperativa més gran al treball avaluable (accés al treball dels grups, cooperació en la construcció de bases de dades, wikis editades pel conjunt de la classe etc.)

Polítiques docents en el context de l'EEES: oportunitats, dificultats i dilemes

El procés de convergència cap a l'Espai Europeu d' Educació Superior ha fet que les universitats s'hagin plantejat el repte de millorar la docència. Que amb l'EEES es vulgui fomentar un nou model d'ensenyança, ha suscitat opinions divergents, però hagués estat irresponsable no aprofitar el procés de canvi per anar al fons del tema docent. En el context actual, cercar com millorar els processos d'aprenentatge dels i de les estudiants suposa la necessitat de reflexionar col·lectivament sobre què i sobre com s'ha d'ensenyar a la universitat. Per tal d'afavorir un canvi de model que dugui a focalitzar la mirada en el procés d'aprenentatge de l'estudiant, cal debatre sobre els dilemes que sorgeixen quan els requeriments del nou model xoquen amb la cultura tradicionalment predominant entre el professorat universitari. En l'article es comenten alguns d'aquests dilemes.

Estudis sobre l'equitat de gènere en el context de l'educació infantil

La preocupació, com a docents universitaris i professionals de l’educació, per la manca de representació masculina en l’Educació Infantil, ha determinat que el nostre grup de recerca, centrat en estudis sobre la infància, es plantegés la realització de diferents estudis descriptius sobre l’equitat de gènere en aquesta etapa educativa. El primer estudi està centrat en l’home com a professional de l’Educació Infantil, com a estudiant i com a professio· nal en actiu. El segon estudi està centrat en l’avaluació de l’equitat de gènere en la pràctica educativa a l’escola, a Catalunya. I finalment, el tercer estudi, focalitza la seva mirada en el context cultural, portant a terme un estu· di paral·lel entre les realitats educatives de Catalunya i La Paz (Bolívia). Els resultats, malgrat que es detecten petits avenços en la presència del valor de l’equitat de gènere en els centres educatius, confirmen les dificultats, existents encara, per realitzar pràctiques de qualitat que puguin incidir vers un canvi social. Considerem que aquest canvi només s’aconseguirà quan es plantegi seriosament la necessitat d’aquest valor social i es treballi no solament des de l’escola, sinó també des de dinàmiques laborals, mediàtiques, familiars i socials. Aquest article recull les reflexiones que deriven de les tres recerques esmentades.

La dimensió social del moviment priscil·lianista en el context de l'antiguitat tardana. Heretgia, lluita contra la institucionalització eclesiàstica i contestació social.

L'any 385, Priscil·lià i la resta del grup priscil·lianista era condemnat a la ciutat de Trèveris i, fruit de la ingerència determinant de l'usurpador Magne Màxim, es convertia en el primer heretge ajusticiat pel poder secular en nom de l'Església. Els fets de Trèveris, per bé que van significar el final de la disputa entre dos grups amb posicions antagòniques vers les característiques del nou cristianisme institucionalitzat, no van aconseguir acabar amb el priscil·lianisme. El moviment perdurà, especialment a la província de la Gallaecia, i Priscil·lià va esdevenir venerat com màrtir. L'Església, mentrestant, es fracturava per culpa de la competència jurisdiccional entre la institució clerical i el poder imperial. Aquest treball intenta ser un estat de la qüestió respecte a la dimensió social d'un moviment que, més enllà de l'eterna discussió entre la seva possible catalogació com a ortodòxia o heterodòxia, intenta contextualitzar el priscil·lianisme en el seu marc històric i els convulsos anys de les transformacions de l'antiguitat tardana.

Experiències d'innovació docent en el context de l'EEES: estan preparats els nostres estudiants per al canvi cultural?

L’adaptació a l’EEES comporta un canvi cultural per a les universitats de l’estat espanyol. Desde la perspectiva de la gestió del canvi organitzatiu, marc teòric en el que es sustenta aquest estudi, aquest canvi es pot categoritzar com una reorientació segons la classificació de Nadler i Tushman (1995), donat que es tracta d’un canvi profund, discontinu i radical que s’anticipa als canvis i necessitats de l’entorn. Aquest tipus de canvis requereixen d’una introducció gradual, donat que la seva magnitud qüestiona la identitat i cultura de l’organització, generant moltes resistències. Des d’aquesta literatura es recomana fer un diagnòstic de les forces que afecten al canvi per tal de garantir el seu èxit. En aquest sentit, l’objectiu del present estudi és la identificació de les forces inhibidores del canvi cultural en la URV a partir d’una anàlisi introspectiva de les experiència d’innovació docent en l’assignatura de Pràctiques Integrades I. La metodologia utilitzada per aquest estudi ha estat la introspecció personal subjectiva (Brown & Reid , 1997; Patterson et al., 1998; Holbrook, 2005). L’experiència consistia en l’avaluació de certes competències de saber, saber fer, i saber ser i estar, a través de diferents mètodes d’avaluació docent. Les dades de satisfacció dels estudiants amb la metodologia de l’assignatura es van recollir mitjançant un informe d’opinió anònim i no estructurat que se’ls demanava entregar l’últim dia de classe. Opinions més generals sobre el canvi a l’EEES es van recollir a l’inici de l’assignatura a través d’una sessió de focus group amb cada un dels grups d’activitat de l’assignatura. Son múltiples els estudis que afirmen la conveniència de posar en pràctica noves metodologies i formes d’innovació docent que situïn a l’alumne com a eix central de l’aprenentatge i que avaluïn els seus aprenentatges en funció de l’adquisició de competències (Apodaca, 2006, Bautista et al. 2007, Margalef i Canabal, 2007, Brown i Glasner, 2003). No obstant, els resultats del nostre estudi posen en evidència que una de les principals forces inhibidores per a la gestió del canvi en el sistema docent universitari son les actituds dels alumnes, i en especial les d’aquells alumnes que combinen simultàniament estudis amb l’activitat laboral. Com a resultat de l’anàlisi, es proposen mesures per neutralitzar o eliminar les resistències identificades i es duu a terme una reflexió sobre com s’està duent a terme la gestió del canvi en la universitat