Separating significant matches from spurious matches in DNA sequences

Finding Statistically Significant Repeats in Nucleic Acids and Proteins

DNA repeats have great importance for biological research and a large number of tools for determining repeats have been developed. Herein we define a method for extracting a statistically significant subset of a determined set of repeats. Our aim was to identify a subset of repeats in the input sequences that are not expected to occur with a number of their appearances in a random sequence of the same length. It is expected that results obtained in such manner would reduce the quantity of processed material and could thereby represent a more important biological signal. With DNA, RNA, and protein sequences serving as input material, we also examined the possibility of statistical filtering of repeats in sequences over an arbitrary alphabet. A new method for selecting statistically significant repeats from a set of determined repeats has been defined. The proposed method was tested on a large number of randomly generated sequences. The application of the method on biological sequences revealed that for some viruses, shorter repeats are more statistically significant than longer ones because of their frequent appearance, whereas for bacteria, the majority of identified repeats are statistically significant.

Fast and accurate phylogeny reconstruction using filtered spaced-word matches

Motivation

Word-based or ‘alignment-free’ algorithms are increasingly used for phylogeny reconstruction and genome comparison, since they are much faster than traditional approaches that are based on full sequence alignments. Existing alignment-free programs, however, are less accurate than alignment-based methods.

Results

We propose Filtered Spaced Word Matches (FSWM), a fast alignment-free approach to estimate phylogenetic distances between large genomic sequences. For a pre-defined binary pattern of match and don’t-care positions, FSWM rapidly identifies spaced word-matches between input sequences, i.e. gap-free local alignments with matching nucleotides at the match positions and with mismatches allowed at the don’t-care positions. We then estimate the number of nucleotide substitutions per site by considering the nucleotides aligned at the don’t-care positions of the identified spaced-word matches. To reduce the noise from spurious random matches, we use a filtering procedure where we discard all spaced-word matches for which the overall similarity between the aligned segments is below a threshold. We show that our approach can accurately estimate substitution frequencies even for distantly related sequences that cannot be analyzed with existing alignment-free methods; phylogenetic trees constructed with FSWM distances are of high quality. A program run on a pair of eukaryotic genomes of a few hundred Mb each takes a few minutes.

Availability and Implementation

The program source code for FSWM including a documentation, as well as the software that we used to generate artificial genome sequences are freely available at http://fswm.gobics.de/

Supplementary information

Supplementary data are available at Bioinformatics online.

Accurate Prediction of the Statistics of Repetitions in Random Sequences: A Case Study in Archaea Genomes

Repetitive patterns in genomic sequences have a great biological significance and also algorithmic implications. Analytic combinatorics allow to derive formula for the expected length of repetitions in a random sequence. Asymptotic results, which generalize previous works on a binary alphabet, are easily computable. Simulations on random sequences show their accuracy. As an application, the sample case of Archaea genomes illustrates how biological sequences may differ from random sequences.

Threshold group testing on inhibitor model

In classical group testing, one is given a population [Formula: see text] and an unknown subset [Formula: see text] of positive items, and the goal is to determine D by testing subsets of [Formula: see text]. Threshold group testing is a generalization of classical group testing, where the outcome of a group test is determined by the number of positive items in the test. In group testing on inhibitor model, inhibitors are the third type of item that dictate the test outcome to be negative regardless of how many positives are in the test. The threshold group testing on k-inhibitor model is a natural combination of threshold group testing and inhibitor model. In this article, we provide nonadaptive algorithms to conquer the threshold group testing on k-inhibitor model where error-tolerance is considered. Furthermore, we provide a two-stage algorithm to identify all inhibitors and find a g-approximate set.