Segmentation and Clustering of Textual Sequences: a Typological Approach

The long term goal of this research is to develop a program able to produce an automatic segmentation and categorization of textual sequences into discourse types. In this preliminary contribution, we present the construction of an algorithm which takes a segmented text as input and attempts to produce a categorization of sequences, such as narrative, argumentative, descriptive and so on. Also, this work aims at investigating a possible convergence between the typological approach developed in particular in the field of text and discourse analysis in French by Adam (2008) and Bronckart (1997) and unsupervised statistical learning.

A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata

Two-way alternating automata were introduced by Vardi in order to study the satisfiability problem for the modal μ-calculus extended with backwards modalities. In this paper, we present a very simple proof by way of Wadge games of the strictness of the hierarchy of Motowski indices of two-way alternating automata over trees.

Cognitive Behavior Therapy for Obsessive-Compulsive Behavior in Children with Autism Spectrum Disorder: A Comparison of Hierarchical Linear Modelling and Visual Analysis

Behavioral researchers commonly use single subject designs to evaluate the effects of a given treatment. Several different methods of data analysis are used, each with their own set of methodological strengths and limitations. Visual inspection is commonly used as a method of analyzing data which assesses the variability, level, and trend both within and between conditions (Cooper, Heron, & Heward, 2007). In an attempt to quantify treatment outcomes, researchers developed two methods for analysing data called Percentage of Non-overlapping Data Points (PND) and Percentage of Data Points Exceeding the Median (PEM). The purpose of the present study is to compare and contrast the use of Hierarchical Linear Modelling (HLM), PND and PEM in single subject research. The present study used 39 behaviours, across 17 participants to compare treatment outcomes of a group cognitive behavioural therapy program, using PND, PEM, and HLM on three response classes of Obsessive Compulsive Behaviour in children with Autism Spectrum Disorder. Findings suggest that PEM and HLM complement each other and both add invaluable information to the overall treatment results. Future research should consider using both PEM and HLM when analysing single subject designs, specifically grouped data with variability.

The Impact of Labeling in Childhood on the Sense of Self of Young Adults

Research studies on labeling of children have either focused on the effects of formal labels on the lives of children with exceptionalities and mental health issues, or the effect of informal labeling by parents, peers and teachers on teenagers. The effects of informal labeling in childhood and its implications in later life or for one’s career choice have not yet been examined. This study adds to the growing research on informal labeling. The purpose of this qualitative study was to determine what negative effects informal labeling of children as deviant had on their lives. Data were gathered through semi-structured interviews conducted with seventeen young adults, between the ages of sixteen and thirty years, from a post-secondary institution and an organization for homeless youth. The results showed an initial negative impact on the lives of the young adults during their childhood and early teenage years but as they progressed into their late teens and early adulthood, most were able to overcome their negative labels suggesting resilience. There were no significant gender differences in the impact of the labels. The implications of the study for policy makers and parents are discussed as well as some recommendations for parents and practitioners are offered.

Assessing the Reproducibility of Clustering of Molecular Dynamics Conformations on Self-Organizing Maps

The goal of most clustering algorithms is to find the optimal number of clusters (i.e. fewest number of clusters). However, analysis of molecular conformations of biological macromolecules obtained from computer simulations may benefit from a larger array of clusters. The Self-Organizing Map (SOM) clustering method has the advantage of generating large numbers of clusters, but often gives ambiguous results. In this work, SOMs have been shown to be reproducible when the same conformational dataset is independently clustered multiple times (~100), with the help of the Cramérs V-index (C_v). The ability of C_v to determine which SOMs are reproduced is generalizable across different SOM source codes. The conformational ensembles produced from MD (molecular dynamics) and REMD (replica exchange molecular dynamics) simulations of the penta peptide Met-enkephalin (MET) and the 34 amino acid protein human Parathyroid Hormone (hPTH) were used to evaluate SOM reproducibility. The training length for the SOM has a huge impact on the reproducibility. Analysis of MET conformational data definitively determined that toroidal SOMs cluster data better than bordered maps due to the fact that toroidal maps do not have an edge effect. For the source code from MATLAB, it was determined that the learning rate function should be LINEAR with an initial learning rate factor of 0.05 and the SOM should be trained by a sequential algorithm. The trained SOMs can be used as a supervised classification for another dataset. The toroidal 10×10 hexagonal SOMs produced from the MATLAB program for hPTH conformational data produced three sets of reproducible clusters (27%, 15%, and 13% of 100 independent runs) which find similar partitionings to those of smaller 6×6 SOMs. The χ^2 values produced as part of the C_v calculation were used to locate clusters with identical conformational memberships on independently trained SOMs, even those with different dimensions. The χ^2 values could relate the different SOM partitionings to each other.

(A) Photoregulation of DNA Functions by Cyclic Azobenzene-tethered Oligonucleotides (B) Site-specific Fluorescent Labeling of DNA using Inverse Electron Demand Diels-Alder Reaction between trans-Cyclooctene Derivatives and BODIPY-Tetrazine Adducts

(A) Most azobenzene-based photoswitches require UV light for photoisomerization, which limit their applications in biological systems due to possible photodamage. Cyclic azobenzene derivatives, on the other hand, can undergo cis-trans isomerization when exposed to visible light. A shortened synthetic scheme was developed for the preparation of a building block containing cyclic azobenzene and D-threoninol (cAB-Thr). trans-Cyclic azobenzene was found to thermally isomerize back to the cis-form in a temperature-dependent manner. cAB-Thr was transformed into the corresponding phosphoramidite and subsequently incorporated into oligonucleotides by solid phase synthesis. Melting temperature measurement suggested that incorporation of cis-cAB into oligonucleotides destabilizes DNA duplexes, these findings corroborate with circular dichroism measurement. Finally, Fluorescent Energy Resonance Transfer experiments indicated that trans-cAB can be accommodated in DNA duplexes. (B) Inverse Electron Demand Diels-Alder reactions (IEDDA) between trans-olefins and tetrazines provide a powerful alternative to existing ligation chemistries due to its fast reaction rate, bioorthogonality and mutual orthogonality with other click reactions. In this project, an attempt was pursued to synthesize trans-cyclooctene building blocks for oligonucleotide labeling by reacting with BODIPY-tetrazine. Rel-(1R-4E-pR)-cyclooct-4-enol and rel-(1R,8S,9S,4E)-Bicyclo[6.1.0]non-4-ene-9-ylmethanol were synthesized and then transformed into the corresponding propargyl ether. Subsequent Sonogashira reactions between these propargylated compounds with DMT-protected 5-iododeoxyuridine failed to give the desired products. Finally a methodology was pursued for the synthesis of BODIPY-tetrazine conjugates that will be used in future IEDDA reactions with trans-cyclooctene modified oligonucleotides.

Annotation syntaxico-sémantique des actants en corpus spécialisé

L’annotation en rôles sémantiques est une tâche qui permet d’attribuer des étiquettes de rôles telles que Agent, Patient, Instrument, Lieu, Destination etc. aux différents participants actants ou circonstants (arguments ou adjoints) d’une lexie prédicative. Cette tâche nécessite des ressources lexicales riches ou des corpus importants contenant des phrases annotées manuellement par des linguistes sur lesquels peuvent s’appuyer certaines approches d’automatisation (statistiques ou apprentissage machine). Les travaux antérieurs dans ce domaine ont porté essentiellement sur la langue anglaise qui dispose de ressources riches, telles que PropBank, VerbNet et FrameNet, qui ont servi à alimenter les systèmes d’annotation automatisés. L’annotation dans d’autres langues, pour lesquelles on ne dispose pas d’un corpus annoté manuellement, repose souvent sur le FrameNet anglais. Une ressource telle que FrameNet de l’anglais est plus que nécessaire pour les systèmes d’annotation automatisé et l’annotation manuelle de milliers de phrases par des linguistes est une tâche fastidieuse et exigeante en temps. Nous avons proposé dans cette thèse un système automatique pour aider les linguistes dans cette tâche qui pourraient alors se limiter à la validation des annotations proposées par le système. Dans notre travail, nous ne considérons que les verbes qui sont plus susceptibles que les noms d’être accompagnés par des actants réalisés dans les phrases. Ces verbes concernent les termes de spécialité d’informatique et d’Internet (ex. accéder, configurer, naviguer, télécharger) dont la structure actancielle est enrichie manuellement par des rôles sémantiques. La structure actancielle des lexies verbales est décrite selon les principes de la Lexicologie Explicative et Combinatoire, LEC de Mel’čuk et fait appel partiellement (en ce qui concerne les rôles sémantiques) à la notion de Frame Element tel que décrit dans la théorie Frame Semantics (FS) de Fillmore. Ces deux théories ont ceci de commun qu’elles mènent toutes les deux à la construction de dictionnaires différents de ceux issus des approches traditionnelles. Les lexies verbales d’informatique et d’Internet qui ont été annotées manuellement dans plusieurs contextes constituent notre corpus spécialisé. Notre système qui attribue automatiquement des rôles sémantiques aux actants est basé sur des règles ou classificateurs entraînés sur plus de 2300 contextes. Nous sommes limités à une liste de rôles restreinte car certains rôles dans notre corpus n’ont pas assez d’exemples annotés manuellement. Dans notre système, nous n’avons traité que les rôles Patient, Agent et Destination dont le nombre d’exemple est supérieur à 300. Nous avons crée une classe que nous avons nommé Autre où nous avons rassemblé les autres rôles dont le nombre d’exemples annotés est inférieur à 100. Nous avons subdivisé la tâche d’annotation en sous-tâches : identifier les participants actants et circonstants et attribuer des rôles sémantiques uniquement aux actants qui contribuent au sens de la lexie verbale. Nous avons soumis les phrases de notre corpus à l’analyseur syntaxique Syntex afin d’extraire les informations syntaxiques qui décrivent les différents participants d’une lexie verbale dans une phrase. Ces informations ont servi de traits (features) dans notre modèle d’apprentissage. Nous avons proposé deux techniques pour l’identification des participants : une technique à base de règles où nous avons extrait une trentaine de règles et une autre technique basée sur l’apprentissage machine. Ces mêmes techniques ont été utilisées pour la tâche de distinguer les actants des circonstants. Nous avons proposé pour la tâche d’attribuer des rôles sémantiques aux actants, une méthode de partitionnement (clustering) semi supervisé des instances que nous avons comparée à la méthode de classification de rôles sémantiques. Nous avons utilisé CHAMÉLÉON, un algorithme hiérarchique ascendant.

Clustering algorithms and shape factor methods to discriminate among small GTPase phenotypes using DIC image analysis.

Naïvement perçu, le processus d’évolution est une succession d’événements de duplication et de mutations graduelles dans le génome qui mènent à des changements dans les fonctions et les interactions du protéome. La famille des hydrolases de guanosine triphosphate (GTPases) similaire à Ras constitue un bon modèle de travail afin de comprendre ce phénomène fondamental, car cette famille de protéines contient un nombre limité d’éléments qui diffèrent en fonctionnalité et en interactions. Globalement, nous désirons comprendre comment les mutations singulières au niveau des GTPases affectent la morphologie des cellules ainsi que leur degré d’impact sur les populations asynchrones. Mon travail de maîtrise vise à classifier de manière significative différents phénotypes de la levure Saccaromyces cerevisiae via l’analyse de plusieurs critères morphologiques de souches exprimant des GTPases mutées et natives. Notre approche à base de microscopie et d’analyses bioinformatique des images DIC (microscopie d’interférence différentielle de contraste) permet de distinguer les phénotypes propres aux cellules natives et aux mutants. L’emploi de cette méthode a permis une détection automatisée et une caractérisation des phénotypes mutants associés à la sur-expression de GTPases constitutivement actives. Les mutants de GTPases constitutivement actifs Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V ont été analysés avec succès. En effet, l’implémentation de différents algorithmes de partitionnement, permet d’analyser des données qui combinent les mesures morphologiques de population native et mutantes. Nos résultats démontrent que l’algorithme Fuzzy C-Means performe un partitionnement efficace des cellules natives ou mutantes, où les différents types de cellules sont classifiés en fonction de plusieurs facteurs de formes cellulaires obtenus à partir des images DIC. Cette analyse démontre que les mutations Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V induisent respectivement des phénotypes amorphe, allongé, rond et large qui sont représentés par des vecteurs de facteurs de forme distincts. Ces distinctions sont observées avec différentes proportions (morphologie mutante / morphologie native) dans les populations de mutants. Le développement de nouvelles méthodes automatisées d’analyse morphologique des cellules natives et mutantes s’avère extrêmement utile pour l’étude de la famille des GTPases ainsi que des résidus spécifiques qui dictent leurs fonctions et réseau d’interaction. Nous pouvons maintenant envisager de produire des mutants de GTPases qui inversent leur fonction en ciblant des résidus divergents. La substitution fonctionnelle est ensuite détectée au niveau morphologique grâce à notre nouvelle stratégie quantitative. Ce type d’analyse peut également être transposé à d’autres familles de protéines et contribuer de manière significative au domaine de la biologie évolutive.

Distributed conditional computation

L'objectif de cette thèse est de présenter différentes applications du programme de recherche de calcul conditionnel distribué. On espère que ces applications, ainsi que la théorie présentée ici, mènera à une solution générale du problème d'intelligence artificielle, en particulier en ce qui a trait à la nécessité d'efficience. La vision du calcul conditionnel distribué consiste à accélérer l'évaluation et l'entraînement de modèles profonds, ce qui est très différent de l'objectif usuel d'améliorer sa capacité de généralisation et d'optimisation. Le travail présenté ici a des liens étroits avec les modèles de type mélange d'experts. Dans le chapitre 2, nous présentons un nouvel algorithme d'apprentissage profond qui utilise une forme simple d'apprentissage par renforcement sur un modèle d'arbre de décisions à base de réseau de neurones. Nous démontrons la nécessité d'une contrainte d'équilibre pour maintenir la distribution d'exemples aux experts uniforme et empêcher les monopoles. Pour rendre le calcul efficient, l'entrainement et l'évaluation sont contraints à être éparse en utilisant un routeur échantillonnant des experts d'une distribution multinomiale étant donné un exemple. Dans le chapitre 3, nous présentons un nouveau modèle profond constitué d'une représentation éparse divisée en segments d'experts. Un modèle de langue à base de réseau de neurones est construit à partir des transformations éparses entre ces segments. L'opération éparse par bloc est implémentée pour utilisation sur des cartes graphiques. Sa vitesse est comparée à deux opérations denses du même calibre pour démontrer le gain réel de calcul qui peut être obtenu. Un modèle profond utilisant des opérations éparses contrôlées par un routeur distinct des experts est entraîné sur un ensemble de données d'un milliard de mots. Un nouvel algorithme de partitionnement de données est appliqué sur un ensemble de mots pour hiérarchiser la couche de sortie d'un modèle de langage, la rendant ainsi beaucoup plus efficiente. Le travail présenté dans cette thèse est au centre de la vision de calcul conditionnel distribué émis par Yoshua Bengio. Elle tente d'appliquer la recherche dans le domaine des mélanges d'experts aux modèles profonds pour améliorer leur vitesse ainsi que leur capacité d'optimisation. Nous croyons que la théorie et les expériences de cette thèse sont une étape importante sur la voie du calcul conditionnel distribué car elle cadre bien le problème, surtout en ce qui concerne la compétitivité des systèmes d'experts.

SPATIAL CLUSTERING ALGORITHMS-AN OVERVIEW.

An Overview of known spatial clustering algorithms The space of interest can be the two-dimensional abstraction of the surface of the earth or a man-made space like the layout of a VLSI design, a volume containing a model of the human brain, or another 3d-space representing the arrangement of chains of protein molecules. The data consists of geometric information and can be either discrete or continuous. The explicit location and extension of spatial objects define implicit relations of spatial neighborhood (such as topological, distance and direction relations) which are used by spatial data mining algorithms. Therefore, spatial data mining algorithms are required for spatial characterization and spatial trend analysis. Spatial data mining or knowledge discovery in spatial databases differs from regular data mining in analogous with the differences between non-spatial data and spatial data. The attributes of a spatial object stored in a database may be affected by the attributes of the spatial neighbors of that object. In addition, spatial location, and implicit information about the location of an object, may be exactly the information that can be extracted through spatial data mining

Detection of Flock Movement in Spatio-Temporal Database using Clustering Techniques - an Experience

In this paper, moving flock patterns are mined from spatio- temporal datasets by incorporating a clustering algorithm. A flock is defined as the set of data that move together for a certain continuous amount of time. Finding out moving flock patterns using clustering algorithms is a potential method to find out frequent patterns of movement in large trajectory datasets. In this approach, SPatial clusteRing algoRithm thrOugh sWarm intelligence (SPARROW) is the clustering algorithm used. The advantage of using SPARROW algorithm is that it can effectively discover clusters of widely varying sizes and shapes from large databases. Variations of the proposed method are addressed and also the experimental results show that the problem of scalability and duplicate pattern formation is addressed. This method also reduces the number of patterns produced

Spectral clustering independent component analysis for tissue classification from brain MRI

A spectral angle based feature extraction method, Spectral Clustering Independent Component Analysis (SC-ICA), is proposed in this work to improve the brain tissue classification from Magnetic Resonance Images (MRI). SC-ICA provides equal priority to global and local features; thereby it tries to resolve the inefficiency of conventional approaches in abnormal tissue extraction. First, input multispectral MRI is divided into different clusters by a spectral distance based clustering. Then, Independent Component Analysis (ICA) is applied on the clustered data, in conjunction with Support Vector Machines (SVM) for brain tissue analysis. Normal and abnormal datasets, consisting of real and synthetic T1-weighted, T2-weighted and proton density/fluid-attenuated inversion recovery images, were used to evaluate the performance of the new method. Comparative analysis with ICA based SVM and other conventional classifiers established the stability and efficiency of SC-ICA based classification, especially in reproduction of small abnormalities. Clinical abnormal case analysis demonstrated it through the highest Tanimoto Index/accuracy values, 0.75/98.8%, observed against ICA based SVM results, 0.17/96.1%, for reproduced lesions. Experimental results recommend the proposed method as a promising approach in clinical and pathological studies of brain diseases

Small World Folksonomies: Clustering in Tri-Partite Hypergraphs

Many recent Web 2.0 resource sharing applications can be subsumed under the "folksonomy" moniker. Regardless of the type of resource shared, all of these share a common structure describing the assignment of tags to resources by users. In this report, we generalize the notions of clustering and characteristic path length which play a major role in the current research on networks, where they are used to describe the small-world effects on many observable network datasets. To that end, we show that the notion of clustering has two facets which are not equivalent in the generalized setting. The new measures are evaluated on two large-scale folksonomy datasets from resource sharing systems on the web.

Protein-Expressions-Analysen zur Etablierung prädiktiver Biomarker bei der Behandlung fortgeschrittener Tumoren der Mamma und der Prostata

Aktuelle Entwicklungen auf dem Gebiet der zielgerichteten Therapie zur Behandlung maligner Erkrankungen erfordern neuartige Verfahren zur Diagnostik und Selektion geeigneter Patienten. So ist das Ziel der vorliegenden Arbeit die Identifizierung neuer Zielmoleküle, die die Vorhersage eines Therapieerfolges mit targeted drugs ermöglichen. Besondere Aufmerksamkeit gilt dem humanisierten monoklonalen Antikörper Trastuzumab (Herceptin), der zur Therapie Her-2 überexprimierender, metastasierter Mammakarzinome eingesetzt wird. Jüngste Erkenntnisse lassen eine Anwendung dieses Medikamentes in der Behandlung des Hormon-unabhängigen Prostatakarzinoms möglich erscheinen. Therapie-beeinflussende Faktoren werden in der dem Rezeptor nachgeschalteten Signaltransduktion oder Veränderungen des Rezeptors selbst vermutet. Mittels Immunhistochemie wurden die Expressions- und Aktivierungsniveaus verschiedener Proteine der Her-2-assoziierten Signaltransduktion ermittelt; insgesamt wurden 37 molekulare Marker untersucht. In Formalin fixierte und in Paraffin eingebettete korrespondierende Normal- und Tumorgewebe von 118 Mammakarzinom-Patientinnen sowie 78 Patienten mit Prostatakarzinom wurden in TMAs zusammengefasst. Die in Zusammenarbeit mit erfahrenen Pathologen ermittelten Ergebnisse dienten u.a. als Grundlage für zweidimensionales, unsupervised hierarchisches clustering. Ergebnis dieser Analysen war für beide untersuchten Tumorentitäten die Möglichkeit einer Subklassifizierung der untersuchten Populationen nach molekularen Eigenschaften. Hierbei zeigten sich jeweils neue Möglichkeiten zur Anwendung zielgerichteter Therapien, deren Effektivität Inhalt weiterführender Studien sein könnte. Zusätzlich wurden an insgesamt 43 Frischgeweben die möglichen Folgen des sog. shedding untersucht. Western Blot-basierte Untersuchungen zeigten hierbei die Möglichkeit der Selektion von Patienten aufgrund falsch-positiver Befunde in der derzeit als Standard geltenden Diagnostik. Zusätzlich konnte durch Vergleich mit einer Herceptin-sensitiven Zelllinie ein möglicher Zusammenhang eines Therapieerfolges mit dem Phosphorylierungs-/ Aktivierungszustand des Rezeptors ermittelt werden. Fehlende klinische Daten zum Verlauf der Erkrankung und Therapie der untersuchten Patienten lassen keine Aussagen über die tatsächliche Relevanz der ermittelten Befunde zu. Dennoch verdeutlichen die erhaltenen Resultate eindrucksvoll die Komplexität der molekularen Vorgänge, die zu einem Krebsgeschehen führen und damit Auswirkungen auf die Wirksamkeit von targeted drugs haben können. Entwicklungen auf dem Gebiet der zielgerichteten Therapie erfordern Verbesserungen auf dem Gebiet der Diagnostik, die die sichere Selektion geeigneter Patienten erlauben. Die Zukunft der personalisierten, zielgerichteten Behandlung von Tumorerkrankungen wird verstärkt von molekularen Markerprofilen hnlich den hier vorgestellten Daten beeinflusst werden.