Efficient Pseudomedian Filter for Tiling Microarrays
Author Information
Author(s): Royce Thomas E, Carriero Nicholas J, Gerstein Mark B
Primary Institution: Yale University
Hypothesis
Can we improve the efficiency of pseudomedian calculations in tiling microarray analyses?
Conclusion
We have significantly reduced the computation time for pseudomedian calculations in tiling microarray analyses by implementing efficient algorithms.
Supporting Evidence
- The new algorithm reduced the runtime of pseudomedian calculations by nearly 90%.
- Maintaining a sorted list of values from window to window cut run times by an additional 43%.
- The original pseudomedian filter's runtimes can be improved by 93%.
Takeaway
This study shows how to make analyzing DNA data faster by using smarter math tricks, which helps scientists work with more information quickly.
Methodology
We implemented Monahan's HLQEST algorithm to reduce the runtime complexity for computing the pseudomedian and used skip lists to maintain sorted values across sliding windows.
Limitations
The study does not assess the sensitivity gained by using pseudomedian filters in tiling array analyses.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website