IngentaConnect The consensus string problem and the complexity of comparing hidd...

Authors: Lyngsø R.B.¹; Pedersen C.N.S.²

Source: Journal of Computer and System Sciences, Volume 65, Number 3, November 2002 , pp. 545-569(25)

Abstract:

The basic theory of hidden Markov models was developed and applied to problems in speech recognition in the late 1960s, and has since then been applied to numerous problems, e.g. biological sequence analysis. Most applications of hidden Markov models are based on efficient algorithms for computing the probability of generating a given string, or computing the most likely path generating a given string. In this paper we consider the problem of computing the most likely string, or consensus string, generated by a given model, and its implications on the complexity of comparing hidden Markov models. We show that computing the consensus string, and approximating its probability within any constant factor, isNP-hard, and that the same holds for the closely related labeling problem for class hidden Markov models. Furthermore, we establish theNP-hardness of comparing two hidden Markov models under theL- andL₁-norms. We discuss the applicability of the technique used for proving the hardness of comparing two hidden Markov models under theL₁-norm to other measures of distance between probability distributions. In particular, we show that it cannot be used for provingNP-hardness of determining the Kullback–Leibler distance between two hidden Markov models, or of comparing them under the L_k-norm for any fixed even integer k.

Language: English

Document Type: Research article

DOI: 10.1016/S0022-0000(02)00009-0

Affiliations: 1: Department of Computer Science, University of California at Santa Cruz, Santa Cruz, CA 95064, USA 2: BRICS, Department of Computer Science, University of Aarhus, 8000 A ring rhus C, Denmarkrhus C, Denmark">

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$54.38 plus tax Refund Policy

The consensus string problem and the complexity of comparing hidden Markov models