Skip to content

[v0.2] Multi-witness master alignment graph (Epic) #9

@bsesic

Description

@bsesic

Stage 2 of the long-term TRACE vision (see `docs/ROADMAP.md`): simultaneous multi-witness alignment producing a canonical variant graph plus a derived aligned table view.

Goal

Implement `tracealign.align_multi(witnesses, lang, config) -> MultiAlignmentResult`, building on the v0.1 pairwise aligner. Three-phase pipeline:

  1. Pairwise distance matrix via v0.1 `align()`.
  2. UPGMA guide tree built from the distance matrix; deterministic tie-breaking on sorted witness IDs.
  3. POA-based progressive merge: walk the guide tree in post-order, align each new witness against the current variant graph via partial-order alignment, merge the result.

Phase issues

Reference documents

Branch and release strategy

  • Feature branch: `feature/v0.2-multi-witness` off `develop`
  • PR target: `develop`
  • Release branch for cutting 0.2.0: `release/0.2.0` off `main`

Acceptance criteria (from spec §8)

  • `align_multi(witnesses, lang="hbo", config=None)` works for any well-formed input
  • `flake8 src/ tests/` is clean
  • Full test suite passes on Python 3.10 / 3.11 / 3.12 (CI matrix green)
  • Permutation-invariance property test passes
  • Lossless-reconstruction property test passes
  • JSON round-trip via `tracealign.io.multi_result` preserves all fields including the guide tree's distance matrix
  • Documentation updated (`usage.md`, `details.md`, `ROADMAP.md`)
  • 0.2.0 tagged on `main`, uploaded to PyPI, archived on Zenodo
  • `CITATION.cff` version bumped

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions