This preview shows page 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-115-116-117-118-119-120-121-122-123-124-125-126-127-128-129-130-131-232-233-234-235-236-237-238-239-240-241-242-243-244-245-246-247 out of 247 pages.
Protein Structure AlignmentRamji [email protected]•Kolodny, R., and Linial, N. Approximate protein structural alignment in polynomial time. PNAS, 101(33):12201-12206, 2004.•Xu, J., et. al. A Parameterized Algorithm for Protein Structure Alignment. RECOMB 2006.2Motivation3Motivation•Evolution conserves protein structure significantly more than protein sequence3Motivation•Evolution conserves protein structure significantly more than protein sequence•Structural similarity often implies functional similarity3Motivation•Structural similarity often implies functional similarity3Motivation3Motivation3Motivation3MotivationProtein A3MotivationProtein A Protein B3MotivationProtein A Protein B•Assume we know the structure of two proteins, A and B, and we know the function of A3MotivationProtein A Protein B•Assume we know the structure of two proteins, A and B, and we know the function of A•If we can produce an alignment between A and B, we might be able to infer B’s function 3MotivationProtein A Protein B•Assume we know the structure of two proteins, A and B, and we know the function of A•If we can produce an alignment between A and B, we might be able to infer B’s function 3MotivationProtein A Protein B•Assume we know the structure of two proteins, A and B, and we know the function of A•If we can produce an alignment between A and B, we might be able to infer B’s function Structural Alignment may imply functional similarity3Problem•Take 2 protein structures in R3, A and B, and output a pair of maximal substructures--one from each protein--that have the highest degree of similarity•Like protein sequence alignment, just harder ;)4Preliminaries and Definitions5Preliminaries and Definitions• Each protein is a chain of atoms in R3• Assume one atom per residue to simplify the model• Let A be a protein of n atoms, so A = (a1, . . . , an) with ai∈ R3• Define a k-long s ubchain P = (p1, p2, . . . , pk) where 1 ≤ p1≤ p2≤ · · · ≤pn, by A(P ) = (ap1, ap2, . . . , apk)• A gap is two consecutive indices, pi, pi+1, such that pi+ 1 < pi+15Preliminaries and Definitions• Each protein is a chain of atoms in R3• Assume one atom per residue to simplify the model• Let A be a protein of n atoms, so A = (a1, . . . , an) with ai∈ R3• Define a k-long s ubchain P = (p1, p2, . . . , pk) where 1 ≤ p1≤ p2≤ · · · ≤pn, by A(P ) = (ap1, ap2, . . . , apk)• A gap is two consecutive indices, pi, pi+1, such that pi+ 1 < pi+1a1a2a3a4a5a6Protein A5Preliminaries and Definitions• Each protein is a chain of atoms in R3• Assume one atom per residue to simplify the model• Let A be a protein of n atoms, so A = (a1, . . . , an) with ai∈ R3• Define a k-long s ubchain P = (p1, p2, . . . , pk) where 1 ≤ p1≤ p2≤ · · · ≤pn, by A(P ) = (ap1, ap2, . . . , apk)• A gap is two consecutive indices, pi, pi+1, such that pi+ 1 < pi+1Say P = (1, 2, 3, 5,6)a1a2a3a4a5a6Protein A5Preliminaries and Definitions• Each protein is a chain of atoms in R3• Assume one atom per residue to simplify the model• Let A be a protein of n atoms, so A = (a1, . . . , an) with ai∈ R3• Define a k-long s ubchain P = (p1, p2, . . . , pk) where 1 ≤ p1≤ p2≤ · · · ≤pn, by A(P ) = (ap1, ap2, . . . , apk)• A gap is two consecutive indices, pi, pi+1, such that pi+ 1 < pi+1Say P = (1, 2, 3, 5,6)a1a2a3a4a5a6Protein Aa1a2a3a5a6Subchain P5Preliminaries and Definitions• Each protein is a chain of atoms in R3• Assume one atom per residue to simplify the model• Let A be a protein of n atoms, so A = (a1, . . . , an) with ai∈ R3• Define a k-long s ubchain P = (p1, p2, . . . , pk) where 1 ≤ p1≤ p2≤ · · · ≤pn, by A(P ) = (ap1, ap2, . . . , apk)• A gap is two consecutive indices, pi, pi+1, such that pi+ 1 < pi+1Say P = (1, 2, 3, 5,6)a1a2a3a4a5a6Protein Aa1a2a3a5a6Subchain PGap5Preliminaries and Definitions•Consider 2 proteins, A of n atoms and B of m atoms, with 2 subchains, P of protein A and Q of protein B, with n ≥ m•Correspondence: two subchains P and Q of equal length |P| = |Q|; a correspondence associates pairs of atoms from two proteins that appear in the same position in their respective subchains•Number of gaps in a correspondence denoted by GP,Q•We keep A fixed, and apply a rigid transformation to B6Preliminaries and Definitions•Consider 2 proteins, A of n atoms and B of m atoms, with 2 subchains, P of protein A and Q of protein B, with n ≥ m•Correspondence: two subchains P and Q of equal length |P| = |Q|; a correspondence associates pairs of atoms from two proteins that appear in the same position in their respective subchains•Number of gaps in a correspondence denoted by GP,Q•We keep A fixed, and apply a rigid transformation to Ba1a2a3a4a5a6Protein Aa8a76Preliminaries and Definitions•Consider 2 proteins, A of n atoms and B of m atoms, with 2 subchains, P of protein A and Q of protein B, with n ≥ m•Correspondence: two subchains P and Q of equal length |P| = |Q|; a correspondence associates pairs of atoms from two proteins that appear in the same position in their respective subchains•Number of gaps in a correspondence denoted by GP,Q•We keep A fixed, and apply a rigid transformation to Bb1b2b3b4b5b6Protein Ba1a2a3a4a5a6Protein Aa8a76Preliminaries and Definitions•Consider 2 proteins, A of n atoms and B of m atoms, with 2 subchains, P of protein A and Q of protein B, with n ≥ m•Correspondence: two subchains P and Q of equal length |P| = |Q|; a correspondence associates pairs of atoms from two proteins that appear in the same position in their respective subchains•Number of gaps in a correspondence denoted by GP,Q•We keep A fixed, and apply a rigid transformation to Bb1b2b3b4b5b6Protein Ba1a2a3a4a5a6Protein Aa8a7a4a5a6Subchain Pa76Preliminaries and Definitions•Consider 2 proteins, A of n atoms and B of m atoms, with 2 subchains, P of protein A and Q of protein B, with n ≥ m•Correspondence: two subchains P and Q of equal length |P| = |Q|; a correspondence associates pairs of atoms from two proteins that appear in the same position in their respective subchains•Number of gaps in a correspondence denoted by GP,Q•We keep A fixed, and apply a rigid transformation to Bb1b2b3b4b5b6Protein Ba1a2a3a4a5a6Protein Aa8a7a4a5a6Subchain Pa7b4b5b6Subchain Q6Preliminaries and Definitions•Consider 2 proteins, A of n atoms and B of m atoms, with 2 subchains, P of protein A and Q
View Full Document
Unlocking...