Cppp

Cppp computes a Constrained Persistent Phylogeny (CPPP) from a binary character matrix to reconstruct evolutionary histories that allow single gains and single losses (persistency) and accommodate back mutations under lineage-specific constraints.

Key Features:

• CPPP model: Extends the Perfect Phylogeny and the infinite sites assumption by allowing each binary character to be gained and lost at most once (persistency).
• Persistency handling: Models characters that can be gained and subsequently lost but only once across the phylogeny, enabling representation of back mutations.
• Lineage-specific constraints: Allows constraints that forbid specific character–species pairs and their ancestors from possessing particular characters, preventing persistence in those lineages.
• Conflict graph specialization: Provides an efficient polynomial-time solution for instances whose conflict graph of the binary matrix has no edges.
• Parameterized algorithm: Implements a parameterized reconstruction algorithm using the number of characters as the parameter.
• Application to protein domains: Supports analysis of protein domain presence/absence data where domains may be acquired and subsequently lost.

Scientific Applications:

• Protein domain evolution: Infers histories of acquisition and loss of protein domains using binary presence/absence matrices.
• Resolving non-Perfect Phylogeny data: Reconstructs phylogenies for binary matrices that violate the Perfect Phylogeny assumptions by allowing persistence and lineage-specific constraints.
• Modeling back mutations: Captures scenarios involving back mutations or single-event reversions that the Perfect Phylogeny model cannot represent.

Methodology:

Analyzes the conflict graph of the input binary character matrix; applies a polynomial-time algorithm when the conflict graph has no edges and employs a parameterized algorithm with the number of characters as the parameter to reconstruct the CPPP.