Method for large scale scaffolding of genome assemblies

A method for large scale scaffolding of a genome assembly from a set of reads comprising:

• generating a chromosome interaction dataset from the set of reads from a genome of interest lacking a reference genome, wherein the chromosome interaction dataset includes intrachromosomal and interchromosomal contact information for the reads that provides long-range information for scaffolding the genome assembly, and wherein chromosome interaction dataset is generated by a chromosome conformation analysis technique selected from Chromatin Conformation Capture (3C), Circularized Chromatin Conformation Capture (4C), Carbon Copy Chromosome Conformation Capture (5C), Chromatin Immunoprecipitation (ChIP), ChIP-Loop, Hi-C, combined 3C-ChIP-cloning (6C), or Capture-C;
• aligning the set of reads with a draft assembly sequence, a shotgun assembly sequence, or a reference assembly sequence, wherein the alignment results in a test set of contigs;
• generating a de novo genome assembly to establish long range or chromosome-scale contiguity of the genome of interest from the draft assembly sequence, the shotgun assembly sequence, or the reference assembly sequence by subjecting the chromosome interaction dataset and the test set of contigs to a scaffolding method performed by a computing system, the scaffolding method comprising:
• clustering the test set of contigs to form two or more location cluster groups by performing a hierarchical agglomerative clustering algorithm on a clustering graph to generate an agglomerated clustering graph, each location cluster group comprising one or more location-clustered contigs;
• ordering the one or more location-clustered contigs within each of the two or more location cluster groups to form an ordered set of one or more location-clustered contigs within each cluster group by determining a minimum spanning tree of the agglomerated clustering graph and finding the longest path in the minimum spanning tree for each location cluster group;
• orienting each ordered set of one or more location-clustered contigs to assign a relative orientation to each of the location-clustered contigs within each location cluster group by performing an orienting algorithm on a weighted directed acyclic graph (WDAG).