On the complexity of deriving position specific score matrices from positive and negative sequences

DOI10.1016/J.DAM.2004.10.011MaRDI QIDQ876465zbMATH OpenOpenAlexFDO

Authors Tatsuya Akutsu, Hideo Bannai, Satoru Miyano, Sascha Ott

Publication date 18 April 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2004.10.011

zbMATH Keywords

profileNP-hardweight matrixsequence motifposition specific score matrix

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 2087052
• The complexity of multiple sequence alignment with SP-score that is a metric
• Calculating PSSM probabilities with lazy dynamic programming
• An upper bound on the hardness of exact matrix based motif discovery
• Complexity of biological sequence alignment

Cites work

• scientific article; zbMATH DE number 996385 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305456 (Why is no real title available?)
• A new polynomial-time algorithm for linear programming
• Biological Sequence Analysis
• Finding similar regions in many strings
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Optimization, approximation, and complexity classes
• Zero knowledge and the chromatic number

Cited in

(3)

• scientific article; zbMATH DE number 2087052 (Why is no real title available?)
• Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings
• Calculating PSSM probabilities with lazy dynamic programming

Describes a project that uses

Uses Software

• AAindex

This page was built for publication: On the complexity of deriving position specific score matrices from positive and negative sequences

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