Md. Asif Uddin

    Chapter 7 VII.7

    Biological Sequences as Graphs

    Sequence alignment is a shortest path through a grid, and genome assembly is an Eulerian path through a de Bruijn graph.

    Alignment and assembly are shortest-path and Eulerian-path problems wearing biological clothes.

    How this chapter is built

    M3Load-bearing

    The content is mathematics. Understanding is demonstrated by computation, not recall.

    basics3/11what the words mean
    concept2/2what to picture
    theory0/4why it works, and when it does not
    mathematics0/15derive it, then compute it
    practice0/9build it, break it, read the papers

    Five strands, not one. Mathematics is the spine; the other four are the body. A chapter cannot pay its way out of teaching with problems, nor out of problems with teaching.

    Before you start

    The problem

    The two oldest problems in bioinformatics — comparing sequences and reconstructing them from fragments — are graph problems with known algorithms. Seeing them as such replaces a set of tool names with two derivations.

    Four ways to read a sequence, by path length and parallelismA table of four architectures. Recurrent models connect distant positions through a path that grows with distance and cannot be parallelised. Convolution shortens the path logarithmically and parallelises. Attention connects any two positions in one step, in parallel, at quadratic cost.architecturepath between two positionsover the sequenceRNNO(n)sequentialLSTM / GRUO(n)sequentialCNNO(log n)parallelAttentionO(1)parallelAttention is not a better idea than recurrence in the abstract. It is the trade that pays when thehardware is parallel and the sequences are short enough to afford n².
    Fig. 7 — Four ways to read a sequence, placed by path length and parallelism. Attention is not a better idea in the abstract; it is the trade that pays on parallel hardware.

    Apparatus

    The mathematics this chapter leans on, held in Book 0 so it can be assumed here without being taught here. Not a gate — follow a link when a step stops making sense.

    Graphs, vertices and edges 0.GR.01 · Representing a graph 0.GR.02 · Walks, paths, cycles and connectivity 0.GR.03 · Shortest paths 0.GR.06 · Eulerian and Hamiltonian paths 0.GR.07 · Complexity: P, NP, and why some problems are hard 0.GR.08

    Notation

    • 𝒱The vocabulary, as a set of tokens
    • TSequence length in tokens
    • 𝒟A dataset, as a set of examples

    Propositions

    Not yet written. The topics above are the plan for this chapter; each will become a proposition with its own figure.

    Worked problems

    0/5 problems0/4 variants0/10 exercisesowes 15 more

    Not yet written. At M3 this chapter owes 5 worked problems across 4 distinct variants, and 10 exercises, every one with a published solution. The build enforces that from the day the chapter is marked published.