Please use this identifier to cite or link to this item:
Title: Parametric sequence alignment with constraints
Authors: Yap, R.H.C. 
Keywords: Approximate matching
Computational molecular biology
Constraint programming
Parametric alignment
String alignment
Issue Date: 2001
Citation: Yap, R.H.C. (2001). Parametric sequence alignment with constraints. Constraints 6 (2-3) : 157-172. ScholarBank@NUS Repository.
Abstract: Approximate matching techniques based on string alignment are important tools for investigating similarities between strings, such as those representing DNA and protein sequences. We propose a constraint based approach for parametric sequence alignment which allows for more general string alignment queries where the alignment cost can itself be parameterized as a query with some initial constraints. Thus, the costs need not be fixed in a parametric alignment query unlike the case in normal alignment. The basic dynamic programming string edit distance algorithm is generalized to a naive algorithm which uses inequalities to represent the alignment score. The naive algorithm is rather costly and the remainder of the paper develops an improvement which prunes alternatives where it can and approximates the alternatives otherwise. This reduces the number of inequalities significantly and strengthens the constraint representation with equalities. We present some preliminary results using parametric alignment on some general alignment queries.
Source Title: Constraints
ISSN: 13837133
DOI: 10.1023/A:1011429504996
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on May 15, 2019

Page view(s)

checked on May 17, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.