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

DOI10.1016/J.DAM.2004.10.011zbMATH Open1111.68027OpenAlexW2018936944MaRDI QIDQ876465FDOQ876465

Sascha Ott, Tatsuya Akutsu, Satoru Miyano, Hideo Bannai

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

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

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)

Cites Work

• Biological Sequence Analysis
• A new polynomial-time algorithm for linear programming
• Title not available (Why is that?)
• Optimization, approximation, and complexity classes
• Title not available (Why is that?)
• Zero knowledge and the chromatic number
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Finding similar regions in many strings
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings
• Calculating PSSM probabilities with lazy dynamic programming
• Title not available (Why is that?)

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)