Please use this identifier to cite or link to this item: https://doi.org/10.1142/S0219720005000862
Title: Adaptive control of hybridization noise in dna sequencing-by-hybridization
Authors: Leong, H.-W. 
Preparata, F.P.
Sung, W.-K. 
Willy, H. 
Keywords: False negatives
Gapped probes
Graceful degradation
Hybridization errors
Microarrays
Sequencing-by-hybridization
Issue Date: 2005
Source: Leong, H.-W.,Preparata, F.P.,Sung, W.-K.,Willy, H. (2005). Adaptive control of hybridization noise in dna sequencing-by-hybridization. Journal of Bioinformatics and Computational Biology 3 (1) : 79-98. ScholarBank@NUS Repository. https://doi.org/10.1142/S0219720005000862
Abstract: We consider the problem of sequence reconstruction in sequencing-by-hybridization in the presence of spectrum errors. As suggested by intuition, and reported in the literature, false-negatives (i.e., missing spectrum probes) are by far the leading cause of reconstruction failures. In a recent paper we have described an algorithm, called "threshold-θ", designed to recover from false negatives. This algorithm is based on overcompensating for missing extensions by allowing larger reconstruction subtrees. We demonstrated, both analytically and with simulations, the increasing effectiveness of the approach as the parameter θ grows, but also pointed out that for larger error rates the size of the extension trees translates into an unacceptable computational burden. To obviate this shortcoming, in this paper we propose an adaptive approach which is both effective and efficient. Effective, because for a fixed value of θ it performs as well as its single-threshold counterpart, efficient because it exhibits substantial speed-ups over it. The idea is that, for moderate error rates a small fraction of the target sequence can be involved in error recovery; thus, expectedly the remainder of the sequence is reconstructible by the standard noiseless algorithm, with the provision to switch to operation with increasingly higher thresholds after detecting failure. This policy generates interesting and complex interplays between fooling probes and false negatives. These phenomena are carefully analyzed for random sequences and the results are found to be in excellent agreement with the simulations. In addition, the experimental algorithmic speed-ups of the multithreshold approach are explained in terms of the interaction amongst the different threshold regimes. © Imperial College Press.
Source Title: Journal of Bioinformatics and Computational Biology
URI: http://scholarbank.nus.edu.sg/handle/10635/39112
ISSN: 02197200
DOI: 10.1142/S0219720005000862
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Dec 12, 2017

Page view(s)

61
checked on Dec 15, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.