Please use this identifier to cite or link to this item: https://doi.org/10.1023/A:1011429504996
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
Source: Yap, R.H.C. (2001). Parametric sequence alignment with constraints. Constraints 6 (2-3) : 157-172. ScholarBank@NUS Repository. https://doi.org/10.1023/A:1011429504996
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39243
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.

SCOPUSTM   
Citations

5
checked on Dec 12, 2017

Page view(s)

65
checked on Dec 15, 2017

Google ScholarTM

Check

Altmetric


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