A binary search approach to whole-genome data analysis.
A sequence analysis-oriented binary search-like algorithm was transformed to a sensitive and accurate analysis tool for processing whole-genome data. The advantage of the algorithm over previous methods is its ability to detect the margins of both short and long genome fragments, enriched by up-regulated signals, at equal accuracy. The score of an enriched genome fragment reflects the difference between the actual concentration of up-regulated signals in the fragment and the chromosome signal baseline. The "divide-and-conquer"-type algorithm detects a series of nonintersecting fragments of various lengths with locally optimal scores. The procedure is applied to detected fragments in a nested manner by recalculating the lower-than-baseline signals in the chromosome. The algorithm was applied to simulated whole-genome data, and its sensitivity/specificity were compared with those of several alternative algorithms. The algorithm was also tested with four biological tiling array datasets comprising Arabidopsis (i) expression and (ii) histone 3 lysine 27 trimethylation CHIP-on-chip datasets; Saccharomyces cerevisiae (iii) spliced intron data and (iv) chromatin remodeling factor binding sites. The analyses' results demonstrate the power of the algorithm in identifying both the short up-regulated fragments (such as exons and transcription factor binding sites) and the long--even moderately up-regulated zones--at their precise genome margins. The algorithm generates an accurate whole-genome landscape that could be used for cross-comparison of signals across the same genome in evolutionary and general genomic studies.
Brodsky
Leonid
L
Institute of Evolution, University of Haifa, Mount Carmel, Haifa 31905, Israel. lbrodsky@research.haifa.ac.il
Kogan
Simon
S
Benjacob
Eshel
E
Nevo
Eviatar
E
D000465:Algorithms; D017360:Arabidopsis / Q000235:genetics; D002874:Chromosome Mapping / Q000706:statistics & numerical data; D020869:Gene Expression Profiling / Q000706:statistics & numerical data; D055106:Genome-Wide Association Study / Q000706:statistics & numerical data*; D007438:Introns; D020411:Oligonucleotide Array Sequence Analysis / Q000706:statistics & numerical data; D012326:RNA Splicing; D012441:Saccharomyces cerevisiae / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*