Speeding up HMM decoding and training by exploiting sequence repetitions

DOI10.1007/S00453-007-9128-0MaRDI QIDQ834590zbMATHOpenAlexWikidataFDO

Authors Yury Lifshits, Shay Mozes, Oren Weimann, Michal Ziv-Ukelson

Publication date 27 August 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9128-0

zbMATH Keywords

HMMdynamic programmingcompressionViterbi

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
• Viterbi algorithms for hidden semi-Markov models with application to DNA analysis
• The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection
• A coarse-to-fine approach to computing the \(k\)-best Viterbi paths
• scientific article; zbMATH DE number 1099037

Cites work

• scientific article; zbMATH DE number 1615281 (Why is no real title available?)
• scientific article; zbMATH DE number 1629861 (Why is no real title available?)
• scientific article; zbMATH DE number 2119727 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• A universal algorithm for sequential data compression
• Algorithms and Data Structures
• An improved algorithm for computing the edit distance of run-length coded strings
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Edit distance of run-length encoded strings.
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• Gaussian elimination is not optimal
• Hidden Markov chains and the analysis of genome structure
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Matching for run-length encoded strings
• Matrix multiplication via arithmetic progressions
• More algorithms for all-pairs shortest paths in weighted graphs
• On the Complexity of Finite Sequences
• Processing Compressed Texts: A Tractability Border
• Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
• Window Subsequence Problems for Compressed Texts

Cited in

(6)

• Textual data compression in computational biology: algorithmic techniques
• \texttt{CarpeDiem}: optimizing the Viterbi algorithm and applications to supervised sequential learning
• Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions
• A faster algorithm for the computation of string convolutions using LZ78 parsing
• The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection
• Accelerating Viterbi algorithm on graphics processing units

This page was built for publication: Speeding up HMM decoding and training by exploiting sequence repetitions

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