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

DOI10.1016/j.dam.2004.10.011zbMath1111.68027OpenAlexW2018936944MaRDI QIDQ876465

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

zbMATH Keywords

profileNP-hardweight matrixsequence motifposition specific score matrix

Mathematics Subject Classification ID

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

Related Items (1)

Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings

Uses Software

• AAindex

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Optimization, approximation, and complexity classes
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Zero knowledge and the chromatic number
• Finding similar regions in many strings
• Biological Sequence Analysis

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