Tiberius

i'm not sure its as bad as O(n^2) for peasent multiplication.

for example, lets take 32767 * 8191; the worst case.

with a length of 14 and 12 bits, it should take roughly 168 operations.

so let's count them and see.

a = 0b11111111111111
b = 0b111111111111
r1 = 0
r2 = 0
count = 0
while a > 0:
  if a & 1 == 1:
     r2 = b
     while r2 != 0:
         r1, r2 = r1^r2, (r1&r2)<<1  #add function
         count += 3
  a >>= 1
  b <<= 1
  count += 2
print(count)

i get 142 for an expected 168 operations. but more importantly, the above code runs in about .02 seconds.

now what happens if i double the size if the input?

i get roughly 290 operations, for an expected 28*24 = 672 number of operations.

but agian, more importantly the code still runs in about .02 seconds.

I don't think this is a fair way to test the complexity of an algorithm. O(n²) is an upper bound to the running time. In general, the actual T(n) terms could have fractional constants, or could be a very complex polynomial in the number of digits as well.

Even in this case, The N²log₂10 is rounding up a lot of things [for example, as you move down the table, the complexity of addition keeps reducing by a fraction, but it is still O(n)].

I don't think doubling the input length is sufficient to draw conclusions. Look at the graphs of 0.1N² and NlogN:

Clearly, the hidden constants in the big O notation are relevant when you have small input sizes of 14 and 12, and you are simply doubling them.

I guess if you raise the input size to a sufficiently large power, then it might be a good indication of the complexity. (say N^5 ?)

I'm just learning this stuff, so I could be wrong.

This is known as peasant multiplication. Both schoolbook multiplication and peasant multiplication are examples of a more general algorithm

called Shift and add.

 

Your reasoning is okay except for your definition of operation.

Addition is order N as well (ie. the amount of time increases linearly with the length of the number), so you have to do K bitshifts and then one order N addition for each bitshift that passes your oddness test. N*N = O(N^2).

You can muddle with the time constants a bit by using different bases and memorizing a multiplication table for smaller numbers, larger is generally better.

This is basically the principle on which karatsuba/divide and conquer is based on iirc, but the 'multiplication table' is the same multiplication algorithm on two smaller numbers. Because this process of picking a smaller base is recursive and starts with a base dependant on your original number, it can have lower asymptotic complexity.

Ah, yes, that would make sense. For some reason I believed that addition was a constant time operation. How silly of me.

So K=Nlog₂10, and a bunch of O(N) additions for each pass in the worst case--- O(N²)

Got it, thanks.

I was looking up the fastest multiplication algorithms on Wikipedia. Karatsuba showed up [O(N^1.585)], Strassen showed up[O(N log N log log N)], all with respectable big O scores, but a friend recently told me of an algorithm that seems to work in linear time (wrt to the number of digits in the numbers).

I can't seem to find it on Google, so I'll just describe it here with an example:

Suppose you have two numbers 141 and 45 and we want to multiply them. We keep dividing the first number by 2 until it becomes 1 (integer division), and keep multiplying the 2nd number the same number of times.

141 45

70 90

35 180

17 360

8 720

4 1440

2 2880

1 5760

Now, we look at the LHS and add up all the terms that correspond to ODD terms on the left: 45+180+360+5760=6345 which is 141*45

Now as far as I could tell, there is a linear relationship between the number of iterations of division before you get down to 1 and the number of digits. (You end up adding 3 or 4 iterations per digit increase because multiplying by 10 is multiplying by 1010 in binary).

The relationship is something like K=3.322N +0.5, where N is the number of digits and K is the number of iterations. ( I wasn't too sure of a mathematical approach to the relation between K and N, so I plotted K vs N for N=1 to 600 and found that a linear relationship existed)

So in the worst case, for an N digit number, one has to do K multiplications by 2 and K divisions by 2. During the process, one has to do at max (if all LHS terms are odd) K additions as well. [Multiplying/Dividing a number by two is a constant time operation right ? Just a simple bit-shift ?] So shouldn't the overall run-time be O(2K+K)

=O(9.966N+1.5) = O(N) ?

Am I missing something here ? Can I consider division by 2 as a constant time operation as well ? I assumed it was because bit-shifting seems like something that would be classified as constant time, just as adding zero's in Karatsuba's algorithm was considered a constant time operation. Is there something wrong with the relationship between K and N ? Will it deviate for higher values on N ? (I couldn't really go beyond 600, nor could I derive a formal mathematical relationship).

I forgot I put this up...

Thanks mathematic !

Hi,

I am trying to prove that a limit exists at a point using the epsilon delta definition in the complex plane, but I can't seem to reach a conclusion.

Here's what I have been trying to get at:

[LATEX]\lim_{z\to z_o} z^2+c = {z_o}^2 +c[/LATEX]

[LATEX] |z^2+c-{z_o}^2-c|<\epsilon \ whenever\ 0<|z-z_o|<\delta[/LATEX]

[LATEX]LH=|z^2-{z_o}^2|=|z-z_o||z+z_o|[/LATEX]

[LATEX]=|z-z_o||\overline{z+z_o}|[/LATEX]

[LATEX]=|z-z_o||\bar{z}+\bar{z_o}|[/LATEX]

[LATEX]=|z\bar{z} +z\bar{z_o} -{z_o}\bar{z} -z_o\bar{z_o}|[/LATEX]

[LATEX]=| |z|^2 -|z_o|^2 +2Im(zz_o) |[/LATEX]

[LATEX]\leq||z|^2 -|z_o|^2 +2|z||z_o|| \ (because\ Im(z)\leq|z|)[/LATEX]

But I can't get any further. I did this much thinking I could factor it to the square of delta, but that didn't work out because of the positive 2zzo term.If anyone can help me out here, it would be great. Thanks.

Here are the two sets of questions that I had asked earlier:

The first set(with hypervalent_iodine's answers in orange):

1. In all the steps, 2 out of 3 of the acidic residues are de-protonated. I'm guessing that the dotted lines on the COO- group shows that it is in resonance. How did the H atom dissociate from these molecules and where did they go ? It seems irrelevant to the reaction as such since Asp 206 and Asp 297 hardly take part... But is there any particular reason they are ionized while Glu230 is not ?

The reason that the glutamate isn't deprotonated is and the aspartate residues are comes down to the pH of the enzyme pocket and the pKa's of the amino acid side chains. pKa, as I think was mentioned when we were chatting the other night, is a measure of the ability for an acidic proton to dissociate from the molecule. In this case the proton is the -COOH proton on the side chain - you can ignore the other COOH as it doesn't change anything here. The side chain for Glu has a pKa of 4.4 and the Asp side chain has a pKa of 3.7. Essentially what that is saying is that spontaneous deprotonation of the Asp side chain will occur at above a pH of 3.7, where as the Glu won't be deprotonated until the pH reaches 4.4. If you were interested, the reason for that is simply because Glu has an extra CH2 in its side chain. Alkyl groups are electron donating and will donate their electron density towards the COOH group. The more alkyl groups present or the larger the alkyl group, the more electron density there is to be donated. Since electrons are negatively charged, this property affects the stability of the corresponding COO- ion - i.e. the more negatively charged electron density that is inducted towards the COO- ion, the more negatively charged it becomes thus causing it to be less stable. What you can infer from the pKa's then, is the pH of the enzyme pocket must lie somewhere between 3.7 and 4.4. I had a look at the diagram in the 2000 paper that showed the H bonding and relative locations of the amino acids and from what I can tell it's really just there to hold it in place through H bonding. I've drawn and attached for you a picture which might make it a bit clearer for you.

2.The context is "There are many hydrogen bonds involving water molecules around the catalytic triad. The binding of the substrate, maltoheptaose, to the enzyme excludes the water molecules from the cleft and breaks the original hydrogen network"

 

The reason is, "The glucosidic oxygen is closely located to Asp-297, while the H-l is close to Asp-206.....The new hydrogen bonds and hydrophobic interactions between the substrate and the substrate-binding sites are regenerated. This results in the screening effect that weakens the hydrogen bond between Glu-230 and Asp-297"

 

This seems to be the initiation step but I can't understand how it happened. Is the H bond between Asp297 and Glu230 weakened because of the formation of another H bond between glycosidic oxygen and the H atom of Glu230 ? Both oxygens seems equally electronegative so I can't get why the Asp-Glue bond is broken.

Also, what does H1 being close to Asp-206 have anything to do with, well... anything ?

I have drawn you a better mechanism with all the amino acid residues in it that may help you make sense of it. Note that it is an SN1 type reaction. I looked at the ones the paper had and they weren't very clear on it. As you can see, the H-bonds that were broken during the reaction are reformed. What you said is correct - the H bond between Glu and Asp is broken upon addition of the substrate. The initiation step is the step where the glycosidic oxygen becomes protonated by the hydrogen on the Glu side chain. This breaks what was initially a H bond between the glycosidic oxygen and the hydrogen on the Glu side chain, which is then reformed at the end of the reaction. I think the only reason the mentioned the relative positioning of the Asp-206 to H1 is just so that the reader could visualise it (even though they drew a picture). A lot of what the paper talked about was determining the crystal structure of the substrate laden/unladen enzyme, so positions of amino acid residues are important in that sense. In terms of the reaction, the only reason that is important is because the carboxylate is able to stabilise the positively charged oxocarbenium ion.

 

3. Between which/where are the hydrophobic interactions generated? Why does this result in the weakening of the H bond?

The other paper made mention of hydrophobic residues present at positions 207 and 210. The latter of the two is said to allow for interaction between a larger variety of sugar or non sugar residues. I'm not really too sure what they mean by 'screening' effect. From memory, screening is a phenomena similar to shielding, where the electrons surrounding the nucleus of an atom 'screen' the net charge felt by the valence electrons. Sodium for instance has 11 electrons - 10 inner and 1 valence - and 11 protons. The 10 inner electrons screen some of the positive charge so that the valence electron only feels a +1 charge from the nucleus. I'm not sure how that applies to this situation, so make of it what you will.

 

For 1 and 2, I understood the situation and was just slightly confused, but for 3, I am actually clueless.

I never encountered/studied 'hydrophobic interactions' (other than in colloidal solutions) before and the wikipedia article wasn't very helpful. If you don't want to answer it because its 'hit-your-head obvious', then I'll read up on it later, but I do need your help on the first 2 questions.

The second set:

There are a few interesting things i read up in another paper that I need help understanding.... Of course, this is just another of the many proposed mechanisms for amylase action, but it seemed to include topics which had me confused before, so why not!

 

1.My previous question: "1. In all the steps, 2 out of 3 of the acidic residues are de-protonated. I'm guessing that the dotted lines on the COO- group shows that it is in resonance. How did the H atom dissociate from these molecules and where did they go ? It seems irrelevant to the reaction as such since Asp 206 and Asp 297 hardly take part... But is there any particular reason they are ionized while Glu230 is not ? "

The paper says "In the conserved structure at the catalytic center (Fig. 2), the Arg204 imino group is always hydrogen-bonded (or salt-bridged) to the side chain of the essential carboxylate Asp206. Since the arginine imino group carries a cation, the side chain of Asp206 must be anionized. This event causes a resistance to deprotonation of the Glu230 side chain which lies close to Asp206. "

There is a bit more about hydrophobic environments, and I really do not understand that part well, but for now, I can gather that the resistance to deprotonation is not only because of inherent structure (extra CH2 group like you suggested).

Could you explain why this 'resistance to deprotonation' arises ? I can't grasp why Asp206 being anionic induces stability in Glu230. (This diagram suggests that they are actually far away from each other)

Is it because the anionic Asp bonds with Glu's H atom and keeps it in place ? Your original pKa explanation still holds right, because that made perfect sense ?

 

2.The structure (fig 2) is re-arranged wrt the previous structure(and features an Arg residue), but the main residues(Glu,Asp,Asp,His) are on the top. This is a diagram of amylase's structure before the substrate enters right ?

Fig 3 is just the same diagram for the mechanism which shows that Asp 297 has no role other than holding the substrate molecule in place while Glu does its work.. So that's fine..

 

3.The paper suggests that Asp206 acts as a base catalyst..("These facts suggest the possibility of Asp206 as base catalyst (nucleophile) in the reaction pathway, probably getting involved in forming a reaction intermediate with the substrate.")

What does this even mean ?I get the 'forms an intermediate' part, but it has COO- group, seems acidic to me. Base catalysts should be OH- groups, but Asp206 is still a proton donating group....

 

4.I read that the role of calcium in amylase is purely structural. That is, its only function is to create co-ordinate bonds with groups from the top and middle domains to make the enzyme "physically" stable.

I could not however find any freely available papers on the role of the chloride ion that is present somewhere in the enzyme.

It has something to do with the activation of the enzyme, but that's all I could gather from the abstracts of some articles.

Do you have any idea about how it 'activates' amylase, or if it has any other function?

Thank you.

In step (I) of your diagram Aspartate-231 [D231] attacks C1 of the furanose through the D231 carboxylic oxygen. This is a nucleophilic attack. Remember that C1 will be slightly elctrophylic being attached to the ring O and the alkoxy O.

Sorry, I didn't see your post before, but you answered my question spot-on.

Thanks.

Great ! Thanks.

From what I understood of what you said, this is what happens:

Glu is the rest of the glutamate anion. So there's only one COOH group involved ? I was browsing around trying to find out the mechanism before I saw your reply and I stumbled across this:

This mechanism involves both aspartate and glutamate, but the description kind of confuses me.. I'll quote the mechanism from the article.

Step one is the protonation of the glycosidic oxygen by

 

the proton donor (Glu261). This is followed by a nucleophilic

 

attack on the C1 of the sugar residue in subsite-1 by Asp231

 

(nomenclature as described by Davies et al. [39]). After the

 

aglycon part of the substrate leaves, a water molecule is

 

activated, presumably by the now deprotonated Glu261. This

 

water molecule hydrolyses the covalent bond between the

 

nucleophile oxygen and the C1 of the sugar residue in subsite-1,

 

thus completing the catalytic cycle. Asp328 plays no direct role

 

in this catalytic mechanism, but is nevertheless known to be

 

important for catalysis [29]. Asp328 is presumed to elevate the

 

pKa of E261 [40,41].

I don't understand where this 'nucleophilic attack' comes in and which molecules are involved...

Thank you.

Hello,

On the PDB site, it says that "...glutamate 233, aspartate 197, and aspartate 300 work together to cleave the connection..."

Is there a generalized mechanism of some sort for this sort of cleavage ? Because I can't figure out how these groups are capable of breaking bonds...

The wikipedia article on enzyme catalysis has a section on electrostatic catalysis which seems to be relevant to amylase, but I can't figure out how it applies in this case.

From the example that is there in the wikipedia artice, The metal atom forms co-ordinate bonds with the O of water and another atom of the substrate. This extra bond makes the substrate bond(in amylase's case the glycosidic bond) weak and it breaks off, allowing hydrolysis.

I can't see where these glutamate and aspartate groups come into the picture...

Thanks.

I was looking over the mechanism of alpha amylase hydrolysis of starch. It seems that a particular pair of glucose monomers are held in place with hydrogen bonds by the amylase enzyme. The molecule bends due to these bonds thus lowering the energy required to cleave the glycosidic bond between them.

My question is, what locations on the amylase enzyme and the starch polymer does the hydrogen bonding take place ?

I found a representation of what goes on:

It shows the starch held in place.... Where are these bonds made to keep the molecule in place ?

I know its probably a stupid question because amylase looks like this

but it would be interesting to know if the answer is out there....

Thank you.

Thanks for your reply.

I may get access to column chromatography facilities in a BSc Chem Lab... Assuming I do, could you point me to a link for the method ?

Also, do you have any experience with crystallizing out(and growing) thermally unstable proteins like alpha amylase ?

Thank you.

I wanted to perform some experiments on enzyme rates and chose amylase as it is easy to obtain. However, I wanted it in pure form so that I can perform mass/concentration-based calculations as well.

Is there any way to extract alpha-amylase from human saliva?

Thank you.