Efficient representation of uncertainty in multiple sequence alignments using directed acyclic graphs.

Area of Science:

• Bioinformatics
• Computational Biology
• Phylogenetics

Background:

• Multiple sequence alignments (MSAs) are foundational in bioinformatics, but downstream analyses are sensitive to alignment choice.
• Ignoring alignment uncertainty can introduce significant bias in biological inference.
• Existing methods for probabilistic alignment sampling are not widely integrated into downstream algorithms.

Purpose of the Study:

• To develop a framework for representing sets of sampled multiple sequence alignments (MSAs).
• To enable the use of probabilistic alignment information in downstream bioinformatics analyses.
• To improve the accuracy and reduce bias in phylogenetic inference and other MSA-dependent tasks.

Main Methods:

• Representing sampled MSAs as a directed acyclic graph (DAG) where nodes are alignment columns.
• Estimating column probabilities from empirical frequencies to enable sample-based posterior alignment probability estimation.
• Leveraging conditional independencies within the DAG to encode a larger effective set of alignments.

Main Results:

• The DAG framework naturally represents distributions over MSAs, increasing the effective sample size.
• Enables efficient scaling of existing algorithms to operate on large sets of alignments.
• Demonstrates computation of marginal probabilities for tree topologies by averaging over numerous MSAs.

Conclusions:

• The alignment DAG provides a robust method for representing MSA distributions.
• Facilitates improved downstream analyses, including more accurate summary alignments and enhanced tree inference.
• Offers a scalable solution for incorporating alignment uncertainty into bioinformatics workflows.