当前位置： SCI文献检索 > BMC BIOINFORMATICS期刊下所有文献 > iSeg: an efficient algorithm for segmentation of genomic and epigenomic data.

iSeg: an efficient algorithm for segmentation of genomic and epigenomic data.

Abstract：

BACKGROUND:Identification of functional elements of a genome often requires dividing a sequence of measurements along a genome into segments where adjacent segments have different properties, such as different mean values. Despite dozens of algorithms developed to address this problem in genomics research, methods with improved accuracy and speed are still needed to effectively tackle both existing and emerging genomic and epigenomic segmentation problems. RESULTS:We designed an efficient algorithm, called iSeg, for segmentation of genomic and epigenomic profiles. iSeg first utilizes dynamic programming to identify candidate segments and test for significance. It then uses a novel data structure based on two coupled balanced binary trees to detect overlapping significant segments and update them simultaneously during searching and refinement stages. Refinement and merging of significant segments are performed at the end to generate the final set of segments. By using an objective function based on the p-values of the segments, the algorithm can serve as a general computational framework to be combined with different assumptions on the distributions of the data. As a general segmentation method, it can segment different types of genomic and epigenomic data, such as DNA copy number variation, nucleosome occupancy, nuclease sensitivity, and differential nuclease sensitivity data. Using simple t-tests to compute p-values across multiple datasets of different types, we evaluate iSeg using both simulated and experimental datasets and show that it performs satisfactorily when compared with some other popular methods, which often employ more sophisticated statistical models. Implemented in C++, iSeg is also very computationally efficient, well suited for large numbers of input profiles and data with very long sequences. CONCLUSIONS:We have developed an efficient general-purpose segmentation tool and showed that it had comparable or more accurate results than many of the most popular segment-calling algorithms used in contemporary genomic data analysis. iSeg is capable of analyzing datasets that have both positive and negative values. Tunable parameters allow users to readily adjust the statistical stringency to best match the biological nature of individual datasets, including widely or sparsely mapped genomic datasets or those with non-normal distributions.

journal_name

BMC Bioinformatics

journal_title

BMC bioinformatics

authors

Girimurugan SB,Liu Y,Lung PY,Vera DL,Dennis JH,Bass HW,Zhang J

doi

10.1186/s12859-018-2140-3

subject

Has Abstract

pub_date

2018-04-11 00:00:00

pages

131

issue

issn

1471-2105

pii

10.1186/s12859-018-2140-3

journal_volume

pub_type

杂志文章

在线工具

iSeg: an efficient algorithm for segmentation of genomic and epigenomic data.