Computer Science Technical Reports
2006
-
CS-2006-01 (94 pages) (pdf)
Abstract
Sequence comparison is one of the most primitive operations used in bio-informatics. It is used as a basis for many other complex manipulations in the field of Computational Molecular Biology. Many methods and algorithms were developed to compare and align sequences effectively. Most of these methods use linear comparison and some standard scoring schemes to calculate the similarity between sequences. We described an alternative approach to compare sequences based on the correlogram method. This method has already been used in the past for comparing images. By using the correlogram method, a sequence is projected on a 3-D space and the difference between two sequences is calculated. This research describes construction of a correlogram and how correlograms can be used for sequence comparison. It also adds additional functionality to the basic correlogram method. Experiments with protein sequences corresponding to different strains of influenza virus and parvo virus will be described and the phylogeny/evolutionary trees constructed using the correlogram method will be compared, with the ones available in literature.
-
CS-2006-02 (92 pages) (pdf)
Abstract
This thesis is a confluence of three problems in constraint reasoning: qualitative temporal reasoning (QTR), incremental reasoning, and explanation generation. We first address a set of algorithms to solve the QTR for point algebra (PA) with explanation. Next, we turn to the tractable form of Allen's Interval Algebra (IA). For both problems, an incremental version of the problem, where a new temporal object is added to a set of objects committed on the time-line, is being studied. We provide a model or solution space for the new object, if it exists, otherwise, for (PA) and a particular sub-algebra of (IA) called ORD-Horn, we provide explanation for inconsistency. Both the problems of incremental reasoning and explanation generation are based on some recent investigation in constraint programming.
-
CS-2006-03 (11 pages) (pdf)
Abstract
Here we show how the idea of dynamic backtracking can be applied to branch and bound optimization. This is done by exploiting the concept of valued nogood. However, simple replacement of nogoods with valued nogoods does not lead to a correct algorithm. We show that a way to achieve correctness is to use at each variable a separate nogood storage for each position that the variable holds in the order on assigned variables. This is a different version to the one in [dago97].
Constraint Satisfaction Problems (CSPs) are typically addressed with some kind of backtracking algorithm. A seminal work that helped to deeply understand and unify many backtracking algorithms was [Ginsberg93]'s dynamic backtracking (DB). Optimization problems are often solved with branch and bound (B&B) algorithms, a family of algorithms related to backtracking. However, no equivalent of DB's heuristic was so far developed for branch and bound. The algorithm proposed here, Dynamic Branch & Bound (DBB), is optimal and guaranteed to terminate, having polynomial space complexity and a reordering policy similar to Dynamic Backtracking. The experimentation performed validates the correctness of the theory. Like Dynamic Backtracking, whose reordering heuristic is known to be rather inefficient, the interest of the proposed algorithm is shown to be mainly theoretical.
-
CS-2006-04 (6 pages) (pdf)
Abstract
Using N-Version programming techniques to increase software reliability is a well-explored field. In this paper, we extend the concept to the detection of new security vulnerabilities. Using our own N-Version arbiter, Judicare, we implement a simple auction web application, and demonstrate how our application is robust to the most common Web vulnerabilities as documented by OWASP. Finally, we discuss the implications of our results in the context of detection of Zero-Day attacks.