@article {49599, title = {BlindCall: ultra-fast base-calling of high-throughput sequencing data by blind deconvolution.}, volume = {30}, year = {2014}, month = {2014 May 1}, pages = {1214-9}, abstract = {

MOTIVATION: Base-calling of sequencing data produced by high-throughput sequencing platforms is a fundamental process in current bioinformatics analysis. However, existing third-party probabilistic or machine-learning methods that significantly improve the accuracy of base-calls on these platforms are impractical for production use due to their computational inefficiency.

RESULTS: We directly formulate base-calling as a blind deconvolution problem and implemented BlindCall as an efficient solver to this inverse problem. BlindCall produced base-calls at accuracy comparable to state-of-the-art probabilistic methods while processing data at rates 10 times faster in most cases. The computational complexity of BlindCall scales linearly with read length making it better suited for new long-read sequencing technologies.

}, keywords = {algorithms, High-Throughput Nucleotide Sequencing, HUMANS, Probability, Reproducibility of Results, Sequence Analysis, DNA, software, Time factors}, issn = {1367-4811}, doi = {10.1093/bioinformatics/btu010}, author = {Ye, Chengxi and Hsiao, Chiaowen and Corrada Bravo, Hector} } @article {49560, title = {MCMC data association and sparse factorization updating for real time multitarget tracking with merged and multiple measurements.}, volume = {28}, year = {2006}, month = {2006 Dec}, pages = {1960-72}, abstract = {

In several multitarget tracking applications, a target may return more than one measurement per target and interacting targets may return multiple merged measurements between targets. Existing algorithms for tracking and data association, initially applied to radar tracking, do not adequately address these types of measurements. Here, we introduce a probabilistic model for interacting targets that addresses both types of measurements simultaneously. We provide an algorithm for approximate inference in this model using a Markov chain Monte Carlo (MCMC)-based auxiliary variable particle filter. We Rao-Blackwellize the Markov chain to eliminate sampling over the continuous state space of the targets. A major contribution of this work is the use of sparse least squares updating and downdating techniques, which significantly reduce the computational cost per iteration of the Markov chain. Also, when combined with a simple heuristic, they enable the algorithm to correctly focus computation on interacting targets. We include experimental results on a challenging simulation sequence. We test the accuracy of the algorithm using two sensor modalities, video, and laser range data. We also show the algorithm exhibits real time performance on a conventional PC.

}, keywords = {algorithms, Artificial Intelligence, Image Enhancement, Image Interpretation, Computer-Assisted, Information Storage and Retrieval, Movement, Pattern Recognition, Automated, Reproducibility of Results, Sensitivity and Specificity, Subtraction Technique}, issn = {0162-8828}, doi = {10.1109/TPAMI.2006.247}, author = {Khan, Zia and Balch, Tucker and Dellaert, Frank} }