A new statistic for efficient detection of repetitive sequences

Sijie Chen; Yixin Chen; Fengzhu Sun; Michael S Waterman; Xuegong Zhang

doi:10.1093/bioinformatics/btz262

A new statistic for efficient detection of repetitive sequences

Bioinformatics. 2019 Nov 1;35(22):4596-4606. doi: 10.1093/bioinformatics/btz262.

Authors

Sijie Chen¹, Yixin Chen¹, Fengzhu Sun^{2

3}, Michael S Waterman^{1

2

3}, Xuegong Zhang^{1

4}

Affiliations

¹ Department of Automation, MOE Key Laboratory of Bioinformatics, Bioinformatics Division and Center for Synthetic & Systems Biology, BNRist, Tsinghua University, Beijing 100084, China.
² Quantitative and Computational Biology Program, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089, USA.
³ Institute of Science and Technology for Brain-Inspired Intelligence, Fudan University, Shanghai 200433, China.
⁴ School of Life Sciences, Tsinghua University, Beijing 100084, China.

Abstract

Motivation: Detecting sequences containing repetitive regions is a basic bioinformatics task with many applications. Several methods have been developed for various types of repeat detection tasks. An efficient generic method for detecting most types of repetitive sequences is still desirable. Inspired by the excellent properties and successful applications of the D2 family of statistics in comparative analyses of genomic sequences, we developed a new statistic D2R that can efficiently discriminate sequences with or without repetitive regions.

Results: Using the statistic, we developed an algorithm of linear time and space complexity for detecting most types of repetitive sequences in multiple scenarios, including finding candidate clustered regularly interspaced short palindromic repeats regions from bacterial genomic or metagenomics sequences. Simulation and real data experiments show that the method works well on both assembled sequences and unassembled short reads.

Availability and implementation: The codes are available at https://github.com/XuegongLab/D2R_codes under GPL 3.0 license.

Supplementary information: Supplementary data are available at Bioinformatics online.

Publication types

Research Support, N.I.H., Extramural
Research Support, Non-U.S. Gov't
Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

Algorithms
Clustered Regularly Interspaced Short Palindromic Repeats*
Genome, Bacterial
Genomics*
Metagenomics

Grants and funding

R01 GM120624/GM/NIGMS NIH HHS/United States