Spaced Seed Coverage as a Measure of Pattern Clumping

• Activity Number: 490
• Type: Contributed
• Date/Time: Wednesday, August 7, 2013 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Computing
• Author(s): Donald Martin*+
• Companies: NC State University
• Keywords: minimal deterministic finite automaton ; spaced seed ; success runs ; seed coverage

Abstract

In computational biology, spaced seeds are used to improve sensitivity of the initial stage of alignment searches without simultaneously increasing the number of random hits. In this paper, we first give an efficient method to compute the distribution of the number of positions of a sequence that are included (covered) in spaced seeds hits. We then compute the power of this statistic for testing the null hypothesis of independent binary trials with a constant success probability versus alternatives that include dependency and nonstationarity. The power will be compared to that of coverage of contiguous seeds, as well as scans statistics and other that are typically used to detect clumping of successes. The underlying sequence will be assumed to be Markovian of a fixed, but arbitrary, order of dependence.