An efficient overlap graph coarsening approach for modeling short reads

Julia Warnke, Hesham H. Ali

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Next generation sequencing has quickly emerged as the most exciting yet challenging computational problem in Bioinformatics. Current sequencing technologies are capable of producing several hundreds of thousands to several millions of short sequence reads in a single run. However, current methods for managing, storing, and processing the produced reads remain for the most part simple and lack the complexity needed to model the produced reads efficiently and assemble them correctly. These reads are produced at a high coverage of the original target sequence such that many reads overlap. The overlap relationships are used to align and merge reads into contiguous sequences called contigs. In this paper, we present an overlap graph coarsening scheme for modeling reads and their overlap relationships. Our approach is different from previous read analysis and assembly methods that use a single graph to model read overlap relationships. Instead, we use a series of graphs with different granularities of information to represent the complex read overlap relationships. We present a new graph coarsening algorithm for clustering a simulated metagenomics dataset at various levels of granularity. We also use the proposed graph coarsening scheme along with graph traversal algorithms to find a labeling of the overlap graph that allows for the efficient organization of nodes within the graph data structure.

Original languageEnglish (US)
Title of host publicationProceedings - 2012 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2012
Pages704-711
Number of pages8
DOIs
StatePublished - 2012
Event2012 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2012 - Philadelphia, PA, United States
Duration: Oct 4 2012Oct 7 2012

Publication series

NameProceedings - 2012 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2012

Conference

Conference2012 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2012
CountryUnited States
CityPhiladelphia, PA
Period10/4/1210/7/12

Keywords

  • Clustering
  • Graph theory
  • Next generation sequencing
  • metagenomics

ASJC Scopus subject areas

  • Biomedical Engineering
  • Health Informatics

Fingerprint Dive into the research topics of 'An efficient overlap graph coarsening approach for modeling short reads'. Together they form a unique fingerprint.

Cite this