QuickProbs 2: Towards rapid construction of high-quality alignments of large protein families (2015-12-23T00:00:00.000000Z)

TL;DR

The presented algorithm has similar execution times to ClustalΩ, and is orders of magnitude faster than full consistency approaches, like MSAProbs or PicXAA, which make QuickProbs 2 an excellent tool for aligning families ranging from few, to hundreds of proteins.

Abstract

The ever-increasing size of sequence databases caused by the development of high throughput sequencing, poses to multiple alignment algorithms one of the greatest challenges yet. As we show, well-established techniques employed for increasing alignment quality, i.e., refinement and consistency, are ineffective when large protein families are investigated. We present QuickProbs 2, an algorithm for multiple sequence alignment. Based on probabilistic models, equipped with novel column-oriented refinement and selective consistency, it offers outstanding accuracy. When analysing hundreds of sequences, Quick-Probs 2 is noticeably better than ClustalΩ and MAFFT, the previous leaders for processing numerous protein families. In the case of smaller sets, for which consistency-based methods are the best performing, QuickProbs 2 is also superior to the competitors. Due to low computational requirements of selective consistency and utilization of massively parallel architectures, presented algorithm has similar execution times to ClustalΩ, and is orders of magnitude faster than full consistency approaches, like MSAProbs or PicXAA. All these make QuickProbs 2 an excellent tool for aligning families ranging from few, to hundreds of proteins.

Authors

Adam Gudyś

1 papers

Sebastian Deorowicz

1 papers

TL;DR

Abstract

Authors

References49 items

Application of the MAFFT sequence alignment program to large data—reexamination of the usefulness of chained guide trees

FAMSA: Fast and accurate multiple sequence alignment of huge protein families

A simple method to control over-alignment in the MAFFT multiple sequence alignment program

Reply to Tan et al.: Differences between real and simulated proteins in multiple sequence alignments

Simple chained guide trees give poorer multiple sequence alignments than inferred trees in simulation and phylogenetic benchmarks

Simple chained guide trees give high-quality protein multiple sequence alignments

QuickProbs—A Fast Multiple Sequence Alignment Algorithm Designed for Graphics Processors

ACKNOWLEDGEMENTS

GLProbs: Aligning multiple sequences adaptively

Making automated multiple alignments of very large numbers of protein sequences

Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega

On the Future of Genomic Data

Sequence embedding for fast construction of guide trees for multiple sequence alignment

PicXAA: greedy probabilistic construction of maximum expected accuracy alignment of multiple sequences

Quality measures for protein alignment benchmarks

Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features

Phylogeny-Aware Gap Placement Prevents Errors in Sequence Alignment and Evolutionary Analysis

The Pfam protein families database

PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences

Probalign: multiple sequence alignment using partition function posterior probabilities

Refining multiple sequence alignments with conserved core regions

Evaluation of iterative alignment algorithms for multiple alignment

ProbCons: Probabilistic consistency-based multiple sequence alignment.

MAFFT version 5: improvement in accuracy of multiple sequence alignment

MUSCLE: multiple sequence alignment with high accuracy and high throughput.

OXBench: A benchmark for evaluation of protein multiple sequence alignment accuracy

Scoring residue conservation

MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform.

T-Coffee: A novel method for fast and accurate multiple sequence alignment.

PipMaker--a web server for aligning two genomic DNA sequences.

HOMSTRAD: A database of protein structure alignments for homologous families

Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids

Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments.

A reliable sequence alignment method based on probabilities of residue correspondences.

Comprehensive study on iterative algorithms of multiple sequence alignment

CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice.

The First Decade of Numerical Taxonomy. (Book Reviews: Numerical Taxonomy. The Principles and Practice of Numerical Classification)

Numerical Taxonomy: The Principles and Practice of Numerical Classification

Numerical Taxonomy: The Principles and Practice of Numerical Classification

Phylogeny-aware alignment with PRANK.

Kalign-LCS - A More Accurate and Faster Variant of Kalign2 Algorithm for the Multiple Sequence Alignment Problem

Algorithm xxx : NOMAD : Nonlinear Optimization with the MADS algorithm

Alignment

BIOINFORMATICS APPLICATIONS NOTE Sequence analysis SABmark—a benchmark for sequence alignment that covers the entire known fold space

Estimating amino acid substitution models: a comparison of Dayhoff's estimator, the resolvent approach and a maximum likelihood method.

Some probabilistic and statistical problems in the analysis of DNA sequences

Scientific RepoRts | 7:41553 | DOI: 10

BIOINFORMATICS ORIGINAL PAPER

Benchmark collection ( 2009 )

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names