Thesis--Auburn University, 2008. / Abstract. Vita. Includes bibliographical references (p. 45-48).

Un des principaux défis de la bioinformatique moderne est de saisir le sens des données biologiques en constante croissance. Il est prépondérant de trouver de bons modèles pour toutes ces données, modèles qui servent à la fois à expliquer les données et à produire des réponses aux questions biologiques sous-jacentes. Une des nombreuses difficultés d’une telle approche est la grande variété dans les types des données manipulées. La biologie computationnelle moderne propose des approches qui combinent ces types de données dans des techniques dites intégratives. Cette thèse contribue au problème de l’identification de module biologique en intégrant les informations de conservation dans les modèles modernes d’identification d’ensemble de protéines. Nous introduisons un modèle pour la détection de modules connexes actifs et conservés, c’est-à-dire des modules connexes dont une majorité d’éléments sont similaires entre deux espèces. Nous présentons une formulation de notre modèle sous forme de programmation linéaire en nombres entiers, et proposons un algorithme branch-and-cut qui résout le modèle à l’optimalité en temps raisonnable. Nous appliquons notre modèle sur des données de différentiation cellulaire, à savoir les cellules Th0 en Th17 pour l’humain et la sourie. Nous analysons également notre modèle du point du vue de la complexité algorithmique, et fournissons des résultats pour le cas général ainsi que des cas spéciaux. / One of the major challenge for modern bioinformatics is making sense of the ever increasing size of biological data. Finding good models for all this data, models that can both explain the data and provide insight into biological questions, is paramount. One of the many difficulties of such path is the variety in the types of data. Modern computational biology approaches combine these many data into integrative approaches, that combine the knowledge inside the data in the hope to extract higher level information. This thesis contribute to the biological module identification problem by integrating conservation information with modern models of modular detection of protein sets. We introduce a model for the detection of conserved active connected modules, that is connected modules that are conversed across two species. These active connected modules are similar in sequence composition between the two species. We present a mixed-integer linear programming formulation of our model, and propose a branch-and-cut algorithm to solve to provable optimality in reasonable run time. We apply our model to cell line differentiation data, namely Th0 into Th17 for both human and mouse. We also analyse the model from a complexity standpoint, and provide general as well as special cases complexity results.

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

A graph is said to be 2-edge-connected if it remains connected after the deletion of any single edge. Given an unweighted bridgeless graph G with n vertices, the minimum size 2-edge-connected spanning subgraph problem (2EC) is that of finding a 2-edge-connected spanning subgraph of G with the minimum number of edges. This problem has important applications in the design of survivable networks. However, because the problem is NP-hard, it is unlikely that efficient methods exist for solving it. Thus efficient methods that find solutions that are provably close to optimal are sought. In this thesis, an approximation algorithm is presented for 2EC on bridgeless cubic graphs which guarantees to be within 5/4 of the optimal solution value, improving on the previous best proven approximation guarantee of 5/4+ε for this problem. We also focus on the linear programming (LP) relaxation of 2EC, which provides important lower bounds for 2EC in useful solution techniques like branch and bound. The “goodness” of this lower bound is measured by the integrality gap of the LP relaxation for 2EC, denoted by α2EC. Through a computational study, we find the exact value of α2EC for graphs with small n. Moreover, a significant improvement is found for the lower bound on the value of α2EC for bridgeless subcubic graphs, which improves the known best lower bound on α2EC from 9/8 to 8/7.

Árvore de componentes é uma forma hierárquica de representar imagens em níveis de cinza baseada nas relações de inclusão dos componentes conexos da imagem. A escolha da vizinhança utilizada para gerar os componentes impacta diretamente na árvore resultante, de forma que uma alteração na escolha da vizinhança pode acarretar em uma alteração na árvore de componentes obtida. Em particular, quando uma sequência de vizinhanças crescentes é usada, os nós das árvores obtidas a partir dessas vizinhanças satisfazem uma relação de inclusão, de forma que se é possível estabelecer relações entre nós de diferentes árvores. Assim sendo, o principal objetivo desta dissertação consiste no desenvolvimento de um algoritmo eficiente para a construção de uma sequência de árvores de componentes. Para tanto, será introduzida uma classe particular de sequências de vizinhanças, que não apenas satisfaz a propriedade crescente como também permite que as árvores de componentes associadas a ela sejam construídas de forma incremental. Com base nestas propriedades, um novo algoritmo de construção de árvores de componentes associado a esta classe de vizinhanças será proposto. Para analisar a eficiência do algoritmo proposto apresentamos, ao final do texto, alguns resultados práticos e teóricos obtidos com relação ao consumo de tempo e à complexidade computacional. / Component tree is a hierarchical way of representing gray-level images based on the inclusion relation of the connected components of the image. The choice of the neighborhood used to generate these components directly impacts in the resulting tree: changing the neighborhood used may cause a change in the resulting component tree. In particular, when considering a sequence of increasing neighborhoods, the nodes of the obtained from these neighborhoods will also satisfy an inclusion relation and that will make it possible to link nodes from different trees. Therefore, the main goal of this dissertation is the development of an efficient algorithm to build a sequence of component trees. In order to do that, we will introduce a class of sequences of neighborhood that not only satisfy the increasing property but also makes it possible to incrementally build the trees associated to it. This additional property will guide us to a novel algorithm, that will build the component trees associated to this class of neighborhoods. To show how efficient the proposed algorithm is, we present some experimental and theoretical results regarding time consumption and computational complexity.

With the rapid advances of technology, digitisation of many facets of our existence is taking place in an attempt to improve everyday life. The automotive industry is following suit, attempting to introduce connected traffic technology that is meant to improve traffic fluidity and safety. To facilitate this, connected vehicles aim to create solutions for the sharing of information between other vehicles, infrastructure - such as traffic light controllers, and pedestrians. In an attempt to further investigate the connected vehicle landscape of today, the thesis compared the two most prominent technologies, DSRC and cellular communication. An essential part of this comparison was highlighting the potential attacks that the two technologies could be exposed to. This was done in order to open up a discussion on what technology is the most suitable to focus on for the future both in terms of viability and security. DSRC has been considered the prominent communication technology for connected vehicles, but the development has stagnated. As such, the ever-evolving cellular technology is looking like the superior technology. This, however, is reliant on 5G delivering the speeds, stability and security promised. The state of constant vehicular connection is going to lead to many issues and concerns, both for the privacy of the individual but also the safety of the public. While connected traffic aims to solve a number of issues from traffic accidents to emissions - if the security of the communication is not constantly evolving to meet the rapid development of new technology, the consequences of connecting such a delicate system might nullify the potential benefits.

Weight-sharing property in convolutional neural network (CNN) is useful in reducing number of parameters in the network and also introduces regularization effect which helps to gain high performance. Non-weight-shared convolutional neural networks also known as Locally connected networks (LCNs) has potential to learn more<br>in each layer due to large number of parameters without increasing number of inference computations as compared to CNNs. This work explores the idea of where Locally connected layers can be used to gain performance benefits in terms of accuracy and computations, what are the challenges in training the locally connected networks and what are the techniques that should be introduced in order to train this network and achieve high performance. Partially-local connected network (P-LCN) VGG-16 which is hybrid of convolutional layers and Locally connected layers achieves on average 2.0% accuracy gain over VGG-16 full convolutional network on CIFAR100 and 0.32% on CIFAR10. Modified implementation of batch normalization for Full LCNs (all layers in network are locally connected layers) gives improvement of 50% in training accuracy as compared to using CNN batch normalization layer in full LCN. Since L1, L2 and Dropout regularization does not help improve accuracy of LCNs, regularization methods which focuses on kernels rather than individual weight for regularizing the network were explored. Ladder networks with semi supervised learning achieves this goal. Training methodology of ladder networks was modified to achieve ∼2% accuracy improvement on Pavia-University hyper-spectral image dataset with 5 labels per class.

No description available.

Este documento apresenta uma dissertação sobre o desenvolvimento de um sistema de integração de dados para geração de estruturas tridimensionais a partir de vídeo 3D. O trabalho envolve a extensão de um sistema de vídeo 3D em tempo real proposto recentemente. Esse sistema, constituído por projetor e câmera, obtém imagens de profundidade de objetos por meio da projeção de slides com um padrão de faixas coloridas. Tal procedimento permite a obtenção, em tempo real, tanto do modelo 2,5 D dos objetos quanto da textura dos mesmos, segundo uma técnica denominada luz estruturada. Os dados são capturados a uma taxa de 30 quadros por segundo e possuem alta qualidade: resoluções de 640 x 480 pixeis para a textura e de 90 x 240 pontos (em média) para a geometria. A extensão que essa dissertação propõe visa obter o modelo tridimensional dos objetos presentes em uma cena por meio do registro dos dados (textura e geometria) dos diversos quadros amostrados. Assim, o presente trabalho é um passo intermediário de um projeto maior, no qual pretende-se fazer a reconstrução dos modelos por completo, bastando para isso apenas algumas imagens obtidas a partir de diferentes pontos de observação. Tal reconstrução deverá diminuir a incidência de pontos de oclusão (bastante comuns nos resultados originais) de modo a permitir a adaptação de todo o sistema para objetos móveis e deformáveis, uma vez que, no estado atual, o sistema é robusto apenas para objetos estáticos e rígidos. Até onde pudemos averiguar, nenhuma técnica já foi aplicada com este propósito. Este texto descreve o trabalho já desenvolvido, o qual consiste em um método para detecção, rastreamento e casamento espacial de componentes conexas presentes em um vídeo 3D. A informação de imagem do vídeo (textura) é combinada com posições tridimensionais (geometria) a fim de alinhar partes de superfícies que são vistas em quadros subseqüentes. Esta é uma questão chave no vídeo 3D, a qual pode ser explorada em diversas aplicações tais como compressão, integração geométrica e reconstrução de cenas, dentre outras. A abordagem que adotamos consiste na detecção de características salientes no espaço do mundo, provendo um alinhamento de geometria mais completo. O processo de registro é feito segundo a aplicação do algoritmo ICP---Iterative Closest Point---introduzido por Besl e McKay em 1992. Resultados experimentais bem sucedidos corroborando nosso método são apresentados. / This document presents a MSc thesis focused on the development of a data integration system to generate tridimensional structures from 3D video. The work involves the extension of a recently proposed real time 3D video system. This system, composed by a video camera and a projector, obtains range images of recorded objects using slide projection of a coloured stripe pattern. This procedure allows capturing, in real time, objects´ texture and 2,5 D model, at the same time, by a technique called structured light. The data are acquired at 30 frames per second, being of high quality: the resolutions are 640 x 480 pixels and 90 x 240 points (in average), respectively. The extension that this thesis proposes aims at obtaining the tridimensional model of the objects present in a scene through data matching (texture and geometry) of various sampled frames. Thus, the current work is an intermediary step of a larger project with the intent of achieving a complete reconstruction from only a few images obtained from different viewpoints. Such reconstruction will reduce the incidence of occlusion points (very common on the original results) such that it should be possible to adapt the whole system to moving and deformable objects (In the current state, the system is robust only to static and rigid objects.). To the best of our knowledge, there is no method that has fully solved this problem. This text describes the developed work, which consists of a method to perform detection, tracking and spatial matching of connected components present in a 3D video. The video image information (texture) is combined with tridimensional sites (geometry) in order to align surface portions seen on subsequent frames. This is a key step in the 3D video that may be explored in several applications such as compression, geometric integration and scene reconstruction, to name but a few. Our approach consists of detecting salient features in both image and world spaces, for further alignment of texture and geometry. The matching process is accomplished by the application of the ICP---Iterative Closest Point---algorithm, introduced by Besl and McKay in 1992. Succesful experimental results corroborating our method are shown.

Grid-connected inverters have wide application in the field of distributed generation and power quality. As the power level demanded by these applications increase, the design and performance evaluation of these converters become important. In the present work, a 50 kVA three-phase back-to-back connected inverter with output LCL filter is built to study design and performance evaluation aspects of grid-connected inverters. The first part of the work explores the split-capacitor resistive-inductive (SC-RL) passive damping scheme for the output LCL filter of a three-phase grid-connected inverter. The low losses in the SC-RL scheme makes it suitable for high power applications. The SCRL damped LCL filter is modelled using state space approach. Using this model, the power loss and damping are analysed. A method for component selection that minimizes the power loss in the damping resistors while keeping the system well damped is proposed. Analytical results show the losses to be in the range of 0.05-0.1% and the quality factor to be in the range of 2.0-2.5. These results are validated experimentally. In the second part of the work, a test method to evaluate the thermal performance of the semi-conductor devices of a three-phase grid-connected inverter is proposed. The method eliminates the need for high power sources, loads or any additional power converters for circulation of power. Only energy corresponding to the losses is consumed. The capability of the method to evaluate the thermal performance of the DC bus capacitors and the output filter components is also explored. The method can be used with different inverter configurations -three-wire or four-wire and for different PWM techniques. The method has been experimentally validated at a power level of 24kVA. In the third part of the work, the back-to-back connected inverter is programmed as a hardware grid simulator. The hardware grid simulator emulates the real-time grid and helps create grid disturbances often observed at the point of common coupling in an ac low voltage grid. A novel disturbance generation algorithm has been developed, analysed and implemented in digital controller using finite state machine model for control of the grid simulator. A wide range of disturbance conditions can be created using the developed algorithm. Experimental tests have been done on a linear purely resistive load, a non-linear diode-bridge load and a current-controlled inverter load to validate the programmed features of the grid simulator.