An Average-Case Sublinear Exact Li and Stephens Forward Algorithm

DOI10.4230/LIPICS.WABI.2018.9MaRDI QIDQ5090334zbMATH OpenOpenAlexFDO

Authors Yohei Rosen, Benedict Paten

Publication date 18 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/9311/pdf/LIPIcs-WABI-2018-9.pdf/

zbMATH Keywords

hidden Markov modelforward algorithmhaplotypelazy evaluation

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Computational methods for problems pertaining to biology (92-08)

Recommendations

• A fast average case algorithm for lyndon decomposition
• Sublinear time algorithms for approximate semidefinite programming
• Two linear approximation algorithms for the subset-sum problem
• scientific article; zbMATH DE number 1104339
• Subsampling mathematical relaxations and average-case complexity
• Average case optimal algorithms in Hilbert spaces
• On the complexity of the Lickteig-Roy subresultant algorithm
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• scientific article; zbMATH DE number 176777
• A near-linear pseudopolynomial time algorithm for subset sum

Cites work

• Describing the local structure of sequence graphs
• The coalescent
• The coalescent and its descendants

Cited in

(2)

• On reducing the statespace of hidden Markov models for the identity by descent process
• A fast average case algorithm for lyndon decomposition

This page was built for publication: An Average-Case Sublinear Exact Li and Stephens Forward Algorithm

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