APPROXIMATION ALGORITHMS FOR LOCAL ALIGNMENT WITH LENGTH CONSTRAINTS

DOI10.1142/S0129054102001436MaRDI QIDQ3021984zbMATH OpenFDO

Authors Abdullah N. Arslan, Ömer Eğecioğlu

Publication date 22 June 2005

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054102001436

zbMATH Keywords

approximation algorithmcyclic edit distanceedit distancelocal sequence alignment

Mathematics Subject Classification ID

Approximation algorithms (68W25) Dynamic programming (90C39) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20)

Recommendations

• scientific article; zbMATH DE number 2086217
• Dynamic programming based approximation algorithms for sequence alignment with constraints
• Bounded-length Smith-Waterman alignment
• Constrained sequence alignment
• Linear-space algorithms that build local alignments from fragments

Cites work

• A time-efficient, linar-space local similarity algorithm
• An improved algorithm for solving the banded cyclic string-to-string correction problem
• Incremental String Comparison
• Locally optimal subalignments using nonlinear similarity functions
• On a cyclic string-to-string correction problem
• The String-to-String Correction Problem

Cited in

(11)

• Hardness of approximation for non-overlapping local alignments.
• Tandem cyclic alignment
• Linear-space algorithms that build local alignments from fragments
• Global and local sequence alignment with a bounded number of gaps
• Dynamic programming based approximation algorithms for sequence alignment with constraints
• scientific article; zbMATH DE number 2086217 (Why is no real title available?)
• scientific article; zbMATH DE number 1996311 (Why is no real title available?)
• scientific article; zbMATH DE number 1786451 (Why is no real title available?)
• Computing and Combinatorics
• Bounded-length Smith-Waterman alignment
• Variable length local decoding and alignment-free sequence comparison

This page was built for publication: APPROXIMATION ALGORITHMS FOR LOCAL ALIGNMENT WITH LENGTH CONSTRAINTS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3021984)