Scalable methods for improving genome assemblies
department or school: Science, Faculty of
data provider: DSpace
degree campus: UBCV
creator: Nikolić, Vladimir
issued: 2021-04-22T18:56:23Z
issued: 2021
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: De novo genome assembly is cornerstone to modern genomics studies. It is also a useful method for studying genomes with high variation, such as cancer genomes, as it is not biased by a reference. De novo short-read assemblers commonly use de Bruijn graphs, where nodes are sequences of equal length k, also known as k-mers. Edges in this graph are established between nodes that overlap by k - 1 bases, followed by merging nodes along unambiguous walks in the graph. The selection of k is influenced by a few factors, and its fine tuning results in a trade-off between graph connectivity and sequence contiguity. Ideally, multiple k sizes should be used, so lower values can provide good connectivity in lesser covered regions and higher values can increase contiguity in well-covered regions. However, this approach has only been explored with small genomes, without addressing scalability issues with larger ones. Here we present RResolver, a scalable algorithm that takes a short-read de Bruijn graph assembly with a starting k as input and uses a k value closer to that of the read length to resolve repeats. RResolver builds a Bloom filter of sequencing reads which it uses to evaluate the assembly graph path support at branching points and removes the paths with insufficient support. RResolver runs efficiently, taking 3% of a typical ABySS human assembly pipeline run time on average with 48 threads and 40GB memory. Compared to a baseline assembly, RResolver improves scaffold contiguity (NGA50) by up to 16% and reduces misassemblies by up to 7%. RResolver adds a missing component to scalable de Bruijn graph genome assembly. By improving the initial and fundamental graph traversal outcome, all downstream ABySS algorithms greatly benefit by working with a more accurate and less complex representation of the genome.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/77903
note: Scalable methods for improving genome assembliesbyVladimir Nikolic´B.Sc., The University of Belgrade, 2018A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Bioinformatics)The University of British Columbia(Vancouver)April 2021© Vladimir Nikolic´, 2021The following individuals certify that they have read, and recommend to the Faculty of Grad-uate and Postdoctoral Studies for acceptance, the thesis entitled:Scalable methods for improving genome assembliessubmitted by Vladimir Nikolic´ in partial fulfillment of the requirements for the degree ofMaster of Science in Bioinformatics.Examining Committee:Dr. Inanc Birol, Medical Genetics, UBCSupervisorDr. Andrew Roth, Computer Science, UBCSupervisory Committee MemberDr. Faraz Hach, Urologic Sciences, UBCSupervisory Committee MemberiiAbstractDe novo genome assembly is cornerstone to modern genomics studies. It is also a usefulmethod for studying genomes with high variation, such as cancer genomes, as it is not biased bya reference. De novo short-read assemblers commonly use de Bruijn graphs, where nodes aresequences of equal length k, also known as k-mers. Edges in this graph are established betweennodes that overlap by k−1 bases, followed by merging nodes along unambiguous walks in thegraph. The selection of k is influenced by a few factors, and its fine tuning results in a trade-offbetween graph connectivity and sequence contiguity. Ideally, multiple k sizes should be used,so lower values can provide good connectivity in lesser covered regions and higher values canincrease contiguity in well-covered regions. However, this approach has only been exploredwith small genomes, without addressing scalability issues with larger ones. Here we presentRResolver, a scalable algorithm that takes a short-read de Bruijn graph assembly with a startingk as input and uses a k value closer to that of the read length to resolve repeats. RResolverb…
has type: Thesis/Dissertation
date issued: 2021-05
is shown at: 10.14288/1.0396934
language: eng
degree discipline: Bioinformatics
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-ShareAlike 4.0 International
rights URI: http://creativecommons.org/licenses/by-sa/4.0/
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/77903