Please use this identifier to cite or link to this item:
|Title:||Parametric sequence alignment with constraints|
Computational molecular biology
|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.|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 12, 2017
checked on Dec 15, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.