SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud

Alexander J. Paul; Dylan Lawrence; Myoungkyu Song; Seung Hwan Lim; Chongle Pan; Tae Hyuk Ahn

doi:10.1109/BIBM.2018.8621546

SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud

Alexander J. Paul, Dylan Lawrence, Myoungkyu Song, Seung Hwan Lim, Chongle Pan, Tae Hyuk Ahn

Discrete Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

The advent of high-throughput DNA sequencing techniques has permitted very high quality de novo assemblies of genomes, but raise an issue of requiring large amounts of computer memory to resolve the large genome graphs generated by most overlap graph de novo assemblers. To address these limitations, we present a novel algorithmic approach; Scalable Overlap-graph Reduction Algorithms (SORA). SORA adapts string graph reduction algorithms for the genome assembly using a distributed computing platform. To efficiently compute coverage for enormous paths in the graphs, SORA uses Apache Spark which is a cluster-based engine designed on top of Hadoop to handle very large datasets in the cloud. The experimental results show that SORA can process a nearly one billion edge graph in a distributed cloud cluster as well as smaller graphs on a local cluster with a short turnaround time. Moreover, our algorithms scale almost linearly with increasing numbers of virtual instances in the cloud. SORA is freely available for download at https://github.com/BioHPC/SORA/.

Original language	English
Title of host publication	Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018
Editors	Harald Schmidt, David Griol, Haiying Wang, Jan Baumbach, Huiru Zheng, Zoraida Callejas, Xiaohua Hu, Julie Dickerson, Le Zhang
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	718-723
Number of pages	6
ISBN (Electronic)	9781538654880
DOIs	https://doi.org/10.1109/BIBM.2018.8621546
State	Published - Jan 21 2019
Event	2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018 - Madrid, Spain Duration: Dec 3 2018 → Dec 6 2018

Publication series

Name	Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018

Conference

Conference	2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018
Country/Territory	Spain
City	Madrid
Period	12/3/18 → 12/6/18

Funding

TA is supported by NSF-1566292, NSF-1564894, Saint Louis University President’s Research Fund 2018, and Amazon Web Service (AWS) Cloud Credits for Research. DL is supported by T32 HG000045 from the National Human Genome Research Institute.

Keywords

apache spark
cloud
genome assembly
graph reduction
overlap-layout-consensus

Access to Document

10.1109/BIBM.2018.8621546

Cite this

Paul, A. J., Lawrence, D., Song, M., Lim, S. H., Pan, C., & Ahn, T. H. (2019). SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud. In H. Schmidt, D. Griol, H. Wang, J. Baumbach, H. Zheng, Z. Callejas, X. Hu, J. Dickerson, & L. Zhang (Eds.), Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018 (pp. 718-723). Article 8621546 (Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BIBM.2018.8621546

Paul, Alexander J. ; Lawrence, Dylan ; Song, Myoungkyu et al. / SORA : Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud. Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018. editor / Harald Schmidt ; David Griol ; Haiying Wang ; Jan Baumbach ; Huiru Zheng ; Zoraida Callejas ; Xiaohua Hu ; Julie Dickerson ; Le Zhang. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 718-723 (Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018).

@inproceedings{69f1ffb82e4b4a20ba87e1c403aabe50,

title = "SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud",

abstract = "The advent of high-throughput DNA sequencing techniques has permitted very high quality de novo assemblies of genomes, but raise an issue of requiring large amounts of computer memory to resolve the large genome graphs generated by most overlap graph de novo assemblers. To address these limitations, we present a novel algorithmic approach; Scalable Overlap-graph Reduction Algorithms (SORA). SORA adapts string graph reduction algorithms for the genome assembly using a distributed computing platform. To efficiently compute coverage for enormous paths in the graphs, SORA uses Apache Spark which is a cluster-based engine designed on top of Hadoop to handle very large datasets in the cloud. The experimental results show that SORA can process a nearly one billion edge graph in a distributed cloud cluster as well as smaller graphs on a local cluster with a short turnaround time. Moreover, our algorithms scale almost linearly with increasing numbers of virtual instances in the cloud. SORA is freely available for download at https://github.com/BioHPC/SORA/.",

keywords = "apache spark, cloud, genome assembly, graph reduction, overlap-layout-consensus",

author = "Paul, \{Alexander J.\} and Dylan Lawrence and Myoungkyu Song and Lim, \{Seung Hwan\} and Chongle Pan and Ahn, \{Tae Hyuk\}",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018 ; Conference date: 03-12-2018 Through 06-12-2018",

year = "2019",

month = jan,

day = "21",

doi = "10.1109/BIBM.2018.8621546",

language = "English",

series = "Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "718--723",

editor = "Harald Schmidt and David Griol and Haiying Wang and Jan Baumbach and Huiru Zheng and Zoraida Callejas and Xiaohua Hu and Julie Dickerson and Le Zhang",

booktitle = "Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018",

}

Paul, AJ, Lawrence, D, Song, M, Lim, SH, Pan, C & Ahn, TH 2019, SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud. in H Schmidt, D Griol, H Wang, J Baumbach, H Zheng, Z Callejas, X Hu, J Dickerson & L Zhang (eds), Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018., 8621546, Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018, Institute of Electrical and Electronics Engineers Inc., pp. 718-723, 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018, Madrid, Spain, 12/3/18. https://doi.org/10.1109/BIBM.2018.8621546

SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud. / Paul, Alexander J.; Lawrence, Dylan; Song, Myoungkyu et al.
Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018. ed. / Harald Schmidt; David Griol; Haiying Wang; Jan Baumbach; Huiru Zheng; Zoraida Callejas; Xiaohua Hu; Julie Dickerson; Le Zhang. Institute of Electrical and Electronics Engineers Inc., 2019. p. 718-723 8621546 (Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - SORA

T2 - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018

AU - Paul, Alexander J.

AU - Lawrence, Dylan

AU - Song, Myoungkyu

AU - Lim, Seung Hwan

AU - Pan, Chongle

AU - Ahn, Tae Hyuk

PY - 2019/1/21

Y1 - 2019/1/21

N2 - The advent of high-throughput DNA sequencing techniques has permitted very high quality de novo assemblies of genomes, but raise an issue of requiring large amounts of computer memory to resolve the large genome graphs generated by most overlap graph de novo assemblers. To address these limitations, we present a novel algorithmic approach; Scalable Overlap-graph Reduction Algorithms (SORA). SORA adapts string graph reduction algorithms for the genome assembly using a distributed computing platform. To efficiently compute coverage for enormous paths in the graphs, SORA uses Apache Spark which is a cluster-based engine designed on top of Hadoop to handle very large datasets in the cloud. The experimental results show that SORA can process a nearly one billion edge graph in a distributed cloud cluster as well as smaller graphs on a local cluster with a short turnaround time. Moreover, our algorithms scale almost linearly with increasing numbers of virtual instances in the cloud. SORA is freely available for download at https://github.com/BioHPC/SORA/.

AB - The advent of high-throughput DNA sequencing techniques has permitted very high quality de novo assemblies of genomes, but raise an issue of requiring large amounts of computer memory to resolve the large genome graphs generated by most overlap graph de novo assemblers. To address these limitations, we present a novel algorithmic approach; Scalable Overlap-graph Reduction Algorithms (SORA). SORA adapts string graph reduction algorithms for the genome assembly using a distributed computing platform. To efficiently compute coverage for enormous paths in the graphs, SORA uses Apache Spark which is a cluster-based engine designed on top of Hadoop to handle very large datasets in the cloud. The experimental results show that SORA can process a nearly one billion edge graph in a distributed cloud cluster as well as smaller graphs on a local cluster with a short turnaround time. Moreover, our algorithms scale almost linearly with increasing numbers of virtual instances in the cloud. SORA is freely available for download at https://github.com/BioHPC/SORA/.

KW - apache spark

KW - cloud

KW - genome assembly

KW - graph reduction

KW - overlap-layout-consensus

UR - https://www.scopus.com/pages/publications/85062482918

U2 - 10.1109/BIBM.2018.8621546

DO - 10.1109/BIBM.2018.8621546

M3 - Conference contribution

AN - SCOPUS:85062482918

T3 - Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018

SP - 718

EP - 723

BT - Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018

A2 - Schmidt, Harald

A2 - Griol, David

A2 - Wang, Haiying

A2 - Baumbach, Jan

A2 - Zheng, Huiru

A2 - Callejas, Zoraida

A2 - Hu, Xiaohua

A2 - Dickerson, Julie

A2 - Zhang, Le

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 3 December 2018 through 6 December 2018

ER -

Paul AJ, Lawrence D, Song M, Lim SH, Pan C, Ahn TH. SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud. In Schmidt H, Griol D, Wang H, Baumbach J, Zheng H, Callejas Z, Hu X, Dickerson J, Zhang L, editors, Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018. Institute of Electrical and Electronics Engineers Inc. 2019. p. 718-723. 8621546. (Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018). doi: 10.1109/BIBM.2018.8621546

SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this