dee/core/overhangs.py

"""Why a Golden Gate assembly with six correct fragments still comes back wrong.

THE FAILURE THIS CATCHES
------------------------
`cloning.py` simulates the assembly: it finds the Type IIS sites, cuts, and
chains parts whose overhangs match into a circle. If the overhangs chain, it
reports success — and it is right, as a simulation.

What it cannot see is that two of those overhangs are one base apart, or that
one is its own reverse complement. In the tube, T4 ligase does not care which
partner it found; near-identical overhangs cross-ligate and the plate comes
back with fragments in the wrong order or dropped entirely. The simulation
says the design works. The bench says otherwise, a week later.

Every one of those conflicts is decidable from the four-base sequences alone,
before anything is ordered.

WHAT THIS DOES AND DOES NOT CLAIM
---------------------------------
It reports STRUCTURAL conflicts — facts about the sequences:

    duplicate          the same overhang used twice; the assembly cannot have
                       a defined order
    palindromic        an overhang that is its own reverse complement, so a
                       fragment ligates to itself and to its own inverse
    complementary      one overhang is the reverse complement of another, so
                       the two junctions are interchangeable
    near-identical     overhangs differing by a single base, the classic
                       source of low-frequency misassembly
    low complexity     all-AT ligates weakly, all-GC ligates promiscuously

It does NOT report a "fidelity percentage". Those numbers come from published
empirical ligation datasets measured on real reactions; this engine has none
of that data, and a percentage computed from sequence alone would be a
fabricated measurement wearing a decimal point. What is returned is what can
be checked by eye — which is also what lets a user fix it.
"""
from __future__ import annotations

import re
from typing import Any, Dict, Iterable, List, Optional

# Type IIS enzymes in common use leave a 4-nt 5' overhang. The length is a
# property of the enzyme, so it is a parameter rather than a constant.
DEFAULT_LEN = 4
_COMP = str.maketrans("ACGT", "TGCA")


def revcomp(s: str) -> str:
    return s.translate(_COMP)[::-1]


def _clean(s: str) -> str:
    return re.sub(r"[^ACGTacgt]", "", s or "").upper()


def is_palindrome(oh: str) -> bool:
    """Self-complementary — ligates to itself AND to its own inverse.

    An even-length overhang can be its own reverse complement (AATT, GGCC).
    A junction built on one has no defined orientation.
    """
    return bool(oh) and oh == revcomp(oh)


def hamming(a: str, b: str) -> int:
    """Substitutions between two equal-length overhangs. -1 if lengths differ."""
    if len(a) != len(b):
        return -1
    return sum(1 for x, y in zip(a, b) if x != y)


def gc_fraction(oh: str) -> float:
    return (oh.count("G") + oh.count("C")) / len(oh) if oh else 0.0


def check(overhangs: Iterable[str], *, length: int = DEFAULT_LEN,
          min_distance: int = 2) -> Dict[str, Any]:
    """Every structural conflict in a proposed overhang set.

    `min_distance` is the Hamming distance below which two overhangs are
    reported as too similar. 2 is the working default: at distance 1 a single
    mis-pairing event produces a wrong-but-ligatable junction.
    """
    raw = list(overhangs or [])
    ohs: List[str] = []
    rejected: List[str] = []
    for o in raw:
        c = _clean(o)
        if len(c) != length:
            rejected.append(f"{o!r} is not {length} nt")
        else:
            ohs.append(c)

    conflicts: List[Dict[str, Any]] = []

    # 1. Duplicates — the assembly has no defined order at all.
    seen: Dict[str, int] = {}
    for idx, o in enumerate(ohs):
        if o in seen:
            conflicts.append({
                "kind": "duplicate", "severity": "fatal",
                "overhangs": [o], "positions": [seen[o], idx],
                "why": f"{o} is used at two junctions, so the fragments "
                       f"between them can assemble in either order."})
        else:
            seen[o] = idx

    # 2. Palindromes — a fragment that ligates to itself.
    for idx, o in enumerate(ohs):
        if is_palindrome(o):
            conflicts.append({
                "kind": "palindromic", "severity": "fatal",
                "overhangs": [o], "positions": [idx],
                "why": f"{o} is its own reverse complement, so the fragment "
                       f"can ligate to itself and to its own inversion."})

    # 3 & 4. Pairwise: complementarity and near-identity, each checked against
    # the partner AND the partner's reverse complement, because the strand a
    # ligase sees depends on which fragment arrives.
    for i in range(len(ohs)):
        for j in range(i + 1, len(ohs)):
            a, b = ohs[i], ohs[j]
            rb = revcomp(b)
            if a == rb:
                conflicts.append({
                    "kind": "complementary", "severity": "fatal",
                    "overhangs": [a, b], "positions": [i, j],
                    "why": f"{a} is the reverse complement of {b}, so those "
                           f"two junctions are interchangeable."})
                continue
            d = min(hamming(a, b), hamming(a, rb))
            if 0 < d < min_distance:
                conflicts.append({
                    "kind": "near_identical", "severity": "high",
                    "overhangs": [a, b], "positions": [i, j], "distance": d,
                    "why": f"{a} and {b} differ by {d} base"
                           f"{'' if d == 1 else 's'}; a single mis-pairing "
                           f"gives a wrong junction that still ligates."})

    # 5. Composition — weak or promiscuous ends.
    for idx, o in enumerate(ohs):
        gc = gc_fraction(o)
        if gc == 0.0:
            conflicts.append({
                "kind": "low_complexity", "severity": "medium",
                "overhangs": [o], "positions": [idx],
                "why": f"{o} is all A/T — the weakest ligation in the set, and "
                       f"the junction most likely to be missing."})
        elif gc == 1.0:
            conflicts.append({
                "kind": "low_complexity", "severity": "medium",
                "overhangs": [o], "positions": [idx],
                "why": f"{o} is all G/C, which ligates promiscuously."})

    fatal = sum(1 for c in conflicts if c["severity"] == "fatal")
    high = sum(1 for c in conflicts if c["severity"] == "high")
    if not ohs:
        verdict = "No usable overhangs given."
    elif fatal:
        verdict = (f"{fatal} conflict(s) that make the assembly ambiguous. "
                   f"This set will not build reliably.")
    elif high:
        verdict = f"{high} pair(s) close enough to misligate at low frequency."
    elif conflicts:
        verdict = "Usable, with weak junctions noted."
    else:
        verdict = f"No structural conflicts across {len(ohs)} overhangs."

    return {
        "ok": True,
        "overhangs": ohs,
        "count": len(ohs),
        "rejected": rejected,
        "conflicts": conflicts,
        "fatal": fatal,
        "usable": fatal == 0 and bool(ohs),
        "verdict": verdict,
        "basis": ("Structural conflicts computed from the sequences. NOT a "
                  "fidelity percentage — those come from published empirical "
                  "ligation datasets this engine does not have, and a number "
                  "derived from sequence alone would be invented."),
    }


def suggest(count: int, *, length: int = DEFAULT_LEN, min_distance: int = 2,
            avoid: Optional[Iterable[str]] = None) -> Dict[str, Any]:
    """A conflict-free set of `count` overhangs.

    Greedy: walk the space in a fixed order and keep any candidate that
    conflicts with nothing already chosen. Deterministic on purpose — the same
    request gives the same set, so a design is reproducible and a methods
    section can name it.
    """
    if count < 1:
        return {"ok": False, "error": "Need at least one overhang."}
    blocked = {_clean(o) for o in (avoid or []) if _clean(o)}
    chosen: List[str] = []

    def fits(cand: str) -> bool:
        if is_palindrome(cand):
            return False
        g = gc_fraction(cand)
        if g in (0.0, 1.0):
            return False
        for o in list(chosen) + list(blocked):
            if cand == o or cand == revcomp(o):
                return False
            if 0 < min(hamming(cand, o), hamming(cand, revcomp(o))) < min_distance:
                return False
        return True

    from itertools import product
    for combo in product("ACGT", repeat=length):
        if len(chosen) >= count:
            break
        cand = "".join(combo)
        if fits(cand):
            chosen.append(cand)

    if len(chosen) < count:
        # The space genuinely runs out; say so rather than return a short set
        # that looks complete.
        return {"ok": False, "kind": "exhausted",
                "error": f"Only {len(chosen)} conflict-free {length}-nt "
                         f"overhangs exist at distance {min_distance} "
                         f"(asked for {count}).",
                "found": chosen,
                "next": "Lower min_distance, use a longer overhang, or split "
                        "the assembly into two rounds."}
    return {"ok": True, "overhangs": chosen, "count": len(chosen),
            "min_distance": min_distance,
            "note": "Deterministic: the same request returns the same set, so "
                    "the design is reproducible."}