Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references.

Thesis (M.Sc.)--York University, 2003. Graduate Programme in Mathematics and Statistics. / Typescript. Includes bibliographical references (leaves 112-121) and index. Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL:http://gateway.proquest.com/openurl?url%5Fver=Z39.88-2004&res%5Fdat=xri:pqdiss&rft%5Fval%5Ffmt=info:ofi/fmt:kev:mtx:dissertation&rft%5Fdat=xri:pqdiss:MQ99310

No description available.

There are three families of exact methods used for probabilistic inference in belief nets. It is necessary to compare them and analyze the advantages and the disadvantages of each algorithm, and know the time cost of making inferences in a given belief network. This paper discusses the factors that influence the computation time of each algorithm, presents the predictive model of the time complexity for each algorithm and shows the statistical results of testing the algorithms with randomly generated belief networks. / Graduation date: 1991

The physical manipulation of biological cells is very attractive now in biotechnology (Butler, 1991)) because it opens the possibility of examining and manipulating single molecules. Other methods are based on chemical effects, electrical effects, etc., and they generally do not allow researchers to examine single molecules cell and, thus, to understand their interaction which may encode many useful pieces of information. Such physical manipulation is fully performed by robotic devices. <p> In order to automate the process of physical manipulation, micro machine vision for the fast identification of the objects involved is required. Typical objects that are involved are cells, cell elements, holders and injectors. <p> In the research described in this thesis, which was carried out in the Advanced Engineering Design Laboratory of the Mechanical Engineering Department, University of Saskatchewan, algorithms for the three objects (the cell, holder and injector) were developed, implemented and tested. The results obtained have shown that the fastest identification times for these three objects are respectively 0.12s for the cell oocyte, 6.78s/100 frames for the holder, and 6.72s/100 frames for the injector. These performances are acceptable in the context of the physical manipulation of biological cells.<p> The goal of the research described in this thesis was to develop algorithms that would give a fast recognition of the cell manipulation system. With the aid of the algorithms, an automatic operation of the cell manipulation system would be achieved. Image process and pattern recognition techniques were used in developing the Visual C++ GUI algorithms that would automatically recognize the components of the cell manipulation system for the purpose of manipulating the cells.

The physical manipulation of biological cells is very attractive now in biotechnology (Butler, 1991)) because it opens the possibility of examining and manipulating single molecules. Other methods are based on chemical effects, electrical effects, etc., and they generally do not allow researchers to examine single molecules cell and, thus, to understand their interaction which may encode many useful pieces of information. Such physical manipulation is fully performed by robotic devices. <p> In order to automate the process of physical manipulation, micro machine vision for the fast identification of the objects involved is required. Typical objects that are involved are cells, cell elements, holders and injectors. <p> In the research described in this thesis, which was carried out in the Advanced Engineering Design Laboratory of the Mechanical Engineering Department, University of Saskatchewan, algorithms for the three objects (the cell, holder and injector) were developed, implemented and tested. The results obtained have shown that the fastest identification times for these three objects are respectively 0.12s for the cell oocyte, 6.78s/100 frames for the holder, and 6.72s/100 frames for the injector. These performances are acceptable in the context of the physical manipulation of biological cells.<p> The goal of the research described in this thesis was to develop algorithms that would give a fast recognition of the cell manipulation system. With the aid of the algorithms, an automatic operation of the cell manipulation system would be achieved. Image process and pattern recognition techniques were used in developing the Visual C++ GUI algorithms that would automatically recognize the components of the cell manipulation system for the purpose of manipulating the cells.

We study the connectivity properties of the Internet graph and its impact on its structure.

Short substrings of genomic data that are responsible for biological processes, such as gene expression, are referred to as motifs. Motifs with the same function may not entirely match, due to mutation events at a few of the motif positions. Allowing for non-exact occurrences significantly complicates their discovery. Given a number of DNA strings, the motif recognition problem is the task of detecting motif instances in every given sequence without knowledge of the position of the instances or the pattern shared by these substrings. We describe a novel approach to motif recognition, and provide theoretical and experimental results that demonstrate its efficiency and accuracy. Our algorithm, MCL-WMR, builds an edge-weighted graph model of the given motif recognition problem and uses a graph clustering algorithm to quickly determine important subgraphs that need to be searched further for valid motifs. By considering a weighted graph model, we narrow the search dramatically to smaller problems that can be solved with significantly less computation. The Closest String problem is a subproblem of motif recognition, and it is NP-hard. We give a linear-time algorithm for a restricted version of the Closest String problem, and an efficient polynomial-time heuristic that solves the general problem with high probability. We initiate the study of the smoothed complexity of the Closest String problem, which in turn explains our empirical results that demonstrate the great capability of our probabilistic heuristic. Important to this analysis is the introduction of a perturbation model of the Closest String instances within which we provide a probabilistic analysis of our algorithm. The smoothed analysis suggests reasons why a well-known fixed parameter tractable algorithm solves Closest String instances extremely efficiently in practice. Although the Closest String model is robust to the oversampling of strings in the input, it is severely affected by the existence of outliers. We propose a refined model, the Closest String with Outliers problem, to overcome this limitation. A systematic parameterized complexity analysis accompanies the introduction of this problem, providing a surprising insight into the sensitivity of this problem to slightly different parameterizations. Through the application of probabilistic and combinatorial insights into the Closest String problem, we develop sMCL-WMR, a program that is much faster than its predecessor MCL-WMR. We apply and adapt sMCL-WMR and MCL-WMR to analyze the promoter regions of the canola seed-coat. Our results identify important regions of the canola genome that are responsible for specific biological activities. This knowledge may be used in the long-term aim of developing crop varieties with specific biological characteristics, such as being disease-resistant.

Parking functions have been a focus of mathematical research since the mid-1970s. Various generalizations have been introduced since the mid-1990s and deep relationships between these and other areas of mathematics have been discovered. Here, we introduced a new generalization, the G-multiparking function, where G is a simple graph on a totally ordered vertex set {1, 2, . . . , n}. We give an algorithm that converts a G-multiparking function into a rooted spanning forest of G by using a graph searching technique to build a sequence F1, F2, . . . , Fn, where each Fi is a subforest of G and Fn is a spanning forest of G. We also give another algorithm that converts a rooted spanning forest of G to a G-multiparking function and prove that the resulting functions (between the sets of G-multiparking functions and rooted spanning forests of G) are bijections and inverses of each other. Each of these two algorithms relies on a choice function , which is a function from the set of pairs (F,W) (where F is a subforest of G and W is a set of some of the leaves of F) into W. There are many possible choice functions for a given graph, each giving formality to the concept of choosing how a graph searching algorithm should procede at each step (i.e. if the algorithm has reached Fi, then Fi+1 is some forest on the vertex set V (Fi)∪{(Fi,W)} for some W). We also define F-redundant edges, which are edges whose removal from G does not affect the execution of either algorithm mentioned above. This concept leads to a categorization of the edges of G, which in turn provides a new formula for the Tutte polynomial of G and other enumerative results.

Bin packing is a very important and popular research area in the computer science field. Past work showed many good and real-world packing algorithms. How- ever, due to the complexity of the problem in multiple-dimensional bin packing, also called hyperbox packing, we need more practical packing algorithms for its real-world applications. In this dissertation, we extend 1D packing algorithms to hyperbox packing prob- lems via a general framework that takes two inputs of a 1D packing algorithm and an instance of hyperbox packing problem and outputs a hyperbox packing algorithm. The extension framework significantly enriches the family of hyperbox-packing algorithms, generates many framework-based algorithms, and simultaneously calls for the analysis for those algorithms. We also analyze the performance of a couple of framework-based algorithms from two perspectives of worst-case performance and average-case performance. In worst- case analysis, we use the worst-case performance ratio as our metric and analyze the relationship of the ratio of framework-based algorithms and that of the corresponding 1D algorithms. We also compare their worst-case performance against two baselines: strip optimal algorithms and optimal algorithms. In average-case analysis, we use expected waste as a metric, analyze the waste of optimal hyperbox packing algorithms, and estimate the asymptotic forms of the waste for framework-based algorithms.