CS Theses & Dissertations 2006

For 2006 graduation dates (in alphabetical order by last name):

BRDF Acquisition With Basis Illumination
Achutha, Shruthi
DOI : 10.14288/1.0051752
URI : http://hdl.handle.net/2429/18359
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Heidrich

The Design and Field Evaluation of PhotoTalk:  A Digital Image Communication Application for People who have Aphasia
Allen, Meghan Elizabeth
DOI : 10.14288/1.0051725
URI : http://hdl.handle.net/2429/17911
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. McGrenere

Disk Performance of Copy-On-Write Snapshot Logical Volumes
Bhavana, Saha
DOI : 10.14288/1.0051513
URI : http://hdl.handle.net/2429/18146
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Hutchinson

An Evaluation of Overviews for Large Tree Navigation
Bodnar, Adam Michael
DOI : 10.14288/1.0051590
URI : http://hdl.handle.net/2429/17735
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisors : Dr. McGrenere, Dr. Munzner

Fluid Animation with Explicit Surface Meshes and Boundary-Only Dynamics
Brochu, Tyson Andre
DOI : 10.14288/1.0051716
URI : http://hdl.handle.net/2429/17862
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Bridson

The Application of the Permutation Test in Genome Wide Expression Analysis
Chan, Timothy Hay Wung
DOI : 10.14288/1.0051243
URI : http://hdl.handle.net/2429/17660
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Ng

Geometric Facility Location under Continuous Motion
Durocher, Stephane
DOI : 10.14288/1.0051487
URI : http://hdl.handle.net/2429/18212
Degree : Doctor of Philosophy - PhD
Graduation Date : 2006-05
Supervisor : Dr. Kirkpatrick

The traditional problems of facility location are defined statically; a set (or multiset) of n points is given as input, corresponding to the positions of clients, and a solution is returned consisting of set of k points, corresponding to the positions of facilities, that optimizes some objective function of the input set. In the k-centre problem, the objective is to select k points for locating facilities such that the maximum distance from any client to its nearest facility is minimized. In the k-median problem, the objective is to select k points for locating facilities such that the average distance front each client to its nearest facility is minimized. A common setting for these problems is to model clients and facilities as points in Euclidean space and to measure distances between these by the Euclidean distance metric. In this thesis, we examine these problems in the mobile setting. A problem instance consists of a set of mobile clients, each following a continuous trajectory through Euclidean space under bounded velocity. The positions of the mobile Euclidean k-centre and k-median are defined as functions of the instantaneous positions of the clients. Since mobile facilities located at the exact Euclidean k-centre or k-median involve either unbounded velocity or discontinuous motion, we explore approximations to these. The goal is to define a set of functions, corresponding to positions for the set of mobile facilities, that provide a good approximation to the Euclidean k-centre or k-median while maintaining motion that is continuous and whose magnitude of velocity has a low fixed upper bound. Thus, the fitness of a mobile facility is determined not only by the quality of its optimization of the objective function but also by the maximum velocity and continuity of its motion. These additional constraints lead to a trade-off between velocity and approximation factor, requiring new approximation strategies quite different from previous static approximations. We identify existing functions and introduce new functions that provide bounded-velocity approximations of the mobile Euclidean 1-centre, 2-centre, and 1-median. We show that no bounded-velocity approximation of the Euclidean 3-centre or the Euclidean 2-median is possible. Finally, we present kinetic algorithms for maintaining these various functions using both exact and approximate solutions.

Freedom and the War on Terror in the Digital Age
Estrada Alvarez, Juan Gabriel
DOI : 10.14288/1.0051399
URI : http://hdl.handle.net/2429/17627
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Rosenberg

Fast Secure Virtualization for the ARM Platform
Ferstay, Daniel
DOI : 10.14288/1.0051591
URI : http://hdl.handle.net/2429/17835
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Hutchinson

Compositionality of Handlers on Intermediate Servers in a Web Service Architecture
Forghanizadeh, Sara
DOI : 10.14288/1.0051723
URI : http://hdl.handle.net/2429/17959
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Wohlstadter

An Investigation of the Effects of Matching Attentional Draw with Utility in Computer-Based Interruption
Gluck, Jennifer Shari
DOI : 10.14288/1.0051730
URI : http://hdl.handle.net/2429/17933
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. McGrenere

RSnap: Recursive Writable Snapshots for Logical Volumes
Gupta, Abhishek
DOI : 10.14288/1.0051721
URI : http://hdl.handle.net/2429/17935
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Hutchinson

Role-Based Refactoring of Crosscutting Concerns
Hannemann, Jan
DOI : 10.14288/1.0051755
URI : http://hdl.handle.net/2429/18477
Degree : Doctor of Philosophy - PhD
Graduation Date : 2006-05
Supervisors : Dr. Kiczales, Dr. Murphy

Improving the structure of code can help developers work with a software system more efficiently and more consistently. Aspect-oriented programming (AOP) offers additional ways to structure software by providing explicit means to modularize crosscutting concerns (CCCs) in modularity units called aspects. With the advent of AOP, a new kind of structural improvement of software needs to be considered: the refactoring of non-modularized CCCs into aspects. Refactorings have shown to be helpful for object-oriented software development and maintenance, but their application to aspect-oriented software is not yet well understood. In particular, since refactorings of non-modularized crosscutting concerns involve multiple program elements with potentially complicated relationships, they are considerably more complex than traditional refactorings; the lack of tool support to help plan, reason about and execute CCC refactorings impedes the improvement of code modularity. The thesis of this research is that the refactoring of crosscutting concerns can be supported by a role-based concern model. In this model, crosscutting concerns are described in terms of abstract roles, and instructions for refactoring the concerns are written in terms of those roles. To apply a refactoring, a developer maps a subset of the roles to concrete program elements; a tool can then help complete the mapping of roles to the existing program. Refactoring instructions are then applied to manipulate and modularize the concrete elements corresponding to the crosscutting concern. The abstract nature of such a role-based concern model allows the definition of a refactoring description separately from concrete systems it may be applied to, and allows using a single description to refactor multiple instances of the same concern. To aid developers in restructuring the implementation of crosscutting concerns using aspect-oriented programming, we introduce in this dissertation a refactoring approach and proof-of-concept tool founded on our role-based concern model. We show that abstract descriptions of crosscutting concerns can be applied to previously existing software and we describe the potential for expressing and executing a variety of new CCC refactorings.

Assisted Detection of Duplicate Bug Reports
Hiew, Lyndon Hin-Fui
DOI : 10.14288/1.0051726
URI : http://hdl.handle.net/2429/18036
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Murphy

Comparative Study of Statistical Methods for Finding Biomarkers in Longitudinal Data
Hollander, Zsuzsanna
DOI : 10.14288/1.0051174
URI : http://hdl.handle.net/2429/17587
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Ng

Computational Problems in Multiagent Systems
Jiang, Xin Albert
DOI : 10.14288/1.0051584
URI : http://hdl.handle.net/2429/17668
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Leyton-Brown

Developable Surface Processing Methods for Three-Dimensional Meshes
Julius, Dan Natan
DOI : 10.14288/1.0051581
URI : http://hdl.handle.net/2429/17648
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Sheffer

Visual Mining of Powersets with Large Alphabets
Kong, Qiang
DOI : 10.14288/1.0051718
URI : http://hdl.handle.net/2429/17553
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisors : Dr. Ng, Dr. Munzner

Interaction Capture and Synthesis of Human Hands
Kry, Paul
DOI : 10.14288/1.0051709
URI : http://hdl.handle.net/2429/18549
Degree : Doctor of Philosophy - PhD
Graduation Date : 2006-05
Supervisor : Dr. Pai

This thesis addresses several issues in modelling interaction with human hands in computer graphics and animation. Modifying motion capture to satisfy the constraints of new animation is difficult when contact is involved because physical interaction involves energy or power transfer between the system of interest and the environment, and is a critical problem for computer animation of hands. Although contact force measurements provide a means of monitoring this transfer, motion capture as currently used for creating animation has largely ignored contact forces. We present a system of capturing synchronized motion and contact forces, called interaction capture. We transform interactions such as grasping into joint compliances and a nominal reference trajectory in an approach inspired by the equilibrium point hypothesis of human motor control. New interactions are synthesized through simulation of a quasi-static compliant articulated model in a dynamic environment that includes friction. This uses a novel position-based linear complementarity problem formulation that includes friction, breaking contact, and coupled compliance between contacts at different fingers. We present methods for reliable interaction capture, addressing calibration, force estimation, and synchronization. Additionally, although joint compliances are traditionally estimated with perturbation-based methods, we introduce a technique that instead produces estimates without perturbation. We validate our results with data from previous work and our own perturbation-based estimates. A complementary goal of this work is hand-based interaction in virtual environments. We present techniques for whole-hand interaction using the Tango, a novel sensor that performs interaction capture by measuring pressure images and accelerations. We approximate grasp hand-shapes from previously observed data through rotationally invariant comparison of pressure measurements. We also introduce methods involving heuristics and thresholds that make reliable drift-free navigation possible with the Tango. Lastly, rendering the skin deformations of articulated characters is a fundamental problem for computer animation of hands. We present a deformation model, called EigenSkin, which provides a means of rendering physically- or example-based deformation models at interactive rates on graphics hardware.

Imitation-based Learning of Bipedal Walking Using Locally Weighted Learning
Loken, Kevin Mark
DOI : 10.14288/1.0051510
URI : http://hdl.handle.net/2429/18314
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. van de Panne

Using Haptics to Address Mobile Interaction Design Challenges: Prototyping and User Evaluation with a Handheld Tactile Display
Luk, Joseph
DOI : 10.14288/1.0051517
URI : http://hdl.handle.net/2429/18317
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. MacLean

On the Study of Tree Pattern Matching Algorithms and Applications
Ma, Fei
DOI : 10.14288/1.0051511
URI : http://hdl.handle.net/2429/18318
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Evans

A Block Preconditioning Cost Analysis for Solving Saddle-Point Linear Systems
MacKinnon-Cormier, Sarah
DOI : 10.14288/1.0051203
URI : http://hdl.handle.net/2429/16638
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Greif

A Model and Adaptive Support for Learning in an Education Game
Manske, Micheline
DOI : 10.14288/1.0051720
URI : http://hdl.handle.net/2429/17581
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Conati

Pointcuts by Example
McCormick, Edward
DOI : 10.14288/1.0051502
URI : http://hdl.handle.net/2429/17605
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. De Volder

LiveRAC - Live Reorderable Accordion Drawing
McLachlan, Peter
DOI : 10.14288/1.0051727
URI : http://hdl.handle.net/2429/18074
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Munzner

On the Use of Eye-tracking in the Assessment of Self-explanation in an Open Learning Environment
Merten, Christina
DOI : 10.14288/1.0051576
URI : http://hdl.handle.net/2429/17573
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Conati

Doxpects: XML Transformation Aspects
Minevskiy, Ivan
DOI : 10.14288/1.0051719
URI : http://hdl.handle.net/2429/18086
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Wohlstadter

Multiclass Object Recognition Inspired by the Ventral Visual Pathway
Mutch, James Vincent
DOI : 10.14288/1.0051724
URI : http://hdl.handle.net/2429/18090
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Lowe

A Comparison of Pan and Zoom and Rubber Sheet navigation
Nekrasovski, Dmitry
DOI : 10.14288/1.0051176
URI : http://hdl.handle.net/2429/17567
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisors : Dr. McGrenere, Dr. Munzner

Towards MPI Progression Layer Elimination with TCP and SCTP
Penoff, Bradley Thomas
DOI : 10.14288/1.0051173
URI : http://hdl.handle.net/2429/17572
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Wagner

A Logic and Decision Procedure for Verification of Heap-Manipulating Programs
Rakamaric, Zvonimir
DOI : 10.14288/1.0051503
URI : http://hdl.handle.net/2429/18130
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Hu

Augmentation Preconditioning for Saddle Point Systems Arising from Interior Point Methods
Rees, Timothy Walter
DOI : 10.14288/1.0051722
URI : http://hdl.handle.net/2429/18115
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Greif

Equalizing Filter Design for High-Speed Off-Chip Buses
Ren, Jihong
DOI : 10.14288/1.0051450
URI : http://hdl.handle.net/2429/18456
Degree : Doctor of Philosophy - PhD
Graduation Date : 2006-05
Supervisor : Dr. Greenstreet

On-chip speeds and integration densities have grown exponentially over the past several decades creating a corresponding demand for high-bandwidth, chip-to-chip communication. Compared with integrated circuit technology, the technologies for chip-packaging, printed circuit boards, and connectors improve at a much slower rate. This results in a big and growing gap between the I/O bandwidth needed and the I/O bandwidth available. Off-chip bandwidth has become a bottleneck in developing high-speed systems. At high data rates, high-frequency losses, reflections and crosstalk severely degrade signal integrity and limit the performance of off-chip links. To combat these issues, designers increasingly rely on on-chip signal processing methods. This thesis explores the effectiveness of equalizing filters for high-bandwidth, point-to- point, off-chip buses. In this work, we combine modelling, optimization and prototyping to demonstrate that linear programming provides practical, effective and flexible basis for designing equalization filters that greatly increase the bandwidth of high-speed buses on printed circuit boards. We first show that the common eye-mask measure of signal integrity is a worst-case performance measure that corresponds to the metric. We show how eye masks can be parameterized to provide a flexible framework for specifying signal integrity trade-offs. We use these parameterized masks to formulate the JQO optimal equalization filter synthesis problem, and show that it can be extended to the unified optimization of pre-equalization, near-end crosstalk cancellation and decision-feedback equalization filters. Our methods work with detailed, realistic channel models and allow the designer to specify practical constraints such as the maximum filter output and' bounds on filter coefficients. Our approach formulates equalization filter synthesis as a linear programming problem. While this makes our approach very flexible, the linear programs that we create can be quite large. To make our methods practical, we implemented a novel linear system solver for use in Mehrotra's interior point linear programming algorithm. Our solver exploits the specific sparsity properties of our optimization problems. We analyze the time and memory requirements of this new implementation as well as its numerical stability.

The role of pre-mRNA secondary structure in gene splicing in Saccharomyces cerevisiae
Rogic, Sanja
DOI : 10.14288/1.0051317
URI : http://hdl.handle.net/2429/18626
Degree : Doctor of Philosophy - PhD
Graduation Date : 2006-11
Supervisors : Dr. Mackworth, Dr. Hoos, Dr. Ouellette (UBC Bioinformatics Centre)

The process of gene splicing, which involves the excision of introns from a pre-mRNA and joining of exons into mature mRNA is one of the essential steps in protein production. Although this process has been extensively studied, it is still not clear how the splice sites are accurately identified and correctly paired across the intron. It is currently believed that identification is accomplished through base-pairing interactions between the splice sites and the spliceosomal snRNAs. However, the relatively conserved sequences at the splice sites are often indistinguishable from similar sequences that are not involved in splicing. This suggests that not only sequence but other features of pre-mRNA may play a role in splicing. A number of authors have studied the effects of pre-mRNA secondary structure on splicing, but these studies are usually limited to one or a small number of genes, and therefore the conclusions are usually gene-specific. This thesis aims to complement previous studies of the role of pre-mRNA secondary structure in splicing by performing a comprehensive computational study of structural characteristics of Saccharomyces cerevisiae introns and their possible role in pre-mRNA splicing. We identify long-range interactions in the secondary structures of all long introns that effectively shorten the distance between the donor site and the branchpoint sequence. The shortened distances are distributed similarly to the branchpoint distances in short yeast introns, which are presumed to be optimal for splicing, and very different from the corresponding distances in random and exonic sequences. We show that in the majority of cases, these stems are conserved among closely related yeast species. Furthermore, we formulate a model of structural requirements for efficient splicing of yeast introns that explains previous splicing studies of the RP51B intron. We also test our model by laboratory experiments, which verify our computational predictions. Finally, we use different computational approaches to identify any structural context at the boundaries or within yeast introns. Our study reveals statistically significant biases, which we use to train machine learning classifiers to distinguish between real and pseudo splice sites.

Probabilistic Inference with Large Discrete Domains
Sharma, Rita
DOI : 10.14288/1.0051316
URI : http://hdl.handle.net/2429/18561
Degree : Doctor of Philosophy - PhD
Graduation Date : 2006-11
Supervisor : Dr. Poole

The straightforward representation of many real world problems is in terms of discrete random variables with large or infinite domains. For example, in a domain where we are trying to identify a person, we may have variables that have as domains, a set of all names, a set of all postal codes, and a set of all credit card numbers. The task usually reduces to performing probabilistic inference, i.e., compute the probability of some values of some random variables given the values of some other variables. Bayesian networks are a compact way to represent joint probability distributions. This thesis is concerned with probabilistic inference in Bayesian networks that have discrete random variables with large or infinite domains. Carrying out inference in Bayesian networks that have variables with large domains is a difficult problem. For efficient inference, we consider cases where there is some structure that can be exploited to make inference efficient. In this thesis we consider two kinds of structures that can be exploited for efficient inference. These structures allow us to partition the large number of values in equivalence classes. Rather than reasoning about every value of a variable individually, we can reason about a set of values in a single step. We first consider the case where there are intensional definitions of the conditional probability distributions. To represent these conditional probabilities, we introduce a CPD language that allows us to define the conditional probabilities procedurally, in terms of predicates and functions. We present an inference algorithm, Large Domain VE, for the CPD language that uses this representation to partitions the domains of the variables dynamically. The partitions depend on what is observed and what is queried. We apply Large Domain VE to the person identification problem that has variables with large domains. The second case we consider where there is a priori internal structure on the values of the variables. In particular, we consider the case where the values of the variables are represented as tree hierarchies. We call such variables hierarchically structured variables. We present a language for representing the conditional probabilities of Bayesian networks with hierarchically structured variables. To perform inference in Bayesian networks with hierarchically structured variables we construct an abstract Bayesian network dynamically, given some evidence and a query, by collapsing the hierarchies to include only those values necessary to answer the query. We can answer the query from the abstract Bayesian network using any standard inference algorithm. Finally, we show how both intensional definitions of the conditional probability distributions and hierarchically structured values can be put together to produce a general framework that can be applied to a more general class of problems.

Novel Heuristic Search Methods for Protein Folding and Identification of Folding Pathways
Shmygelska, Alena
DOI : 10.14288/1.0051759
URI : http://hdl.handle.net/2429/18565
Degree : Doctor of Philosophy - PhD
Graduation Date : 2006-11
Supervisor : Dr. Hoos

Proteins form the very basis of life. If we were to open up any living cell, we would find, apart from DNA and RNA molecules whose primary role is to store genetic information, a large number of different proteins that comprise the cell itself (for example the cell membrane and organelles), as well as a diverse set of enzymes that catalyze various metabolic reactions. If enzymes were absent, the cell would not be able to function, since a number of metabolic reactions would not be possible. Functions of proteins are the consequences of their functional 3D shape. Therefore, to control these versatile properties, we need to be able to predict the 3D shape of proteins; in other words, solve the protein folding problem. The prediction of a protein’s conformation from its amino-acid sequence is currently one of the most prominent problems in molecular biology, biochemistry and bioinformatics. In this thesis, we address the protein folding problem and the closely-related problem of identifying folding pathways. The leading research objective for this work was to design efficient heuristic search algorithms for these problems, to empirically study these new methods and to compare them with existing algorithms. This thesis makes the following contributions: (1) we show that biologically inspired approaches based on the notion of stigmergy--where a collection of agents modifies the environment, and those changes in turn affect the decision process of each agent (particularly artificial colonies of ants that give rise to such properties as self-organization and cooperation also observed in proteins) is a promising field of study for the protein folding problem; (2) we develop a novel adaptive search framework that is used to identify and to bin promising candidate solutions and to adaptively retrieve solutions when the search progress is unsatisfactory; (3) we develop a new method that efficiently explores large search neighbourhoods by performing biased iterated solution construction for identifying folding pathways; and (4) we show that our algorithms efficiently search the vast search landscapes encountered and are able to capture important aspects of the process of protein folding for some widely accepted computational models.

Communicating Emotion Through a Haptic Link: a study of the influence of metaphor, personal space and relationship
Smith, Jocelyn Darlene
DOI : 10.14288/1.0051512
URI : http://hdl.handle.net/2429/18176
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. MacLean

The Importance of Accurate head Registration for Fine Motor Performance in VR
Sprague, David
DOI : 10.14288/1.0051637
URI : http://hdl.handle.net/2429/17616
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Booth, Dr. Fisher

Schema Reintegration Using Generic Schema Manipulation Operators
Sun, Xun
DOI : 10.14288/1.0051766
URI : http://hdl.handle.net/2429/18732
Degree : Master of Science – MSc
Graduation Date : 2006-11
Supervisor : Dr. Pottinger

Comparative Study of Kernel Based Classification and Feature Selection Methods with Gene Expression Data
Tan, Mingyue
DOI : 10.14288/1.0051729
URI : http://hdl.handle.net/2429/18337
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisors : Dr. Ng, Dr. de Freitas

An Epistemological approach to Domain-Specific Multiple Biographical Document Summarization
Tennessy, Blair Douglas
DOI : 10.14288/1.0051642
URI : http://hdl.handle.net/2429/17619
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Carenini

Uniform Support for Modeling Crosscutting Structure
Tkatchenko, Maria A
DOI : 10.14288/1.0051588
URI : http://hdl.handle.net/2429/17806
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Kiczales

Photometric Image Processing for High Dynamic Range Displays
Trentacoste, Matthew
DOI : 10.14288/1.0051400
URI : http://hdl.handle.net/2429/17558
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Heidrich

Better Cloth Through Unbiased Strain Limiting And Physics-Aware Subdivision
Tsiknis, Konstantinos Dinos
DOI : 10.14288/1.0051508
URI : http://hdl.handle.net/2429/18207
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Bridson

Effective Heuristic Methods for DNA Strand Design
Tulpan, Dan Cristian
DOI : 10.14288/1.0051756
URI : http://hdl.handle.net/2429/18592
Degree : Doctor of Philosophy - PhD
Graduation Date : 2006-11
Supervisors : Dr. Condon, Dr. Hoos

Sets of DNA strands that satisfy combinatorial and thermodynamic properties play an important role in various approaches to biomolecular computations, nano structure design, molecular tagging, and DNA microarrays. The problem of designing such sets of DNA strands appears to be computationally hard. This thesis introduces new algorithms for design of DNA strand sets that satisfy any of several combinatorial and thermodynamic constraints, which aim to maximize desired hybridization between strands and their complements, while minimizing undesired cross-hybridizations. To heuristically search for good strand sets for bio-computing applications, our algorithms use a conflict-driven stochastic local search approach, which is known to be effective in solving comparable search problems. We describe new and improved thermodynamic measures of the quality of strand sets. With respect to these measures of quality, our algorithms consistently find, within reasonable time, sets that are significantly better than previously published sets in the literature. We also present a detailed analysis and selection of heuristics for improving the quality of DNA strand selection criteria with direct applications in microarray probe design.

SeMap: A Generic Schema Matching System
Wang, Ting
DOI : 10.14288/1.0051728
URI : http://hdl.handle.net/2429/18322
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Pottinger

Design and Implementation of a Voice-Driven Animation System
Wang, Zhijin
DOI : 10.14288/1.0051586
URI : http://hdl.handle.net/2429/17708
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. van de Panne

Keyframe Animation of Implicit Models
White, David Ian
DOI : 10.14288/1.0051751
URI : http://hdl.handle.net/2429/18380
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Bridson

Secure File System Versioning at the Block Level
Wires, Jake
DOI : 10.14288/1.0051515
URI : http://hdl.handle.net/2429/18183
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Feeley

The Moving Contact Line in a Shallow Water Model
Wong, Albert Christopher
Master’s essay available online : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=214832
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Bridson

Realistic Smoke Simulation Using a Frustum Aligned Grid
Woo, Alan
DOI : 10.14288/1.0051580
URI : http://hdl.handle.net/2429/17818
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Bridson

Coho:  A Verification Tool for Circuit Verification by Reachability Analysis
Yan, Chao
DOI : 10.14288/1.0051509
URI : http://hdl.handle.net/2429/18181
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Greenstreet

Sketch-based Modeling of Parameterized Objects
Yang, Chen
DOI : 10.14288/1.0051583
URI : http://hdl.handle.net/2429/17819
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. van de Panne

MOPAR:  A Mobile Overlay Peer-to-Peer Architecture for Scalable Massively Multiplayer Online Games
Yu, Peiqun
DOI : 10.14288/1.0051587
URI : http://hdl.handle.net/2429/17717
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Vuong

Schema Mediation and Query Processing in Peer Data Management Systems
Zhao, Jie
DOI : 10.14288/1.0051733
URI : http://hdl.handle.net/2429/18358
Degree : Master of Science - MSc
Graduation Date : 2006-11
Supervisor : Dr. Pottinger

Structured Annotations to Support Collaborative Writing Workflow
Zheng, Qixing
DOI : 10.14288/1.0051589
URI : http://hdl.handle.net/2429/17720
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. McGrenere

Animating Sand as a Fluid
Zhu, Yongning
DOI : 10.14288/1.0051582
URI : http://hdl.handle.net/2429/17721
Degree : Master of Science - MSc
Graduation Date : 2006-05
Supervisor : Dr. Bridson