An Average-Case Sublinear Exact Li and Stephens Forward Algorithm

DOI10.4230/LIPICS.WABI.2018.9zbMATH Open1494.92073OpenAlexW2952523533MaRDI QIDQ5090334FDOQ5090334

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/

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

zbMATH Keywords

hidden Markov modelforward algorithmhaplotypelazy evaluation

Mathematics Subject Classification ID

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

Cites Work

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

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)