FAST++ Paper Atlas · 1998
Combinatorial-extension alignment paths
Ilya N. Shindyalov and Philip E. Bourne, Protein Engineering 11, 739–747 (1998)
Start from Aligned Fragment Pairs and learn how CE tests compatibility, controls gaps, extends ordered paths, and finally superposes and optimizes them.
teaching-model
The Broken-Bridge Crew: turning scattered clues into one route
This is a teaching analogy, not a story from the paper. Two broken trails lie across a valley. A crew first finds locally similar pieces, then checks whether they can form one walkable ordered route. Each chapter immediately decodes the analogy into CE terminology.
Chapter 1: two trails, no correspondence map
The crew has two 3D surveys but no map saying which part of trail A matches which part of trail B. Comparing the entire trails at once is too hard, so they first split the problem into local pieces.
Decoded paper language: Protein structural alignment must find residue correspondence as well as spatial superposition. CE first generates local fragment-pair candidates, then seeks candidate paths that form an alignment.
Shindyalov & Bourne 1998, pp. 739–740.
Chapter 2: local resemblance earns only a candidate ticket
The crew uses a fixed-length ruler to compare the trails piece by piece. Similar-looking pieces receive candidate tickets, but one ticket cannot prove that the whole route connects.
Decoded paper language: That ticket is an Aligned Fragment Pair (AFP). The experiments used length m=8 and first filtered local candidates by an internal-distance-difference threshold for a single AFP.
Shindyalov & Bourne 1998, pp. 740–741.
Chapter 3: a new bridge segment cannot make the route go backward
When attaching a candidate to the route under construction, the crew asks whether it agrees with existing pieces, moves forward on both maps, and avoids an excessively large break.
Decoded paper language: CE extends an alignment path constrained by the order of both sequences and tests the geometric relation between an AFP and the existing path. Typical settings also limited the maximum gap to G=30.
Shindyalov & Bourne 1998, pp. 740–741.
Chapter 4: extend the most promising segment first
Trying every possible connection could keep the crew planning forever. They therefore extend the currently best-looking candidate first to keep the work tractable.
Decoded paper language: The CE search described in the paper makes a heuristic tradeoff: an implementation may extend the current best AFP rather than enumerate every combinatorial path, so the result should not be read as a guaranteed global optimum.
Shindyalov & Bourne 1998, p. 741.
Chapter 5: superpose the route, then repair its gaps
Once a route has formed, the crew superposes the two 3D maps, checks whole-route error, shifts some breaks, and performs a final cleanup.
Decoded paper language: Candidate paths are evaluated by rigid-body RMSD. Better paths undergo gap relocation and final dynamic-programming optimization on a post-superposition distance matrix. The ordered path also means CE cannot cover every rearranged-fragment, non-topological similarity.
Shindyalov & Bourne 1998, pp. 741–742.
A five-stop plain-language map of CE
Do not memorize D₀, D₁, or formulas yet. Follow one thread only: where candidates come from, how they support one another, and how they become a final alignment.
1. Two structures in, residue matches out
CE does not merely rotate two models together on screen. It must decide which residues in A correspond to which residues in B; only then is there a basis for rigid superposition.
Keep only this: Structural alignment = find matches + superpose.
Shindyalov & Bourne 1998, pp. 739–740.
2. An AFP is a local candidate, not the answer
The algorithm scans fixed-length fragments from both structures and keeps pairs with sufficiently similar internal geometry. This quickly narrows the search, but local coincidences can remain.
Keep only this: One AFP says only: these two small pieces deserve another look.
Shindyalov & Bourne 1998, pp. 740–741.
3. Compatibility joins candidates into an ordered path
A new AFP must not only look good alone; it must agree geometrically with selected AFPs and move forward along both sequences. Gaps may skip unmatched regions, but they are bounded.
Keep only this: CE wants candidates that form one route, not scattered pretty fragments.
Shindyalov & Bourne 1998, pp. 740–741.
4. For speed, CE does not exhaust every path
The number of combinations grows quickly, so CE prioritizes promising extensions. This keeps the search practical, but it also makes the procedure heuristic.
Keep only this: Practical runtime comes from a search tradeoff.
Shindyalov & Bourne 1998, p. 741.
5. Superpose, repair gaps, finish with DP—and remember the limit
The initial path is evaluated by RMSD, gaps are adjusted, and a final DP optimization uses post-superposition distances. Because the path preserves sequence order, similarities with major fragment rearrangements may not be fully represented.
Keep only this: CE is built for order-consistent extension; it does not cover every topological rearrangement.
Shindyalov & Bourne 1998, pp. 741–742.
Check understanding
What best describes an AFP?
- The final alignment of the entire proteins
- A locally similar fixed-length fragment pair from two structures
- The only gap allowed after superposition
An AFP is a candidate building block. It must pass compatibility and path checks before becoming part of an alignment.
Why is one strongly similar local fragment not enough?
- Local resemblance may be coincidental; it must connect to others in geometric and sequence-order agreement
- CE does not use local fragments at all
- Any low RMSD must be wrong
A structural alignment needs broader support. CE extension tests whether an AFP can coexist with the existing path.
Can CE's ordered path express every similarity involving rearranged fragments?
- Yes; fragments may move backward and reorder freely
- Not necessarily; the sequence-order constraint misses some non-topological similarities
- Yes, if every gap is set to zero
CE paths advance through both sequences in order, so they cannot freely express large fragment rearrangements. This is a method boundary, not a user error.
Completion task: Without looking above, use three sentences to explain what an AFP is, what an ordered path constrains, and why gaps must be controlled. If you get stuck, revisit only stops 2, 3, and 5 of the plain-language guide.
paper-fact
Candidate unit: the Aligned Fragment Pair
CE uses fixed-length fragment pairs as candidates. The paper empirically selected m=8 as a compromise between local structural information and search resolution.
Shindyalov & Bourne 1998, pp. 739–741.
paper-fact
Extending a path through three levels of checks
A candidate first passes a single-AFP threshold, then a relation test against the existing path, and finally a whole-path average-distance test. Typical settings were D₀=3 Å, D₁=4 Å, and maximum gap G=30.
For speed, the implementation can extend only the current best AFP rather than enumerate every path, making this a search heuristic with explicit tradeoffs.
Shindyalov & Bourne 1998, pp. 740–741.
paper-fact
Superposition, gap relocation, and final optimization
Candidate paths are evaluated by rigid-body RMSD. Better paths undergo gap relocation and dynamic programming on the superposed distance matrix.
Shindyalov & Bourne 1998, pp. 741–742.
Glossary
- AFP
- A pair of fixed-length fragments considered locally similar across two structures.
- Alignment path
- A candidate alignment assembled from AFPs while advancing through both sequence orders.
- Gap
- A region where residues in one chain have no matched residues in the other.
Interactive lab
Interactive lab loads when JavaScript is available.
Sources and limits
- The sequence-order constraint cannot represent every non-topological similarity.
- Current interactive values are for learning and do not reproduce the paper's full parameter workflow.