{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# [2]() Fundamentals [edit]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Table of Contents**\n", "0. [Pairwise sequence alignment](1)\n", " 0. [What is a sequence alignment?](1#1)\n", " 0. [A simple procedure for aligning a pair of sequences](1#2)\n", " 0. [Step 1: Create a blank matrix where the rows and columns represent the positions in the sequences.](1#2.1)\n", " 0. [Step 2: Add values to the cells in the matrix.](1#2.2)\n", " 0. [Step 3: Identify the longest diagonals.](1#2.3)\n", " 0. [Step 4: Transcribe some of the possible alignments that arise from this process.](1#2.4)\n", " 0. [Why this simple procedure is too simplistic](1#2.5)\n", " 0. [Differential scoring of matches and mismatches](1#3)\n", " 0. [A better approach for global pairwise alignment using the Needleman-Wunsch algorithm](1#4)\n", " 0. [Stepwise Needleman-Wunsch alignment](1#4.1)\n", " 0. [Step 1: Create blank matrices.](1#4.1.1)\n", " 0. [Step 2: Compute $F$ and $T$.](1#4.1.2)\n", " 0. [Step 3: Transcribe the alignment.](1#4.1.3)\n", " 0. [Automating Needleman-Wunsch alignment with Python](1#4.2)\n", " 0. [A note on computing $F$ and $T$](1#4.3)\n", " 0. [Global versus local alignment](1#5)\n", " 0. [Smith-Waterman local sequence alignment](1#6)\n", " 0. [Step 1: Create blank matrices.](1#6.1)\n", " 0. [Step 2: Compute $F$ and $T$.](1#6.2)\n", " 0. [Step 3: Transcribe the alignment.](1#6.3)\n", " 0. [Automating Smith-Waterman alignment with Python](1#6.4)\n", " 0. [Differential scoring of gaps](1#7)\n", " 0. [How long does pairwise sequence alignment take?](1#8)\n", " 0. [Comparing implementations of Smith-Waterman](1#8.1)\n", " 0. [Analyzing Smith-Waterman run time as a function of sequence length](1#8.2)\n", " 0. [Conclusions on the scalability of pairwise sequence alignment with Smith-Waterman](1#8.3)\n", "0. [Sequence homology searching](2)\n", " 0. [Defining the problem](2#1)\n", " 0. [Loading annotated sequences](2#2)\n", " 0. [Defining the problem](2#3)\n", " 0. [A complete homology search function](2#4)\n", " 0. [Reducing the runtime for database searches](2#5)\n", " 0. [Heuristic algorithms](2#6)\n", " 0. [Random reference sequence selection](2#6.1)\n", " 0. [Composition-based reference sequence collection](2#6.2)\n", " 0. [GC content](2#6.2.1)\n", " 0. [kmer content](2#6.2.2)\n", " 0. [Further optimizing composition-based approaches by pre-computing reference database information](2#6.2.3)\n", " 0. [Determining the statistical significance of a pairwise alignment](2#7)\n", " 0. [Metrics of alignment quality](2#7.1)\n", " 0. [False positives, false negatives, p-values, and alpha](2#7.2)\n", " 0. [Interpreting alignment scores in context](2#7.3)\n", " 0. [Exploring the limit of detection of sequence homology searches](2#7.4)\n", "0. [Generalized dynamic programming for multiple sequence alignment](3)\n", " 0. [Progressive alignment](3#1)\n", " 0. [Building the guide tree](3#1.1)\n", " 0. [Generalization of Needleman-Wunsch (with affine gap scoring) for progressive multiple sequence alignment](3#1.2)\n", " 0. [Putting it all together: progressive multiple sequence alignment](3#1.3)\n", " 0. [Progressive alignment versus iterative alignment](3#2)\n", "0. [Phylogenetic reconstruction](4)\n", " 0. [Why build phylogenies?](4#1)\n", " 0. [How phylogenies are reconstructed](4#2)\n", " 0. [Some terminology](4#3)\n", " 0. [Simulating evolution](4#4)\n", " 0. [A cautionary word about simulations](4#4.1)\n", " 0. [Visualizing trees with ete3](4#5)\n", " 0. [Distance-based approaches to phylogenetic reconstruction](4#6)\n", " 0. [Distances and distance matrices](4#6.1)\n", " 0. [Alignment-free distances between sequences](4#6.2)\n", " 0. [Alignment-based distances between sequences](4#6.3)\n", " 0. [Jukes-Cantor correction of observed distances between sequences](4#6.4)\n", " 0. [Phylogenetic reconstruction with UPGMA](4#6.5)\n", " 0. [Applying UPGMA from SciPy](4#6.5.1)\n", " 0. [Understanding the name](4#6.5.2)\n", " 0. [Phylogenetic reconstruction with neighbor-joining](4#6.6)\n", " 0. [Limitations of distance-based approaches](4#6.7)\n", " 0. [Bootstrap analysis](4#7)\n", " 0. [Parsimony-based approaches to phylogenetic reconstruction](4#8)\n", " 0. [How many possible phylogenies are there for a given collection of sequences?](4#8.1)\n", " 0. [Statistical approaches to phylogenetic reconstruction](4#9)\n", " 0. [Bayesian methods](4#9.1)\n", " 0. [Maximum likelihood methods](4#9.2)\n", " 0. [Rooted versus unrooted trees](4#10)\n", " 0. [Acknowledgements](4#11)\n", "0. [Sequence mapping and clustering](5)\n", " 0. [De novo clustering of sequences by similarity](5#1)\n", " 0. [Furthest neighbor clustering](5#1.1)\n", " 0. [Nearest neighbor clustering](5#1.2)\n", " 0. [Centroid clustering](5#1.3)\n", " 0. [Three different definitions of OTUs](5#1.4)\n", " 0. [Comparing properties of our clustering algorithms](5#2)\n", " 0. [Reference-based clustering to assist with parallelization](5#3)" ] } ], "metadata": {}, "nbformat": 4, "nbformat_minor": 2 }