Parameterized Complexity and Biopolymer Sequence Comparison

The paper surveys parameterized algorithms and complexities for computational tasks on biopolymer sequences, including the problems of longest common subsequence, shortest common supersequence, pairwise sequence alignment, multiple sequencing alignment, structure-sequence alignment and structure-str...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2008-05, Vol.51 (3), p.270-291
Main Authors: Cai, Liming, Huang, Xiuzhen, Liu, Chunmei, Rosamond, Frances, Song, Yinglei
Format: Article
Language:English
Subjects:
Algorithms
Amino acids
Approximation
Biopolymers
Computer science
Genes
Parameter optimization
Proteins
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The paper surveys parameterized algorithms and complexities for computational tasks on biopolymer sequences, including the problems of longest common subsequence, shortest common supersequence, pairwise sequence alignment, multiple sequencing alignment, structure-sequence alignment and structure-structure alignment. Algorithm techniques, built on the structural-unit level as well as on the residue level, are discussed.
ISSN:0010-4620
1460-2067
0010-4620
DOI:10.1093/comjnl/bxm035