🧬Computational Genomics Unit 2 – Sequence Alignment & Assembly

Key Concepts

• Sequence alignment involves arranging DNA, RNA, or protein sequences to identify regions of similarity that may indicate functional, structural, or evolutionary relationships between the sequences
• Pairwise alignment compares two sequences at a time while multiple sequence alignment compares more than two sequences simultaneously
• Dynamic programming algorithms (Needleman-Wunsch and Smith-Waterman) guarantee optimal pairwise alignments but have high computational complexity
• Heuristic algorithms (BLAST and FASTA) trade some accuracy for improved speed and scalability
• Genome assembly reconstructs the original DNA sequence from numerous smaller sequenced fragments called reads
• De novo assembly builds contigs and scaffolds without using a reference genome while reference-guided assembly aligns reads to a known reference sequence
• Sequence alignment and genome assembly play crucial roles in various applications such as phylogenetic analysis, variant detection, and comparative genomics

Biological Background

• DNA consists of four nucleotide bases: adenine (A), thymine (T), guanine (G), and cytosine (C)
  • Complementary base pairing occurs between A-T and G-C
• RNA contains uracil (U) instead of thymine and plays vital roles in gene expression and regulation
• Proteins are composed of amino acids and perform a wide range of functions in living organisms
  • The genetic code determines the relationship between nucleotide triplets (codons) and amino acids
• Mutations can alter DNA sequences through substitutions, insertions, or deletions
  • Point mutations affect single nucleotides while structural variations involve larger segments of DNA
• Evolutionary processes such as selection, drift, and recombination shape the diversity of DNA sequences across species
• Conserved regions in DNA or protein sequences often indicate functional or structural importance

Sequence Alignment Basics

• Sequence alignment arranges sequences to maximize the number of matching characters and minimize the number of gaps (insertions or deletions)
• Matches, mismatches, and gaps are assigned scores based on their likelihood of occurrence
  • Scoring matrices (PAM and BLOSUM) provide empirically derived substitution scores for amino acids
• Global alignment aligns entire sequences from end to end (Needleman-Wunsch algorithm)
• Local alignment identifies the most similar regions between sequences without requiring end-to-end alignment (Smith-Waterman algorithm)
• Gaps are introduced to account for insertions or deletions and are typically penalized in alignment scoring
• Alignment quality is assessed using metrics such as percent identity, similarity, and gap content
• Sequence alignment enables the identification of homologous sequences, which share a common evolutionary origin

Pairwise Alignment Algorithms

• Dynamic programming algorithms guarantee optimal pairwise alignments by systematically exploring all possible alignments
  • Needleman-Wunsch algorithm performs global alignment and uses a scoring matrix and gap penalties to fill a dynamic programming matrix
  • Smith-Waterman algorithm performs local alignment and allows for the identification of the most similar subsequences
• Heuristic algorithms provide faster alternatives to dynamic programming by sacrificing some accuracy
  • BLAST (Basic Local Alignment Search Tool) uses a seed-and-extend approach to identify high-scoring segment pairs (HSPs) between a query sequence and a database
  • FASTA (FAST-All) employs a k-tuple method to find initial matches and then extends them using a dynamic programming algorithm
• Alignment parameters such as substitution matrices, gap penalties, and significance thresholds can be adjusted to optimize alignment results
• Pairwise alignment serves as a foundation for multiple sequence alignment and homology searching

Multiple Sequence Alignment

• Multiple sequence alignment (MSA) simultaneously aligns three or more sequences to identify conserved regions and evolutionary relationships
• Progressive alignment algorithms (ClustalW and MUSCLE) build an MSA by progressively aligning the most similar sequences based on a guide tree
  • Guide trees are constructed using pairwise alignment scores or phylogenetic methods
• Iterative refinement algorithms (MAFFT and T-Coffee) improve the initial MSA by repeatedly dividing and realigning subsets of sequences
• Consistency-based methods (ProbCons and CONTRAlign) incorporate pairwise alignment information from all sequences to guide the MSA construction
• MSA quality assessment tools (GUIDANCE and TCS) evaluate the reliability of alignments and identify potentially misaligned regions
• Multiple sequence alignment is essential for phylogenetic analysis, protein structure prediction, and functional annotation

Genome Assembly Techniques

• Genome assembly reconstructs the original DNA sequence from numerous smaller sequenced fragments called reads
• Sanger sequencing produces longer reads (800-1000 bp) with higher accuracy but lower throughput compared to next-generation sequencing (NGS) technologies
  • NGS platforms (Illumina, 454, and SOLiD) generate millions of shorter reads (50-400 bp) with varying error rates and throughput
• Overlap-layout-consensus (OLC) assembly algorithms (Celera Assembler and Arachne) identify overlaps between reads, construct a graph representation, and generate a consensus sequence
• De Bruijn graph assemblers (Velvet and SPAdes) break reads into k-mers, build a graph based on k-mer overlaps, and traverse the graph to assemble contigs
• Hybrid assembly approaches (MaSuRCA and Allpaths-LG) combine the strengths of different sequencing technologies and assembly algorithms
• Scaffolding techniques (SSPACE and BESST) order and orient contigs using paired-end reads or long-range information (optical mapping and Hi-C)
• Assembly quality metrics include N50, number of contigs, and completeness of conserved gene sets (BUSCO)

Tools and Software

• Sequence alignment tools:
  • BLAST: widely used for local alignment and homology searching against sequence databases
  • MUSCLE: fast and accurate multiple sequence alignment program
  • T-Coffee: consistency-based MSA tool that combines information from pairwise alignments
  • MAFFT: rapid MSA algorithm with options for large-scale alignments and iterative refinement
• Genome assembly software:
  • SPAdes: de Bruijn graph assembler for both single-cell and multi-cell sequencing data
  • Canu: long-read assembler for PacBio and Oxford Nanopore sequencing data
  • Allpaths-LG: hybrid assembler that uses both short and long reads to generate high-quality assemblies
  • QUAST: quality assessment tool for evaluating genome assemblies
• Visualization and analysis platforms:
  • Integrative Genomics Viewer (IGV): interactive visualization tool for exploring sequence alignments and genome annotations
  • Galaxy: web-based platform for accessible, reproducible, and transparent genomic analyses
  • Bioconductor: open-source software project in R for analyzing high-throughput genomic data

Applications and Case Studies

• Comparative genomics: sequence alignment enables the identification of conserved regions, regulatory elements, and evolutionary relationships between species
  • Example: comparing the genomes of humans and chimpanzees to study the genetic basis of human-specific traits
• Variant detection: aligning sequencing reads to a reference genome allows for the identification of single nucleotide polymorphisms (SNPs), insertions, and deletions
  • Example: whole-exome sequencing to identify disease-causing mutations in patients with rare genetic disorders
• Metagenomics: assembling and analyzing DNA sequences from environmental samples to study microbial communities and their functions
  • Example: investigating the role of the human gut microbiome in health and disease
• Evolutionary studies: multiple sequence alignment and phylogenetic analysis help reconstruct the evolutionary history of genes, proteins, and species
  • Example: tracing the origin and spread of SARS-CoV-2 using genome sequences from different viral isolates
• Personalized medicine: identifying genetic variations associated with disease risk, drug response, and treatment outcomes
  • Example: using genome sequencing to guide targeted cancer therapy based on a patient's tumor profile