String graph assembly for polyploid genomes

An executable software product stored on a computer-readable medium comprising program instructions for string graph assembly of a polyploid genome, the program instructions, when executed on at least one processor, comprising perform:

• receiving a plurality of sequence reads of at least 0.5 kb in length for a plurality of homologous chromosomes in the polyploid genome, the plurality of sequence reads comprising sequence reads generated by sequencing, and representing the sequence of, each homologous chromosome in the plurality of homologous chromosomes;
• aligning each respective sequence read in the plurality of sequence reads to each other thereby forming a plurality of aligned sequence reads;
• generating a string graph, that represents the plurality of homologous chromosomes, from the plurality of aligned sequence reads, wherein
• the string graph comprises a plurality of nodes and a plurality of edges, wherein the plurality of nodes and the plurality of edges collectively represent nucleic acid sequences of each homologous chromosome in the plurality of homologous chromosomes of the polyploid genome, wherein each respective chromosome in the plurality of homologous chromosomes differs in sequence from a different corresponding homologous chromosome in the plurality of homologous chromosomes,
• each node in the plurality of nodes is a beginning or an end of a sequence read in the plurality of aligned sequence reads, and
• each edge in the plurality of edges is a sequence represented in the plurality of aligned sequence reads between two vertices in the plurality of vertices;
• identifying non-branching unitigs in the string graph and generating a unitig graph by determining each path in the string graph without any branches;
• identifying string bundles in the unitig graph by traversing the unitig graph and determining a respective primary contig from each of the string bundles, wherein a primary contig is a single path without branching that extends the length of the string bundle;
• determining, for each of the string bundles, associated contigs that are associated with the respective primary contig and that differ in sequence compared to the primary contig;
• and
• using the respective primary contig and the associated contigs associated with the respective primary contig to determine a consensus sequence that represents each homologous chromosome in the plurality of homologous chromosomes, wherein the consensus sequence distinguishes, for a respective junction in the unitig graph, whether the respective junction is (i) caused by a presence of homologous regions having structural variations or (ii) caused by the presence of an insertion error, deletion error, or mismatch error within a respective sequence read in the plurality of sequence reads.

A computer system for string graph assembly of a polyploid genome, comprising:

• a memory;
• and
• a processor coupled to the memory and configured to:
• receive a plurality of sequence reads of at least 0.5 kb in length for a plurality of homologous chromosomes in the polyploid genome, the plurality of sequence reads comprising sequence reads generated by sequencing, and representing the sequence of, each homologous chromosome in the plurality of homologous chromosomes;
• align each respective sequence read in the plurality of sequence reads to each other thereby forming a plurality of aligned sequence reads;
• generate a string graph, that represents the plurality of homologous chromosomes, from the plurality of aligned sequence reads, wherein
• the string graph comprises a plurality of nodes and a plurality of edges, wherein the plurality of nodes and the plurality of edges collectively represent nucleic acid sequences of each homologous chromosomes in the plurality of homologous chromosomes of the polyploid genome, wherein each respective chromosome in the plurality of homologous chromosomes differs in sequence from a different corresponding homologous chromosome in the plurality of homologous chromosomes,
• each node in the plurality of nodes is a beginning or an end of a sequence read in the plurality of aligned sequence reads, and
• each edge in the plurality of edges is a sequence represented in the plurality of aligned sequence reads between two vertices in the plurality of vertices;
• identify non-branching unitigs in the string graph and generate a unitig graph by determining each path in the string graph without any branches;
• identify string bundles in the unitig graph by traversing the unitig graph determining a respective primary contig from each of the string bundles, wherein a primary contig is a single path without branching that extends the length of the string bundle;
• determining, for each of the string bundles, associated contigs that are associated with the respective primary contig and that differ in sequence compared to the primary contig;
• and
• using the respective primary contig and the associated contigs associated with the respective primary contig to determine a consensus sequence that represents each homologous chromosome in the plurality of homologous chromosomes, wherein the consensus sequence distinguishes, for a respective junction in the unitig graph, whether the respective junction is (i) caused by a presence of homologous regions having structural variations or (ii) caused by the presence of an insertion error, deletion error, or mismatch error within a respective sequence read in the plurality of sequence reads.