Mercator

Mercator performs parametric whole-genome alignment using a pair hidden Markov model (PHMM) to identify maximum a posteriori (MAP) alignments across parameter ranges for analysis of complex genome rearrangements and conservation of regulatory elements.

Key Features:

• PHMM-based MAP alignment: Uses a pair hidden Markov model to compute maximum a posteriori alignments and explicitly references Needleman-Wunsch and Smith-Waterman as foundational algorithms.
• Parametric alignment: Identifies all optimal alignments across a range of alignment parameters to address parameter sensitivity and reveal alternative optimal solutions.
• Handling complex genome rearrangements: Leverages existing heuristics to segment genomes into manageable pieces for alignment of large, rearranged genomes.
• Convex polytope computations: Incorporates computational techniques for handling convex polytopes to support parametric alignment with biologically realistic models in non-coding regions.
• Conservation and biological inference: Enables detection of higher conservation of cis-regulatory elements, demonstrated between Drosophila melanogaster and Drosophila pseudoobscura.
• Quantitative assessment of parameters: Allows quantitative evaluation of how alignment parameters influence branch length estimates and downstream evolutionary inferences.

Scientific Applications:

• Orthology mapping: Supports mapping of orthologous regions across multiple genomes using parameter-robust alignments.
• Comparative genomics: Facilitates whole-genome comparisons that account for complex rearrangements and parameter variability.
• Cis-regulatory element discovery: Improves identification of conserved non-coding regulatory elements between species such as Drosophila melanogaster and Drosophila pseudoobscura.
• Phylogenetic parameter sensitivity analysis: Enables assessment of the impact of alignment parameters on branch length estimates and evolutionary dynamics.

Methodology:

Computational methods explicitly include a pair hidden Markov model (PHMM) for MAP alignment, parametric alignment to enumerate optimal alignments across parameter ranges, use of heuristics to segment genomes, and convex polytope computations; the approach builds on Needleman-Wunsch and Smith-Waterman concepts.