Finding optimal parameters for edit distance based sequence classification is NP-hard.
Vlado KeseljHaibin LiuNorbert ZehChristian BlouinChris WhiddenPublished in: KDD Workshop on Statistical and Relational Learning in Bioinformatics (2009)
Keyphrases
- finding optimal
- sequence classification
- np hard
- sequence data
- hidden markov models
- special case
- markov models
- optimal solution
- computational complexity
- approximation algorithms
- conditional random fields
- expectation maximization
- state space
- distance measure
- graphical models
- prior knowledge
- lower bound
- search algorithm