Sequence Assembly Algorithms Overview

True (A)

String graph

<p>Burrows-Wheeler</p> Signup and view all the answers

<p>Genome Assembly = Assembling sequences against a reference RNA splicing studies = Analyzing RNA processing and maturation SNP discovery = Identifying genetic variations Transcription factor binding site discovery = Locating regulatory regions in DNA</p> Signup and view all the answers

<p>It cannot effectively use global information like mate pairs. (B)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Smith Waterman algorithm</p> Signup and view all the answers

<p>2n^2 - 2n</p> Signup and view all the answers

<p>Greedy Approach = Local assembly method Overlap Graph = Allows mismatches for sequencing errors De Brujin = Uses k-mers for assembly String Graph = Series of overlapping sequences</p> Signup and view all the answers

<p>Overlap Graph (OLC) (A)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>Search space</p> Signup and view all the answers

<p>Hamiltonian cycle (A)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>They allow for the efficient assembly of the genome by reducing redundancy and ensuring that k-mers are used effectively.</p> Signup and view all the answers

<p>NP</p> Signup and view all the answers

<p>SOAPdenovo = An assembler utilizing Hamiltonian graphs SGA = An efficient genome assembler ABySS = Assembler designed for large genomes De Bruijn graph = A graph structure used to assemble genomes by k-mers</p> Signup and view all the answers

<p>All k-mers present in the genome should ideally be assembled. (C)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>The computation time required to solve the graph problem increases significantly.</p> Signup and view all the answers

<p>once</p> Signup and view all the answers

<p>Hamiltonian Cycle = Path that visits every node once and returns to the start Eulerian Path = Path that visits every edge exactly once k-mer = Subsequent segments of DNA used in assembly Next-Generation Sequencing = High-throughput sequencing technology</p> Signup and view all the answers

<p>Unitig (A)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>To represent sequences of DNA for analysis.</p> Signup and view all the answers

<p>Contig</p> Signup and view all the answers

<p>Unitig = Initial assembly of sequences Contig = Aligning paired-end reads Scaffold = Joining contigs Bloom Filter = Memory-efficient k-mer storage</p> Signup and view all the answers

<p>A technique that uses sequences to build a graph structure (C)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>The extension of a solid read is halted.</p> Signup and view all the answers

<p>one</p> Signup and view all the answers

<p>Bloom Filter (C)</p> Signup and view all the answers

<p>Traversing edges (B)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Contains all k-mers in the genome.</p> Signup and view all the answers

<p>once</p> Signup and view all the answers

<p>k-mer = Substring of length k from a sequence coverage = The amount of sequencing data available contigs = Continuous sequences produced during assembly branches = Redundant paths in the assembly graph</p> Signup and view all the answers

<p>Multiple contigs being produced (D)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>They can lead to low coverage areas.</p> Signup and view all the answers

<p>100, 200</p> Signup and view all the answers

<p>Using paired-end reads (B)</p> Signup and view all the answers

In sequence assembly, this approach finds the two reads with the greatest overlap and merges them. It repeats this process until no further assembly is possible. It is a simple method but suffers from limitations in dealing with repetitive regions and utilizing global information like paired-end reads.

This method utilizes the concept of k-mers, which are substrings of a fixed length within a sequence. It sorts and indexes these k-mers to identify overlapping reads, significantly reducing the search space.

A graph representation where each node represents a read, and edges represent overlaps between reads. This helps visualize and analyze the relationships between reads during the assembly process.

A commonly used algorithm for sequence assembly, particularly suitable for Sanger sequencing reads (1kb) and long PacBio reads (tens of Kb). It builds a graph based on read overlaps and then uses consensus techniques to determine the final sequence.

These algorithms are used to assemble sequences and can be classified based on the length of the available reads. They include the Greedy approach, Overlap Graph (OLC), De Bruijn, and String Graph methods.

The complexity of finding overlapping reads and assembling them increases disproportionately with an increasing number of reads. For n reads, there are 2n^2 – 2n possible overlaps.

Paired-end reads, or mate pairs, are used to provide additional information for the assembly process. They help resolve repetitive regions and determine the correct order of reads.

This algorithm focuses on identifying and resolving repetitive regions within the sequence. It utilizes a directed graph representation to represent the sequence, where each node represents a unique k-mer and edges indicate overlaps between k-mers.

A k-mer with a specific prefix and su:ix. For example, the k-mer ATG has AT as the prefix and TG as the su:ix.

A path in a graph that visits every edge exactly once.

A graph where the number of edges going into a node equals the number of edges going out.

A graph where every node is visited exactly once.

The process of assembling the genome by finding overlaps between k-mers and joining them together.

An Eulerian graph is more e:icient for genome assembly than a Hamiltonian graph because it ensures that there are no dead ends and only one path to follow.

Regions of the genome where there is not enough sequencing data to determine the correct sequence.

Multiple contiguous sequences that result from low coverage areas in the assembly.

The size of the k-mer used in genome assembly. Longer k-mers provide more information but may not be present in the genome as frequently.

Illumina reads are typically around 100-200 base pairs long, resulting in k-mers of 100+ base pairs or more.

The initial assembly of sequences using the de Bruijn graph approach.

Paired-end reads aligned to the unitigs, and the paired-end information is used to orient and merge overlapping unitigs.

Align mate-pair reads to the contigs to orient and join them into scaffolds. "N" characters are inserted at any gaps in coverage and for unsolved repeats.

A data structure that stores a set of elements, allowing for efficient insertion and querying of elements.

A unit of information that represents a sequence of k consecutive nucleotides in a DNA or RNA sequence.

The process of determining the sequence of nucleotides in a DNA or RNA molecule.

A sequence that can be extended in both directions within the de Bruijn graph without ambiguity.

A point in the de Bruijn graph where a k-mer has more than one possible successor.

A data structure that represents a sequence of characters. It is commonly used to store and manipulate text data in various programming languages.

A string graph is a representation of a sequence of characters where each node represents a unique substring (or read), and edges connect overlapping nodes.

Resequencing is a type of sequence assembly where the goal is to reconstruct an unknown sequence by aligning reads against a known reference sequence. This is simpler than assembling from scratch.

A technique used to efficiently index and search large sequences of genetic data. It is based on the Burrows-Wheeler Transform (BWT) and the Suffix Array.

A data structure that allows efficient searching for specific substrings within a larger sequence. It stores all possible suffixes of the sequence in a sorted fashion.

In traditional Sanger sequencing, reads are depicted as nodes in a graph, and edges represent alignments between these reads. A Hamiltonian cycle is formed by following the edges in numerical order, allowing for the reconstruction of the circular genome by combining alignments between consecutive reads. At the cycle's end, the sequence wraps around to the genome's start.

De Bruijn graphs are used to assemble genomes. Reads are broken down into all possible k-mers, eliminating redundancy. By following the Hamiltonian cycle, each consecutive node (k-mer) is shifted by one nucleotide. This method ensures that every node is touched exactly once, resembling the genome.

A Hamiltonian path is a path in a graph that visits every node exactly once. Finding such a path is an NP problem, meaning there is no known efficient algorithm for all cases to solve it in polynomial time.

The Hamiltonian graph approach is employed by assemblers like SOAPdenovo, SGA, and ABySS. Transversing all nodes once leads to NP-hardness, making it computationally challenging as the number of nodes increases. To overcome this, assembly programs simplify the graphs, reducing branching nodes.

A Hamiltonian path requires finding a path that traverses all nodes in a graph once. This is an NP problem, implying that finding a solution in all cases within polynomial time is currently not possible. Finding such a Hamiltonian path can be complex and computationally expensive.

An Eulerian path is a path in a graph that traverses every edge exactly once. It's a different approach to genome assembly compared to Hamiltonian paths, which focus on nodes.

An Eulerian graph is a graph where an Eulerian path exists. To create an Eulerian graph from k-mers, each k-mer prefix and suffix needs to appear only once in the graph. This creates a unique path through the graph.

In de Bruijn graph assembly, all k-mer prefixes and suffixes are represented as nodes. Each prefix and suffix can only occur once in the graph, guaranteeing a single path through the graph, similar to an Eulerian path.

Genome assembly requires all k-mers present in the genome to be assembled, and each k-mer should appear at most once. These conditions are important for the de Bruijn graph method, allowing for a unique path through the graph.

The size of the k-mer (substring of the genome) is crucial in de Bruijn graph assembly. Larger genomes require larger k-mers for accurate assembly. This is because larger k-mers offer more unique information for each node, making the graph more informative.