Computing and Information Systems - Research Publications
Permanent URI for this collection
Search Results
1 - 10 of 12
-
ItemPrincipal type inference for GHC-style multi-parameter type classes(SPRINGER-VERLAG BERLIN, 2006)
-
ItemDiscovery of minimal unsatisfiable subsets of constraints using hitting set dualization(SPRINGER-VERLAG BERLIN, 2005)
-
ItemPropagating Dense Systems of Integer Linear Equations(ASSOC COMPUTING MACHINERY, 2007)
-
ItemPropagation = Lazy Clause Generation(Springer Verlag, 2007)
-
ItemFast node overlap removal(SPRINGER-VERLAG BERLIN, 2006)
-
ItemIncremental connector routing(SPRINGER-VERLAG BERLIN, 2006)
-
ItemMUSTANG: A multiple structural alignment algorithm(WILEY, 2006-08-15)Multiple structural alignment is a fundamental problem in structural genomics. In this article, we define a reliable and robust algorithm, MUSTANG (MUltiple STructural AligNment AlGorithm), for the alignment of multiple protein structures. Given a set of protein structures, the program constructs a multiple alignment using the spatial information of the C(alpha) atoms in the set. Broadly based on the progressive pairwise heuristic, this algorithm gains accuracy through novel and effective refinement phases. MUSTANG reports the multiple sequence alignment and the corresponding superposition of structures. Alignments generated by MUSTANG are compared with several handcurated alignments in the literature as well as with the benchmark alignments of 1033 alignment families from the HOMSTRAD database. The performance of MUSTANG was compared with DALI at a pairwise level, and with other multiple structural alignment tools such as POSA, CE-MC, MALECON, and MultiProt. MUSTANG performs comparably to popular pairwise and multiple structural alignment tools for closely related proteins, and performs more reliably than other multiple structural alignment methods on hard data sets containing distantly related proteins or proteins that show conformational changes.
-
ItemThe island confinement method for reducing search space in local search methods(SPRINGER, 2007-12)
-
ItemOptimal sum-of-pairs multiple sequence alignment using incremental Carrillo and Lipman bounds(MARY ANN LIEBERT, INC, 2006-04)Alignment of sequences is an important routine in various areas of science, notably molecular biology. Multiple sequence alignment is a computationally hard optimization problem which involves the consideration of different possible alignments in order to find an optimal one, given a measure of goodness of alignments. Dynamic programming algorithms are generally well suited for the search of optimal alignments, but are constrained by unwieldy space requirements for large numbers of sequences. Carrillo and Lipman devised a method that helps to reduce the search space for an optimal alignment under a sum-of-pairs measure using bounds on the scores of its pairwise projections. In this paper, we generalize Carrillo and Lipman bounds and demonstrate a novel approach for finding optimal sum-of-pairs multiple alignments that allows incremental pruning of the optimal alignment search space. This approach can result in a drastic pruning of the final search space polytope (where we search for the optimal alignment) when compared to Carrillo and Lipman's approach and hence allows many runs that are not feasible with the original method.
-
ItemSolving set constraint satisfaction problems using ROBDDS(AI ACCESS FOUNDATION, 2005)In this paper we present a new approach to modeling finite set domain constraint problems using Reduced Ordered Binary Decision Diagrams (ROBDDs). We show that it is possible to construct an efficient set domain propagator which compactly represents many set domains and set constraints using ROBDDs. We demonstrate that the ROBDD-based approach provides unprecedented flexibility in modeling constraint satisfaction problems, leading to performance improvements. We also show that the ROBDD-based modeling approach can be extended to the modeling of integer and multiset constraint problems in a straightforward manner. Since domain propagation is not always practical, we also show how to incorporate less strict consistency notions into the ROBDD framework, such as set bounds, cardinality bounds and lexicographic bounds consistency. Finally, we present experimental results that demonstrate the ROBDD-based solver performs better than various more conventional constraint solvers on several standard set constraint problems.