Back to search

Central Florida

Efficient String Graph Construction Algorithm

Abstract

dc:description.abstract

In the field of genome assembly research where assemblers are dominated by de Bruijn graph-based approaches, string graph-based assembly approach is getting more attention because of its ability to losslessly retain information from sequence data. Despite the advantages provided by a string graph in repeat detection and in maintaining read coherence, the high computational cost for constructing a string graph hinders its usability for genome assembly. Even though different algorithms have been proposed over the last decade for string graph construction, efficiency is still a challenge due to the demand for processing a large amount of sequence data generated by NGS technologies. Therefore, in this thesis, we provide a novel, linear time and alphabet-size-independent algorithm SOF which uses the property of irreducible edges and transitive edges to efficiently construct string graph from an overlap graph. Experimental results show that SOF is at least 2 times faster than the string graph construction algorithm provided in SGA, one of the most popular string graph-based assembler, while maintaining almost the same memory footprint as SGA. Moreover, the availability of SOF as a subprogram in the SGA assembly pipeline will give user facilities to access the preprocessing and postprocessing steps for genome assembly provided in SGA.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Morshed, S.M. Iqbal
Contributors dc:contributor
  • Yooseph, Shibu

Subjects

dc:subject × 1

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
CFE0007504

Chain of custody

source
Harvested from
Central Florida
Base URL
stars.library.ucf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Morshed, S.M. Iqbal. Efficient String Graph Construction Algorithm. https://stars.library.ucf.edu/etd/6303