Maximum likelihood DNA sequence detection via sphere decoding
- 1 January 2010
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2010 IEEE International Conference on Acoustics, Speech and Signal Processing
Abstract
In sequencing-by-synthesis systems, determining the order of nucleotides of a DNA fragment can be cast as an ML sequence detection (MLSD) problem. Solving it via exhaustive search is prohibitive even for relatively short DNA sequences. Symbol-by-symbol and partial-MLSD solutions are computationally feasible but sacrifice the optimal performance. In this paper, we modify the so-called sphere decoding algorithm to efficiently solve the MLSD problem in sequencing-by-synthesis systems. We analyze the expected complexity of the algorithm, and demonstrate via simulations that it significantly outperforms heuristic techniques.Keywords
This publication has 5 references indexed in Scilit:
- Recovering the state sequence of hidden Markov models using mean-field approximationsJournal of Statistical Mechanics: Theory and Experiment, 2009
- Advanced sequencing technologies and their wider impact in microbiologyJournal of Experimental Biology, 2007
- Modeling and base-calling for Dna Sequencing-By-SynthesisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- On the sphere-decoding algorithm I. Expected complexityIEEE Transactions on Signal Processing, 2005
- Improved methods for calculating vectors of short length in a lattice, including a complexity analysisMathematics of Computation, 1985