This thesis describes new gene finding methods for eukaryotic gene prediction. The current methods for deriving model parameters for gene prediction algorithms are based on curated or experimentally validated set of genes or gene elements. These training sets often require time and additional expert efforts especially for the species that are in the initial stages of genome sequencing. Unsupervised training allows determination of model parameters from anonymous genomic sequence with. The importance and the practical applicability of the unsupervised training is critical for ever growing rate of eukaryotic genome sequencing. Three distinct training procedures are developed for diverse group of eukaryotic species. GeneMark-ES is developed for species with strong donor and acceptor site signals such as Arabidopsis thaliana, Caenorhabditis elegans and Drosophila melanogaster. The second version of the algorithm, GeneMark-ES-2, introduces enhanced intron model to better describe the gene structure of fungal species with posses with relatively weak donor and acceptor splice sites and well conserved branch point signal. GeneMark-LE, semi-supervised training approach is designed for eukaryotic species with small number of introns. The results indicate that the developed unsupervised training methods perform well as compared to other training methods and as estimated from the set of genes supported by EST-to-genome alignments. Analysis of novel genomes reveals interesting biological findings and show that several candidates of under-annotated and over-annotated fungal species are present in the current set of annotated of fungal genomes.

The existence of new technologies, implemented in efficient platforms and workflows has made massive genotyping available to all fields of biology and medicine. Genetic analyses are no longer dominated by experimental work in laboratories, but rather the interpretation of the resulting data. When billions of data points representing thousands of individuals are available, efficient computational tools are required. The focus of this thesis is on developing models, methods and implementations for such tools. The first theme of the thesis is multi-dimensional scans for quantitative trait loci (QTL) in experimental crosses. By mating individuals from different lines, it is possible to gather data that can be used to pinpoint the genetic variation that influences specific traits to specific genome loci. However, it is natural to expect multiple genes influencing a single trait to interact. The thesis discusses model structure and model selection, giving new insight regarding under what conditions orthogonal models can be devised. The thesis also presents a new optimization method for efficiently and accurately locating QTL, and performing the permuted data searches needed for significance testing. This method has been implemented in a software package that can seamlessly perform the searches on grid computing infrastructures. The other theme in the thesis is the development of adapted optimization schemes for using hidden Markov models in tracing allele inheritance pathways, and specifically inferring haplotypes. The advances presented form the basis for more accurate and non-biased line origin probabilities in experimental crosses, especially multi-generational ones. We show that the new tools are able to reconstruct haplotypes and even genotypes in founder individuals and offspring alike, based on only unordered offspring genotypes. The tools can also handle larger populations than competing methods, resolving inheritance pathways and phase in much larger and more complex populations. Finally, the methods presented are also applicable to datasets where individual relationships are not known, which is frequently the case in human genetics studies. One immediate application for this would be improved accuracy for imputation of SNP markers within genome-wide association studies (GWAS). / eSSENCE

Detecting human actions using a camera has many possible applications in the security industry. When a human performs an action, his/her body goes through a signature sequence of poses. To detect these pose changes and hence the activities performed, a pattern recogniser needs to be built into the video system. Due to the temporal nature of the patterns, Hidden Markov Models (HMM), used extensively in speech recognition, were investigated. Initially a gesture recognition system was built using novel features. These features were obtained by approximating the contour of the foreground object with a polygon and extracting the polygon's vertices. A Gaussian Mixture Model (GMM) was fit to the vertices obtained from a few frames and the parameters of the GMM itself were used as features for the HMM. A more practical activity detection system using a more sophisticated foreground segmentation algorithm immune to varying lighting conditions and permanent changes to the foreground was then built. The foreground segmentation algorithm models each of the pixel values using clusters and continually uses incoming pixels to update the cluster parameters. Cast shadows were identified and removed by assuming that shadow regions were less likely to produce strong edges in the image than real objects and that this likelihood further decreases after colour segmentation. Colour segmentation itself was performed by clustering together pixel values in the feature space using a gradient ascent algorithm called mean shift. More robust features in the form of mesh features were also obtained by dividing the bounding box of the binarised object into grid elements and calculating the ratio of foreground to background pixels in each of the grid elements. These features were vector quantized to reduce their dimensionality and the resulting symbols presented as features to the HMM to achieve a recognition rate of 62% for an event involving a person writing on a white board. The recognition rate increased to 80% for the &quotseen" person sequences, i.e. the sequences of the person used to train the models. With a fixed lighting position, the lack of a shadow removal subsystem improved the detection rate. This is because of the consistent profile of the shadows in both the training and testing sequences due to the fixed lighting positions. Even with a lower recognition rate, the shadow removal subsystem was considered an indispensable part of a practical, generic surveillance system.

Thesis (M.Eng.(Computer Engineering))--University of Pretoria, 2008. / Summaries in Afrikaans and English. Includes bibliographical references (leaves 77-83).

O desafio de encontrar corretamente genes eucarioticos codificadores de proteinas nas sequencias genomicas e um problema em aberto. Neste trabalho, implementamos uma plata- forma, com o objetivo de melhorar a forma com que preditores de genes sao implementados e avaliados. Tres novas ferramentas foram implementadas: ToPS (Toolkit of Probabilistic Models of Sequences) foi o primeiro arcabouco orientado a objetos que fornece ferramentas para implementacao, manipulacao, e combinacao de modelos probabilisticos para representar sequencias de simbolos; MYOP (Make Your Own Predictor) e um sistema que tem como objetivo facilitar a construcao de preditores de genes; e SGEval utiliza grafos de splicing para comparar diferente anotacoes com eventos de splicing alternativos. Utilizamos nossas ferramentas para o desenvolvimentos de preditores de genes em onze genomas distintos: A. thaliana, C. elegans, Z. mays, P. falciparum, D. melanogaster, D. rerio, M. musculus, R. norvegicus, O. sativa, G. max e H. sapiens. Com esse desenvolvimento, estabelecemos um protocolo para implementacao de novos preditores. Alem disso, utilizando a nossa plata- forma, desenvolvemos um fluxo de trabalho para predicao de genes no projeto do genoma da cana de acucar, que ja foi utilizado em 109 sequencias de BAC geradas pelo BIOEN (FAPESP Bioenergy Program). / The challenge of correctly identify eukaryotic protein-coding genes in the genomic se- quences is an open problem. In this work, we implemented a plataform with the aim of improving the way that gene predictors are implemented and evaluated. ToPS (Toolkit of Probabilistic Models of Sequence) was the first object-oriented framework that provides tools for implementation, manipulation, and combination of probabilistic models that represent sequences of symbols. MYOP (Make Your Own Predictor) facilitates the construction of gene predictors. SGEval (Splicing Graph Evaluation) uses splicing graphs to compare dif- ferent annotations with alternative splicing events. We used our plataform to develop gene finders in eleven distinct genomes: A. thaliana, C. elegans, Z. mays, P. falciparum, D. me- lanogaster, D. rerio, M. musculus, R. norvegicus, O. sativa, G. max e H. sapiens. With this development, we established a protocol for implementing new gene predictors. In addi- tion, using our platform, we developed a pipeline to find genes in the 109 sugarcane BAC sequences produced by BIOEN (FAPESP Bioenergy Program).

Des projections réalisées sur les perspectives démographiques et financières de la dépendance prévoient, en France, une nette augmentation de la population des plus de 80 ans, accompagnée d'une multiplication par 2 du nombre de personnes âgées dépendantes entre 2010 et 2060. Afin de gérer l'augmentation du nombre de personnes âgées dépendantes, les EHPAD (Etablissement d'Hébergement pour Personne Agées Dépendantes) sont appelés à améliorer la prise en charge des résidents et à améliorer les conditions de travail du personnel soignant. C'est dans ce contexte, que nous avons développé un système de supervision permettant de détecter, via un ensemble de capteurs, des évolutions du comportement ou encore, le comportement anormal d'une personne âgée. La détection des comportements anormaux dans le cadre de la supervision est un sujet de recherche qui a été largement étudié dans la littérature ; ce qui n'est tout de même pas le cas de l'analyse des variations des activités de la vie de tous les jours, prenant en compte les spécificités du comportement de la personne au cours du temps. Ainsi, nous avons proposé un modèle de Markov, permettant d'apprendre, avec le moins d'a priori possible, le modèle de comportement habituel au sein de la chambre. Le modèle proposé a été testé sur des données acquises en Living Lab (GIS-Madonah). Nous avons également proposé une nouvelle approche pour calculer la distance entre deux modèles de Markov, afin d'évaluer l'évolution du comportement au cours du temps. Ces méthodes devront permettre, non seulement de déterminer la probabilité du comportement actuel de la personne par rapport à son comportement habituel ; mais également, de détecter des évolutions lentes du comportement de la personne. / Due to demographic changes, it is expected that the number of French having over 80 years will increase drastically and the number of dependent elderly people will grow twice between 2010 and 2060. To manage this increasing number of dependent elderly person, nursing homes are required to improve the care of residents and to improve the working conditions of health workers. In this context, we plan to develop a monitoring system, based on a set of sensors, to detect modifications in the behavior of a person, and unusual behavior. Detection of abnormal activities in smart homes is an important topic of research, unlike the detection of the evolutions of behavior, which take into account the specifics activities of the person in time. Thus, we proposed a Markov model which allow to learn the usual behavior in the room, with a reduced number of a priori. The model is try on data acquired on a Living Lab (GIS Madonah). We proposed a new method to compute the distance between two Markov models, to estimate the evolution of the behavior. These methods allow to compute the probability of the current activities with the usual behavior, and the slow evolutions of the behavior.

Les travaux de recherche développés dans cette thèse concernent la mise en oeuvre d'un système de vidéo surveillance intelligente en milieu hospitalier. Dans le contexte d'une application en unité de soins intensifs médicale, nous introduisons la notion originale de Boite Noire Médicale et nous proposons un nouveau système de monitoring visuel de Détection Automatique de Situations à risque et d'Alerte (DASA) basé sur un système de vidéosurveillance multi-caméra intelligent. L'objectif étant d'interpréter les flux d'informations visuelles et de détecter en temps réel les situations à risque afin de prévenir l'équipe médicale et ensuite archiver les évènements dans une base de donnée vidéo qui représente la Boite Noire Médicale. Le système d'interprétation est basé sur des algorithmes de reconnaissance de scénarios qui exploitent les Modèles de Markovs Cachés (MMCs). Une extension du modèle MMC standard est proposé afin de gérer la structure hiérarchique interne des scénarios et de contrôler la durée de chaque état du modèle markovien. La contribution majeure de ce travail repose sur l'intégration d'un raisonnement de type évènementiel, pour gérer la décision de reconnaissance en tenant compte des imperfections des informations disponibles. Les techniques de reconnaissance de scénarios proposées ont été testées et évaluées sur une base de séquences vidéo médicales et comparés aux modèles de Markov cachés probabilistiques classiques. / This thesis focuses on the study and the implementation of an intelligent visual monitoring system in hospitals. In the context of an application for patient monitoring in mediacal intensive care unit, we introduce an original concept of the Medical Black Box and we propose a new system for visual monitoring of Automatic Detection of risk Situations and Alert (DASA) based on a CCTV system with network smart camera. The aim is to interpret the visual information flow and to detect at real-time risk situations to prevent the mediacl team and then archive the events in a video that is based Medical Black Box data. The interpretation system is based on scenario recognition algorithms that exploit the Hidden Markov Models (HMM). An extension of the classic model of HMM is proposed to handle the internal reporting structure of the scenarios and to control the duration of each state of the Markov model. The main contribution of this work relies on the integration of an evidential reasoning, in order to manage the recognition decision taking into account the imperfections of available information. The proposed scenarios recognition method have been tested and assessed on database of medical video sequences and compared to standard probabilistic Hidden Markov Models.

Orientador: Aparecido Nilceu Marana / Banca: Hélio Pedrini / Banca: Aledir Silveira Pereira / Resumo: As técnicas para identificação biométrica têm evoluído cada vez mais devido à necessidade que os seres humanos têm de identificar as pessoas em tempo real e de forma precisa para permitir o acesso a determinados recursos, como por exemplo, as aplicações e serviços WEB. O reconhecimento facial é uma técnica biométrica que apresenta várias vantagens em relação às demais, tais como: uso de equipamentos simples e baratos para a obtenção das amostras e a possibilidade de se realizar o reconhecimento em sigilo e à distância. O reconhecimento de faces a partir de vídeo é uma tendência recente na área de Biometria. Esta dissertação tem por objetivo principal comparar diferentes técnicas de reconhecimento facial a partir de vídeo para determinar as que apresentam um melhor compromisso entre tempo de processamento e precisão. Outro objetivo é a incorporação dessas melhores técnicas no sistema de autenticação biométrica em ambientes de E-Learning, proposto em um trabalho anterior. Foi comparado o classificador vizinho mais próximo usando as medidas de distância Euclidiana e Mahalanobis com os seguintes classificadores: Redes Neurais MLP e SOM, K Vizinhos mais Próximos, Classificador Bayesiano, Máquinas de Vetores de Suporte (SVM) e Floresta de Caminhos Ótimos (OPF). Também foi avaliada a técnica de Modelos Ocultos de Markov (HMM). Nos experimentos realizados com a base Recogna Video Database, criada especialmente para uso neste trabalho, e Honda/UCSD Video Database, os classificadores apresentaram os melhores resultados em termos de precisão, com destaque para o classificador SVM da biblioteca SVM Torch. A técnica HMM, que incorpora informações temporais, apresentou resultados melhores do que as funções de distância, em termos de precisão, mas inferiores aos classificadores / Abstract: The biometric identification techniques have evolved increasingly due to the need that humans have to identify people in real time to allow access to certain resources, such as applications and Web services. Facial recognition is a biometric technique that has several advantages over others. Some of these advantages are the use of simple and cheap equipment to obtain the samples and the ability to perform the recognition in covert mode. The face recognition from video is a recent approach in the area of Biometrics. The work in this dissertation aims at comparing different techniques for face recognition from video in order to find the best rates on processing time and accuracy. Another goal is the incorporation of these techniques in the biometric authentication system for E-Learning environments, proposed in an earlier work. We have compared the nearest neighbor classifier using the Euclidean and Mahalanobis distance measures with some other classifiers, such as neural networks (MLP and SOM), k-nearest neighbor, Bayesian classifier, Support Vector Machines (SVM), and Optimum Path Forest (OPF). We have also evaluated the Hidden Markov Model (HMM) approach, as a way of using the temporal information. In the experiments with Recogna Video Database, created especially for this study, and Honda/UCSD Video Database, the classifiers obtained the best accuracy, especially the SVM classifier from the SVM Torch library. HMM, which takes into account temporal information, presented better performance than the distance metrics, but worse than the classifiers / Mestre

Made available in DSpace on 2014-06-12T15:50:15Z (GMT). No. of bitstreams: 2 arquivo1959_1.pdf: 2352925 bytes, checksum: 90760b286db4ed0dcc12ae48554413a9 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Estudos recentes têm demonstrado que as redes biológicas apresentam características nãoaleatórias, dentre as quais destacamos a arquitetura modular. Neste trabalho, estamos interessados na organização modular das redes de regulação transcricional (RRT), que modelizam as interações entre genes e proteínas que controlam a sua expressão no nível transcricional. Compreender os mecanismos de regulação transcricional é crucial para se explicar a diversidade morfológica e funcional das células. Nós nos propomos a abordar o problema da identificação de módulos regulatórios transcricionais, i.e. grupos de genes co-regulados e seus reguladores, com ênfase no aspecto computacional. Uma distinção importante deste trabalho é que estamos também interessados em estudar o aspecto evolutivo dos módulos transcricionais. Do ponto de vista biológico, a abordagem proposta está fundamentada em três premissas principais: (i) genes co-regulados são controlados por proteínas regulatórias comuns (fatores de transcrição FTs) e, portanto, eles devem apresentar padrões de sequência (motifs) comuns nas suas regiões regulatórias, que correspondem aos sítios de ligação desses FTs, (ii) genes co-regulados respondem coordenadamente a certas condições ambientais e de desenvolvimento e, logo, devem ser co-expressos sob essas condições, e (iii) uma vez que módulos transcricionais são presumivelmente responsáveis por funções biológicas importantes, eles estão sujeitos a uma maior pressão seletiva e, consequentemente, devem ser evolutivamente conservados. Nós definimos, portanto, o conceito de metamódulo regulatório transcricional (MMRT) como grupos de genes compartilhando motifs e exibindo um comportamento de expressão coerente em contextos específicos consistentemente em várias espécies e propomos modelos probabilísticos para descrever o comportamento modular em termos do compartilhamento de elementos regulatórios (motifs), da co-expressão e da conservação evolutiva das associações funcionais entre os genes com base em dados diversos tais como dados de sequência, de expressão e dados filogenéticos

Single molecule experiments study the kinetics of molecular biological systems. Many such studies generate data that can be described by aggregated hidden Markov models, whereby there is a need of doing inference on such data and models. In this study, model selection in aggregated Hidden Markov models was performed with a criterion of maximum Bayesian evidence. Variational Bayes inference was seen to underestimate the evidence for aggregated model fits. Estimation of the evidence integral by brute force Monte Carlo integration theoretically always converges to the correct value, but it converges in far from tractable time. Nested sampling is a promising method for solving this problem by doing faster Monte Carlo integration, but it was here seen to have difficulties generating uncorrelated samples.