Multiple sequence alignment using partial order graphs

By Christopher J. Lee, Catherine S. Grasso, Mark F. Sharlow. 2002

847 citations recorded by the source corpus.

Subfields: Molecular Biology, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Natural Language Processing

Citations in the corpus

Unsupervised Learning from Narrated Instruction Videos (2015, methodology): “The standard solution from computational biology is to apply a heuristic algorithm that proceeds by incremental pairwise alignment using dynamic programming [18].”
The accuracy of several multiple sequence alignment programs for proteins (2006, methodology): “) [20] version 2.0 POA is another MSA package that uses a progressive alignment algorithm without using generalized profiles.”
Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data (2013, methodology): “Quiver then uses a fast heuristic algorithm (partial order alignment 37 ) to generate an initial, approximate consensus.”
The simple-septate basidiomycetes: a synopsis (2006, methodology): “For both data sets, we followed a multiple-analysis strategy (Lee 2001) and aligned the sequences with four different alignment methods and programs, namely, DIALIGN 2.2.1, using the −n option (Morgenstern 1999); MAFFT, using the FFT-NS-i option (Katoh et al. 2002); MUSCLE 3.2 (Edgar 2004); and POA ”
From squiggle to basepair: computational approaches for improving nanopore sequencing read accuracy (2018, neutral): “[62]”
A complete bacterial genome assembled de novo using only nanopore sequencing data (2015, methodology): “…position in the large contig corresponding to the E. coli origin of replication was determined through a BLAST homology search for the ﬁrst 1000 bases of the reference genome, and the contig was circularised using the minimus2 package in AMOS [12] by the introduction of an artiﬁcial contig break.”
Oxford Nanopore MinION Sequencing and Genome Assembly (2016, methodology): “Multiple alignments are computed using the partial-order alignment (POA) software [38], where data inputs are single reads and their overlaps.”
Fast Statistical Alignment (2009, methodology): “Furthermore, [13,14] introduced the sequence annealing approach to building multiple alignments, via the description of alignments using partially ordered sets [31,55,56].”
Multiple Sequence Alignment Based on Profile Alignment of Intermediate Sequences (2007, methodology): “…algorithms have been proposed for multiple sequence alignment (Thompson et al. 1994; Morgenstern et al. 1996; Stoye 1998; Notredame et al. 2000; Lee et al. 2002; Edgar 2004; Van Walle et al. 2004; Do et al. 2005; Katoh et al. 2005; Lassmann and Sonnhammer 2005; Pei and Grishin 2006; Roshan and…”
25 years of serving the community with ribosomal RNA gene reference databases and tools. (2017, methodology): “The reference sequences from the SEED are transferred into a partial order graph as used in (Lee et al., 2002), while preserving the positional identity from the reference alignment.”
Genome graphs and the evolution of genome inference (2017, background): “Although extending fully ordered dynamic programming algorithms to partially ordered directed acyclic graphs is relatively simple (Lee et al. 2002), sequence graphs are not restricted to directed acyclic structures.”
Assembly of long error-prone reads using de Bruijn graphs (2016, methodology): “The motivation for constructing mini-alignments is to enable accurate error-correction methods (such as a partial order alignment [32]) that are fast when applied to short segments of reads but become too slow in the case of long segments.”