FAST++ Paper Atlas · 2005
FAST candidate graphs and elimination
Jianhua Zhu and Zhiping Weng, Proteins 58, 618–627 (2005)
Read FAST's four-stage workflow while keeping the public paper, the clean-room teaching implementation, and this project's Enhanced extensions clearly separated.
teaching-model
Rescue-Team Selection: from local qualification to mutual support
This is a teaching analogy, not the paper's narrative. Two cities each have a line of team members. FAST first finds locally similar candidate pairs, then asks whether candidates jointly support one consistent spatial formation.
Stage 1: five-member neighborhoods pass a local audition
Each candidate performs with four nearby teammates. Pairs whose local formations differ too much are rejected immediately.
Decoded paper language: FAST Step 1 filters residue-pair candidates by the local geometry of five adjacent Cα atoms.
Zhu & Weng 2005, p. 620, eq. (1).
Stage 2: candidates must support one another
One locally convincing candidate is not enough. Two candidates receive a weighted support link when their distance and directional relations agree.
Decoded paper language: FAST Step 2 treats residue-pair candidates as graph vertices and creates weighted edges from inter-candidate distance and orientation consistency.
Zhu & Weng 2005, p. 620, eq. (2).
Stage 3: repeatedly remove the least-supported candidates
The judges do not enumerate every possible team. They repeatedly remove weakly supported candidates until a clearer formation remains.
Decoded paper language: FAST Step 3 repeatedly prunes candidates by graph support to obtain an initial alignment, reducing the combinatorial search.
Zhu & Weng 2005, pp. 621–622, eqs. (3)–(4).
Stage 4: form a line, then rescore it
After the initial team is ordered, the judges rescore each possible pair under the current formation so missed or weak positions can be updated.
Decoded paper language: FAST Step 4 rescores under the current alignment and refines with dynamic programming for up to five rounds.
Zhu & Weng 2005, pp. 622–623, eq. (5).
Finish: read speed, coverage, and quality separately
A team formed quickly is not necessarily the best team. A tidy formation may still cover too few members, so different outcomes must be reported separately.
Decoded paper language: The paper evaluated sensitivity with SCOP, structural-core agreement with HOMSTRAD, and reported both speed and quality. Site results come from a separate clean-room teaching implementation.
Zhu & Weng 2005, pp. 624–626.
FAST in four steps plus one boundary
Do not begin by memorizing six equations. First see how a locally plausible candidate gains global support and eventually enters an ordered alignment.
1. Local filter: remove obvious mismatches
Each residue is described through the local shape of five adjacent Cα atoms; residue pairs beyond the threshold do not continue.
Keep only this: Step 1 reduces candidates with high recall; it is not the final verdict.
Zhu & Weng 2005, p. 620.
2. Candidate graph: let candidates support each other
Candidate residue pairs are vertices. The more consistent their relative distance and orientation, the stronger their connecting support.
Keep only this: Global geometric support helps reject local coincidences.
Zhu & Weng 2005, p. 620.
3. Elimination: repeatedly remove weak candidates
Pruning changes support among remaining vertices, so support is recomputed iteratively until an initial match is obtained.
Keep only this: FAST uses elimination to avoid direct enumeration of every candidate combination.
Zhu & Weng 2005, pp. 621–622.
4. Refinement: rescore and run DP
Update pair scores using the current alignment's spatial relation, then use dynamic programming to find an order-consistent path over several rounds.
Keep only this: The initial alignment is a starting point, not the finish.
Zhu & Weng 2005, pp. 622–623.
5. Separate the paper, Paper mode, and Enhanced mode
The workbench is a clean-room teaching implementation guided by the public paper. Its Step 2/3 contain documented approximations, and Enhanced adds project-specific extensions.
Keep only this: Interactive does not mean a complete reproduction of the historic FAST binary.
Check understanding
What does passing the local filter mean?
- This residue pair deserves further checking
- The two proteins are proven to share a fold
- The final alignment is complete
Local filtering only generates candidates; graph and path support are still needed.
What does an edge in the candidate graph primarily express?
- Geometric compatibility support between two candidates
- A covalent bond in the protein
- A citation relation
Vertices are residue-pair candidates; edges turn their distance and orientation agreement into support.
Is the FAST++ Workbench the historic FAST binary?
- No; it is a clean-room teaching implementation with documented approximations
- Yes; they are bit-for-bit identical
- Only Enhanced mode is original
The site explicitly separates paper facts, teaching approximations, and project extensions.
Completion task: Without the diagram, use four sentences to explain local filtering, the candidate graph, elimination, and DP refinement in order.
paper-fact
The four-stage pipeline
Step 1 filters residue pairs by five-residue local geometry. Step 2 treats candidates as graph vertices and weights edges by distance and direction consistency between candidate pairs.
Step 3 repeatedly removes weakly supported candidates to obtain an initial alignment. Step 4 rescoring and dynamic-programming refinement runs for up to five rounds.
Zhu & Weng 2005, pp. 620–623, eqs. (1)–(5).
paper-fact
Why build a candidate graph
One locally similar fragment does not guarantee global structural compatibility. The candidate graph lets each residue pair collect geometric support from other candidates before pruning reduces the combinatorial search.
The paper uses several directional angular relationships. The current web-ts code approximates the two paper-side directions with one Cα tangent, which is a teaching-implementation difference.
Zhu & Weng 2005, p. 620, eq. (2).
paper-fact
How the paper evaluated FAST
The authors used representative SCOP structures to test sensitivity and HOMSTRAD alignments to compare structural-core agreement, reporting both speed and alignment quality.
These are paper-reported results, not benchmarks reproduced by this site. The site's own public-PDB sanity checks must be presented separately.
Zhu & Weng 2005, pp. 624–626.
Glossary
- Residue-pair graph
- A graph whose vertices are candidate residue matches and whose weighted edges connect compatible candidates.
- Degree of unanimity
- A measure of overall support consistency during candidate-graph pruning.
- Clean-room
- Built from public papers, general knowledge, and original code without transplanting non-public implementations.
Interactive lab
Interactive lab loads when JavaScript is available.
Sources and limits
- The workbench is neither the historic FAST binary nor a production structure classifier.
- The local TM-like score is not TM-align's official TM-score.
- Current Step 2/3 approximations are visible and tested, but their differences from the paper still need equation-level presentation.