FastLSU: A Linear Implementation for Controlling the False Discovery Rate

Abstract

Large-scale hypothesis testing is an important experimental procedure in the field of bioinformatics. Often times, researchers would like to control the rate of false positives that appear in their experiments. A current method to control this rate - false discovery rate - is known as Linear Step Up from Benjamini and Hochberg (1995). Linear Step up does control the false discovery rate, but it has a linearithmic time complexity, which does not scale well for tests on the order of 107 or larger. Professors Vered Madar and Sandra Batista proposed an alternative algorithm called FastLSU that applies linear scans over the data set to control the false discovery rate, albeit in a linear fashion as opposed to a linearithmic one. In this project, we aimed to successfully implement the algorithm for use on individual machines in a manner that maximizes efficiency while minimizing memory usage and created a simple graphical user interface that researchers can easily use to control the false discovery rate in their experiments.