TreeRefiner

TreeRefiner refines multiple sequence alignments by optimizing the sum-of-pairs function using phylogenetic tree structures and three-dimensional dynamic programming to improve alignment accuracy.

Key Features:

• Input Requirements: Requires a pre-existing multiple sequence alignment, a corresponding unrooted phylogenetic tree, and user-defined scoring parameters.
• Optimization Methodology: Projects the multiple alignment onto sub-alignments at each internal node of the phylogenetic tree, involving neighboring nodes for localized refinement.
• Three-Dimensional Dynamic Programming: Performs three-dimensional dynamic programming within a user-specified radius r around the original alignment to enable precise adjustments.
• Sum-of-Pairs Function Optimization: Optimizes the sum-of-pairs scoring function to evaluate and improve pairwise sequence similarity across the alignment.

Scientific Applications:

• Benchmarking on simulated sequences: Tested on simulated sequences initially aligned with several popular alignment tools and demonstrated substantial improvements in the percentage of correctly aligned positions.

Methodology:

Projects alignments onto sub-alignments at each internal node (including neighboring nodes), applies three-dimensional dynamic programming within a user-specified radius r around the original alignment, and optimizes the sum-of-pairs function using user-defined scoring parameters; requires a pre-existing multiple sequence alignment and a corresponding unrooted phylogenetic tree.