PaperlayerView exact revision on arXiv

Source-linked AI summary

Ultra-large alignments using Phylogeny-aware Profiles

Nam-phuong Nguyen, Siavash Mirarab, Keerthana Kumar, Tandy Warnow

arXiv:1504.01142v1q-bio.GNcs.CEcs.LG

TL;DR

Accurate large-scale multiple sequence alignment is difficult, particularly for fragmentary sequences, despite its role in biological analyses. UPP builds a backbone alignment and uses a phylogeny-aware ensemble of profile HMMs to add query sequences. On fragmentary datasets, it ranks among the first-tier methods for alignment error across all collections and for tree error in three of four.

  • Problem

    Large-scale MSAs are important for phylogenetic and other biological analyses, but accurate alignment is difficult, especially for fragmentary sequences.

    Source: Background · p. 2

  • Method

    UPP builds an alignment and tree on a backbone subset, then uses profile HMMs derived from that backbone to align the remaining sequences.

    Source: Background · p. 4, Conclusions · p. 21

  • Results

    On fragmentary datasets, UPP was first-tier for alignment SP-error across all collections and for tree error in three of four, and was the only method with reasonably low errors across all such datasets.

    Source: Results and discussion · pp. 11, 13

  • Takeaways & Limitations

    The authors conclude that full-length backbones and ensemble HMMs target different performance aspects, increasing sensitivity to remote homology and reducing alignment SP-error and tree error.

    Source: Conclusions · p. 22

    The HomFam rhv dataset was omitted because its alignment was flagged as “very weak.”

    Source: Performance Study · p. 24

Abstract

from arXiv · show

Many biological questions, including the estimation of deep evolutionary histories and the detection of remote homology between protein sequences, rely upon multiple sequence alignments (MSAs) and phylogenetic trees of large datasets. However, accurate large-scale multiple sequence alignment is very difficult, especially when the dataset contains fragmentary sequences. We present UPP, an MSA method that uses a new machine learning technique - the Ensemble of Hidden Markov Models - that we propose here. UPP produces highly accurate alignments for both nucleotide and amino acid sequences, even on ultra-large datasets or datasets containing fragmentary sequences. UPP is available at https://github.com/smirarab/sepp.

Background

Large-scale MSAs matter for phylogenetic and other biological analyses, but accuracy is difficult, especially with fragmentary sequences and high evolutionary rates. UPP addresses these challenges with a de novo, phylogeny-aware ensemble of profile HMMs that adds query sequences to a backbone alignment.

Background

  • Large MSAs support biological analyses, but accurate alignment is difficult, particularly for rapidly evolving or fragmentary datasets.Accurate alignments also affect maximum-likelihood tree accuracy; fragmentary sequences can arise when short reads cannot be assembled into full-length sequences.Source: Background · p. 2
  • UPP is a de novo MSA method that represents alignments with a phylogeny-aware ensemble of profile HMMs.Unlike seed-alignment approaches, it does not require precomputed or experimentally curated alignments.Source: Background · pp. 2, 5
  • UPP selects a backbone subset, computes its alignment and maximum-likelihood tree with PASTA, then aligns remaining query sequences to profile HMMs.It preferentially selects full-length backbone sequences, defined as within 25% of the typical locus length, or the median input length when typical length is unknown.Source: Background · pp. 2, 4
  • The HMM ensemble contains a model for the full backbone and models built from alignment subsets induced by recursively decomposing the backbone tree.Decomposition continues until each subtree contains at most 10 sequences.Source: Background · p. 5
  • Each query is scored against the HMMs, and its best-scoring model guides insertion into the backbone alignment through positional-homology transitivity.Unaligned letters create insertion sites; adjacent sites are combined and masked before phylogenetic analysis.Source: Background · pp. 5–6
  • UPP reports high accuracy on phylogenetic and structural benchmarks, completing 10,000 sequences in under an hour and one million in 12 days on 12 cores.The authors also report strong accuracy when datasets contain many highly fragmentary sequences.Source: Background · p. 6

Results and discussion

UPP performed especially well on fragmentary datasets, while PASTA led on full-length datasets. Tests of UPP’s design and scale show that its backbone and HMM choices matter, and that UPP(Fast) can analyze up to one million sequences.

Results and discussion

  • Clade-based ensembles were generally as accurate but slower, while disjoint subsets could sharply reduce accuracy; MAFFT sequence addition reduced accuracy, and hmmbuild option changes did not improve it.On Indelible 10000M2, disjoint subsets raised alignment SP-error from 3.5% to 28.2% and tree error from 0.6% to 19.9%.Source: Results and discussion · pp. 8–9
  • On full-length datasets, PASTA ranked first on average for alignment SP-error, tree error, and TC; UPP followed, then MAFFT, with Muscle and Clustal-Omega behind.UPP was generally first- or second-tier for tree error, but its alignment SP-error fell to second tier on Indelible 10K and HomFam(2).Source: Results and discussion · p. 11, Table 2 · p. 12
  • On fragmentary datasets, UPP ranked first-tier for alignment SP-error across all collections and for tree error in three of four; only UPP kept both reasonably low throughout.PASTA was not first-tier on any collection for either criterion.Source: Results and discussion · pp. 11, 13, Table 3 · p. 13
  • On ROSE NT 1000M2, UPP’s alignment SP-error rose only slightly through 50% fragmentation, while other methods had larger increases in alignment or tree error.The fragmentary sequences averaged 500 bases, roughly half the average sequence length.Source: Results and discussion · p. 13, Figure 3 · p. 14
  • Fragment robustness depended on full-length-only backbones and HMM ensembles: the former improved accuracy, while ensembles enabled all datasets to be aligned and generally reduced tree error.Default UPP uses 1,000-sequence backbones, PASTA, an HMM ensemble, and hmmalign; 100-sequence backbones typically raised alignment and tree errors but reduced ensemble runtime.Source: Results and discussion · pp. 7, 8, 9, 15
  • At 1,000,000 RNASim sequences, UPP(Fast) completed in 12 days with 12.8% alignment SP-error and 2.0% ∆FN; PASTA took 15 days with 18.5% alignment SP-error and 0.4% ∆FN.At 100K and 200K sequences, only UPP(Fast) and PASTA completed within 24 hours on the 12-core TACC setup; million-sequence runtimes used a different machine and are not directly comparable.Source: Results and discussion · pp. 15, 18
  • UPP(Fast) scaled nearly linearly, taking 17.8 hours at 200K sequences; for UPP(Default), searching for the best HMM dominated runtime on large datasets.On CRW datasets, UPP(Default) averaged 11.6 hours versus 0.4 hours for MAFFT, and was generally the slowest method.Source: Results and discussion · pp. 18–19

Conclusions

UPP is highly robust to fragmentary data, while its relative advantage over PASTA depends on whether sequences are fragmented. Its phylogeny-aware profile strategy supports accurate alignment at large scales.

Conclusions

  • With fragmentary sequences, UPP maintains nearly its full-length SP-error while PASTA’s SP-error rises substantially, and UPP’s tree error does not increase as much.On fragment-free datasets, PASTA typically produces more accurate maximum-likelihood trees, while UPP tends to have lower SP-error but lower TC scores.Source: Conclusions · p. 21
  • UPP builds a PASTA backbone alignment and tree, then represents local tree regions with separate profile HMMs suited to closely related sequences.The backbone is restricted to full-length sequences, a design step the paper identifies as critical to robustness to fragments.Source: Conclusions · p. 21
  • The ensemble of HMMs and full-length backbone together increase sensitivity to remote homology, especially for fragments, and reduce alignment SP-error and tree error.The paper describes these design choices as targeting different aspects of performance.Source: Conclusions · p. 22
  • UPP’s running time scales nearly linearly, and its output alignment has SP-error close to the backbone alignment’s, keeping large-dataset accuracy near that of smaller datasets.The study reports high accuracy on difficult, high-evolution-rate, fragmentary, and ultra-large datasets, including datasets of up to one million sequences.Source: Conclusions · p. 22

Performance Study

The performance study compares UPP with existing methods using simulated and biological datasets, including large datasets and tests of fragmentation. The benchmarks span nucleotide and amino-acid sequences.

Performance Study

  • The study evaluates methods on simulated ROSE NT, Indelible 10K, RNASim, and ROSE AA collections, ranging from 1,000 to 1,000,000 sequences.The collections include nucleotide and amino-acid datasets.Source: Performance Study · pp. 22–23
  • Biological benchmarks include large CRW 16S datasets with curated alignments and ten amino-acid datasets with curated alignments ranging from 320 to 807 sequences.The CRW sets span three phylogenetic domains or bacteria; the amino-acid sets comprise eight BAliBASE datasets and two others.Source: Performance Study · p. 23
  • HomFam comprises 19 of its largest amino-acid sequence datasets, spanning 10,099–93,681 sequences, with Homstrad reference alignments on small subsets of 5–20 sequences (median 7), used to evaluate alignment methods.The rhv dataset was omitted because the PFAM website warned that its alignment was very weak.Source: Performance Study · pp. 23–24
  • Some nucleotide datasets were tested with 12.5%, 25%, or 50% of sequences made fragmentary using random substrings averaging 500 base pairs.Fragment lengths were drawn from a normal distribution with a 60-base-pair standard deviation.Source: Performance Study · p. 24

Basic alignment methods

The methods section specifies software versions, run settings, and command-line invocations for the alignment programs used in the study. It also distinguishes the tested MAFFT modes and UPP variants.

Basic alignment methods

  • Each dataset was aligned when possible with Clustal-Omega 1.2.0, MAFFT 6.956b, MUSCLE 3.8.31, and PASTA 1.5.1.MUSCLE used “-maxiters 2” on datasets of 3,000 sequences or greater. MAFFT-default used version 7.143 because of a bug in earlier MAFFT 6.956b versions; other MAFFT modes were L-INS-i and PartTree.Source: Basic alignment methods · p. 24
  • PASTA ran for three iterations or up to 24 hours, using a MAFFT-PartTree starting tree except on RNASim datasets.RNASim used an ML tree from the UPP(Fast, NoDecomp) alignment because MAFFT-PartTree could not run on the largest datasets.Source: Basic alignment methods · pp. 24–25
  • The listed commands specify separate invocations for Clustal-Omega, three MAFFT alignment modes, MUSCLE, PASTA, and UPP.The UPP-disjoint command changes the UPP invocation with the “-S normal” option.Source: Basic alignment methods · p. 25
  • The UPP command takes a backbone alignment and tree plus query sequences, while PASTA is invoked with input sequences and a starting tree.The listed UPP variants are UPP and UPP-disjoint.Source: Basic alignment methods · p. 25

HMMER Commands

UPP uses HMMER commands to build profile HMMs, search for the best-fitting model for each query, and insert queries into alignments.

HMMER Commands

  • hmmbuild creates profile HMMs from backbone alignments, while hmmsearch scores query sequences against profiles to identify a best match.The study uses HMMER 3.0 for these operations and for query insertion.Source: HMMER Commands · pp. 25–26
  • hmmalign inserts query sequences into the alignment using the selected profile HMM.The command list includes the hmmalign invocation for this step.Source: HMMER Commands · pp. 25–26

Maximum Likelihood Tree Estimation

Maximum-likelihood trees were estimated with FastTree for datasets of 1,000 or more sequences and RAxML for smaller datasets, using models selected by sequence type or dataset. Alignment quality was assessed with SP-error and TC scores, while tree error and ΔFN measured estimated-tree error and its difference from error on the true alignment.

Maximum Likelihood Tree Estimation

  • FastTree was used for datasets with 1,000 or more sequences and RAxML for smaller datasets, with GTR for nucleotide data, JTT for simulated amino acids, and ProtEST-selected models for biological amino acids.FastTree version 2.1.5 SSE3 and RAxML version 8.0.6 were used.Source: Maximum Likelihood Tree Estimation · p. 26
  • The listed commands specify FastTree AA and nucleotide runs and a RAxML amino-acid run.The nucleotide command uses -nt and -gtr; the RAxML command specifies a protein model and GAMMA.Source: Maximum Likelihood Tree Estimation · p. 26
  • SP-error averages SPFN and SPFP rates, and TC scores were also used to compare estimated alignments with reference alignments.SPFN counts reference homologous pairs absent from the estimate; SPFP counts estimated homologous pairs absent from the reference.Source: Maximum Likelihood Tree Estimation · p. 26
  • Tree error was measured as the false-negative (missing-branch) rate, while ΔFN compares estimated-tree error with error on the true alignment.ΔFN is usually greater than zero, but can be less than zero when the estimated ML tree is more accurate than ML on the true alignment.Source: Maximum Likelihood Tree Estimation · pp. 26–27
Loading 1504.01142v1…