[Bioperl-l] program that search databais
Aaron J Mackey
ajm6q@virginia.edu
Tue, 3 Oct 2000 11:38:19 -0400 (EDT)
This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.
Send mail to mime@docserver.cac.washington.edu for more info.
---2138111441-92958057-970587499=:75456
Content-Type: TEXT/PLAIN; charset=US-ASCII
A few people have asked for this info, so I'm copying the list. Excuse
the slightly offtopic conversation.
References describing exact calculations of pI from residue content:
Ribeiro JM. Sillero A.
A program to calculate the isoelectric point of macromolecules.
Computers in Biology & Medicine. 21(3):131-41, 1991.
Ribeiro JM. Sillero A.
An algorithm for the computer calculation of the coefficients of a
polynomial that allows determination of isoelectric points of
proteins and other macromolecules.
Computers in Biology & Medicine. 20(4):235-42, 1990.
Sillero A. Ribeiro JM.
Isoelectric points of proteins: theoretical determination.
Analytical Biochemistry. 179(2):319-25, 1989 Jun.
Attached is a slightly-cruddy c program implementing their algorithm
(alas, I never got around to doing it in Perl ...)
Please feel free to send me questions.
-Aaron
On Mon, 2 Oct 2000, Aaron J Mackey wrote:
>
> I once wrote a pI solver in Perl using a method to explicitly solve for
> pI. But it turns out it's much better to simply 'slide' from pH 0 to pH
> 14 and see where the electric charge function goes from negative to
> positive. While less elegant, it's much faster (and you can play tricks
> with numerical derivatives near zero to get an accurate value, if you'd
> like).
>
> I'll send you the references and my code, if you're interested.
>
> -Aaron
>
> On Mon, 2 Oct 2000, Tsvika wrote:
>
> > Hi all,
> >
> > I am writing a Perl program that search proteins database, and
> > find matches according predicted Molecular Wight (MW) versus MW
> > from results of Mass spectrometry. Also, the program takes short
> > amino acid sequence (tag) and looks at the N-term or C-term as
> > you like. The program has MW tolerance (+/-X%), and uses regexp
> > for the tag input. The program is fully functional, and I used it
> > on C.elegans wormpep25 successfully.
> > Now I want to add the P.I., isoelectric point, option. So, like
> > MW, one can try to find matches according to the P.I. results of
> > first dimension of 2D gel versus the predicted P.I.
> > I would appreciate if you could help me with P.I. calculations,
> > and algorithms. Also, I would like to hear if you think it is a
> > start for Proteomics applications in bioperl?
> >
> > Tsvika.
> >
>
>
--
o ~ ~ ~ ~ ~ ~ o
/ Aaron J Mackey \
\ Dr. Pearson Laboratory /
\ University of Virginia \
/ (804) 924-2821 \
\ amackey@virginia.edu /
o ~ ~ ~ ~ ~ ~ o
---2138111441-92958057-970587499=:75456
Content-Type: TEXT/PLAIN; charset=US-ASCII; name="pI.c"
Content-Transfer-Encoding: BASE64
Content-ID: <Pine.A41.4.21.0010031138190.75456@node13.unix.Virginia.EDU>
Content-Description: pI.c
Content-Disposition: attachment; filename="pI.c"
I2luY2x1ZGUgPHN0ZGlvLmg+DQojaW5jbHVkZSA8c3RkbGliLmg+DQojaW5j
bHVkZSA8c3RyaW5nLmg+DQojaW5jbHVkZSA8bWF0aC5oPg0KDQpzdHJ1Y3Qg
c2VxX3N0ciB7DQogIGNoYXIgKmlkOw0KICBjaGFyICpkZXNjOw0KICBmbG9h
dCBwSTsNCiAgaW50IHJlc2NvdW50WzIzXTsNCiAgaW50IE1XOw0KICBpbnQg
bGVuZ3RoOw0KfTsNCg0Kdm9pZCBzZXR1cF9jb2VmZihkb3VibGUgKioqYm94
ZXMsIGludCBucmVzLCBpbnQgbnBvcywgZG91YmxlICpwS2FzKTsNCnZvaWQg
Y2FsY19jb2VmZihkb3VibGUgKipib3hlcywgaW50ICpjb3VudHMsIGRvdWJs
ZSAqKmNvZWZmcywgaW50IG5yZXMsIGludCBucG9zKTsNCmRvdWJsZSBzb2x2
ZV9jb2VmZihkb3VibGUgKmNvZWZmcywgaW50IG5yZXMpOw0KZG91YmxlIGNh
bGNfcG9seShkb3VibGUgeCwgZG91YmxlICpjb2VmZiwgaW50IG0pOw0KZG91
YmxlIGNhbGNfZGVyKGRvdWJsZSB4LCBkb3VibGUgKmNvZWZmLCBpbnQgbSk7
DQp2b2lkIGR1bXBfc2VxKEZJTEUgKmZwb3V0LCBzdHJ1Y3Qgc2VxX3N0ciAq
c2VxKTsNCnZvaWQgc2F2ZV9zZXEoc3RydWN0IHNlcV9zdHIgKnNlcSk7DQpz
dHJ1Y3Qgc2VxX3N0ciAqbmV4dF9zZXEoRklMRSAqZnApOw0KaW50IGNhbGNf
TVcoc3RydWN0IHNlcV9zdHIgKnNlcSk7DQpmbG9hdCBjYWxjX3BJKHN0cnVj
dCBzZXFfc3RyICpzZXEpOyANCg0Kc3RydWN0IHNlcV9zdHIgKipzYXZlZF9z
ZXFzID0gTlVMTDsNCmludCBuc2VxID0gMDsgLyogZ2xvYmFsIHRvIHN0b3Jl
IGhvdyBtYW55IHNlcSdzIGFyZSBpbiBzYXZlZF9zZXFzICovDQppbnQgbnNh
dmVkID0gMDsNCmNoYXIgYWxwaGFbXSA9ICJBUk5EQ1FFR0hJTEtNRlBTVFdZ
VkJaWCI7DQpjaGFyIHNhdmVkX2J1ZmZlcls1MTJdID0geyAnXDAnIH07DQoN
CmRvdWJsZSBzdG9ja19wS2FzWzldID0geyA5LjY5LCAgLyogTkg0KyAqLw0K
CQkJIDYuMCwgIC8qIEhpcysgKi8NCgkJCSAxMC41LCAvKiBMeXMrICovDQoJ
CQkgMTIuNCwgLyogQXJnKyAqLw0KCQkJIA0KCQkJIDIuMzQsIC8qIENPT0gg
Ki8NCgkJCSAzLjg2LCAvKiBBc3AgICovDQoJCQkgNC4yNSwgLyogR2x1ICAq
Lw0KCQkJIDguMzMsIC8qIEN5cyAgKi8NCgkJCSAxMC4wICAvKiBUeXIgICov
DQp9Ow0KDQpmbG9hdCBhYW1hc3NbMjNdID0geyA3MS4wOCwNCgkJICAgICAx
NTYuMiwNCgkJICAgICAxMTQuMTEsDQoJCSAgICAgMTE1LjA5LA0KCQkgICAg
IDEwMy4xNCwNCgkJICAgICAxMjguMTQsDQoJCSAgICAgMTI5LjEyLA0KCQkg
ICAgIDU3LjA2LA0KCQkgICAgIDEzNy4xNSwNCgkJICAgICAxMTMuMTcsDQoJ
CSAgICAgMTEzLjE3LA0KCQkgICAgIDEyOC4xOCwNCgkJICAgICAxMzEuMjEs
DQoJCSAgICAgMTQ3LjE4LA0KCQkgICAgIDk3LjEyLA0KCQkgICAgIDg3LjA4
LA0KCQkgICAgIDEwMS4xMSwNCgkJICAgICAxODYuMjEsDQoJCSAgICAgMTYz
LjE4LA0KCQkgICAgIDk5LjE0LA0KCQkgICAgIDExNC42NCwNCgkJICAgICAx
MjguNzQsDQoJCSAgICAgMTExLjQ0DQp9Ow0KDQoNCmludCBtYWluKGludCBh
cmdjLCBjaGFyICphcmd2W10pIHsNCg0KICBGSUxFICpmcCwgKmZwb3V0Ow0K
ICBpbnQgdG90YWxjb3VudHNbMjNdLCBubGliID0gMCwgbnNpemUgPSAwOw0K
ICBzdHJ1Y3Qgc2VxX3N0ciAqc2VxOw0KICBpbnQgaTsNCg0KICBpZiAoIGFy
Z2MgPiAxICkgeyAvKiBmaWxlbmFtZSBzcGVjaWZpZWQgb24gY29tbWFuZCBs
aW5lICovDQogICAgZnAgPSBmb3Blbihhcmd2WzFdLCAiciIpOw0KICAgIGlm
ICggZnAgPT0gTlVMTCApIHsNCiAgICAgIGZwcmludGYoc3RkZXJyLCAiQ291
bGRuJ3Qgb3BlbiBmaWxlOiAnJXMnIGZvciByZWFkaW5nXG4iLCBhcmd2WzFd
KTsNCiAgICAgIGV4aXQoMSk7DQogICAgfQ0KICB9IGVsc2Ugew0KICAgIGZw
ID0gc3RkaW47DQogIH0NCg0KICBpZiggYXJnYyA+IDIgKSB7IC8qIGZpbGVu
YW1lIGZvciBvdXRwdXQgcHJlc2VudCAqLw0KICAgIGZwb3V0ID0gZm9wZW4o
YXJndlsyXSwgInciKTsNCiAgICBpZiAoIGZwb3V0ID09IE5VTEwgKSB7DQog
ICAgICBmcHJpbnRmKHN0ZGVyciwgIkNvdWxkbid0IG9wZW4gZmlsZTogJyVz
JyBmb3Igd3JpdGluZ1xuIiwgYXJndlsyXSk7DQogICAgICBleGl0KDEpOw0K
ICAgIH0NCiAgfSBlbHNlIHsNCiAgICBmcG91dCA9IHN0ZG91dDsNCiAgfQ0K
DQogIGZvcihpID0gMCA7IGkgPCAyMyA7IGkrKykgew0KICAgIHRvdGFsY291
bnRzW2ldID0gMDsNCiAgfQ0KDQogIHdoaWxlICgoc2VxID0gbmV4dF9zZXEo
ZnApKSAhPSBOVUxMKSB7DQoNCiAgICBubGliKys7DQogICAgbnNpemUgKz0g
c2VxLT5sZW5ndGg7DQoNCiAgICBzZXEtPk1XID0gY2FsY19NVyhzZXEpOw0K
ICAgIHNlcS0+cEkgPSBjYWxjX3BJKHNlcSk7DQoNCiAgICBpZihzZXEtPnBJ
ID09IC0xLjApIHsNCiAgICAgIC8qICAgICAgZnByaW50ZihzdGRlcnIsICJp
ZDogJXNcbiIsIHNlcS0+aWQpOyAqLw0KICAgIH0NCg0KICAgIGZvcihpID0g
MCA7IGkgPCAyMyA7IGkrKykgew0KICAgICAgdG90YWxjb3VudHNbaV0gKz0g
c2VxLT5yZXNjb3VudFtpXTsNCiAgICB9DQoNCiAgICBzYXZlX3NlcShzZXEp
Ow0KICB9DQoNCiAgZmNsb3NlKGZwKTsNCiAgDQoNCiAgZnByaW50ZihmcG91
dCwgIlNlcXVlbmNlczogJWRcdFJlc2lkdWVzOiAlZFxuIiwgbmxpYiwgbnNp
emUpOw0KDQogIGZvcihpID0gMCA7IGkgPCAyMyA7IGkrKykgew0KICAgIGZw
cmludGYoZnBvdXQsICIlY1x0JWRcbiIsIGFscGhhW2ldLCB0b3RhbGNvdW50
c1tpXSk7DQogIH0NCg0KICBmcHJpbnRmKGZwb3V0LCAiLS1cbiIpOw0KDQog
IGZvcihpID0gMCA7IGkgPCBubGliIDsgaSsrKSB7DQogICAgZHVtcF9zZXEo
ZnBvdXQsIHNhdmVkX3NlcXNbaV0pOyAvKiBkdW1wX3NlcSBmcmVlJ3MgdGhl
IHNlcSBzdHJ1Y3R1cmUgKi8NCiAgfQ0KDQogIGZjbG9zZShmcG91dCk7DQoN
CiAgZnJlZShzYXZlZF9zZXFzKTsNCg0KICBleGl0KDApOw0KfQ0KDQpzdHJ1
Y3Qgc2VxX3N0ciAqbmV4dF9zZXEoRklMRSAqZnApIHsNCg0KICBzdHJ1Y3Qg
c2VxX3N0ciAqc2VxOw0KICBjaGFyICpvZmZzZXQ7DQogIGNoYXIgKmlkOw0K
ICBjaGFyICpkZXNjOw0KICBpbnQgcmVzY291bnRbMjNdOw0KICBjaGFyIGJ1
ZmZlcls1MTJdOw0KICBpbnQgaSwgbGVuZ3RoID0gMDsNCiAgY2hhciAqajsN
Cg0KICBpZihzYXZlZF9idWZmZXJbMF0gIT0gJ1wwJykgew0KICAgIHN0cm5j
cHkoYnVmZmVyLCBzYXZlZF9idWZmZXIsIHNpemVvZihidWZmZXIpKTsNCiAg
fSBlbHNlIHsNCiAgICBidWZmZXJbMF0gPSAnXDAnOw0KICB9DQoNCiAgd2hp
bGUoYnVmZmVyWzBdICE9ICc+Jykgew0KICAgIGlmKGZnZXRzKGJ1ZmZlciwg
c2l6ZW9mKGJ1ZmZlciksIGZwKSA9PSBOVUxMKQ0KICAgICAgcmV0dXJuIE5V
TEw7DQogIH0NCg0KICBvZmZzZXQgPSBzdHJjaHIoYnVmZmVyLCAnICcpOyAv
KiB0aGUgc3BhY2Ugd2hpY2ggc2VwYXJhdGVzIGlkIGZyb20gZGVzYyAqLw0K
ICBpZCA9IChjaGFyICopIGNhbGxvYygob2Zmc2V0IC0gYnVmZmVyICsgMSks
IHNpemVvZihjaGFyKSk7DQogIGlmKGlkID09IE5VTEwpIHsNCiAgICBmcHJp
bnRmKHN0ZGVyciwgIkNvdWxkbid0IGNhbGxvYyBtZW1vcnkgZm9yIGlkIVxu
Iik7DQogICAgZXhpdCgxKTsNCiAgfQ0KICBzdHJuY3B5KGlkLCBidWZmZXIg
KyAxLCAob2Zmc2V0IC0gYnVmZmVyIC0gMSkpOw0KICBpZFtvZmZzZXQgLSBi
dWZmZXJdID0gJ1wwJzsNCg0KICBvZmZzZXQrKzsgLyogbm93IHBvaW50cyB0
byBiZWdpbm5pbmcgb2YgZGVzYyAqLyAgDQogIGRlc2MgPSAoY2hhciAqKSBj
YWxsb2Moc3RybGVuKGJ1ZmZlcikgLSAob2Zmc2V0IC0gYnVmZmVyKSwgc2l6
ZW9mKGNoYXIpKTsNCiAgaWYoZGVzYyA9PSBOVUxMKSB7DQogICAgZnByaW50
ZihzdGRlcnIsICJDb3VsZG4ndCBjYWxsb2MgbWVtb3J5IGZvciBkZXNjIVxu
Iik7DQogICAgZXhpdCgxKTsNCiAgfQ0KICBzdHJuY3B5KGRlc2MsIG9mZnNl
dCwgc3RybGVuKGJ1ZmZlcikgLSAob2Zmc2V0IC0gYnVmZmVyKSAtIDEpOw0K
ICBkZXNjW3N0cmxlbihidWZmZXIpIC0gKG9mZnNldCAtIGJ1ZmZlcikgLSAx
XSA9ICdcMCc7DQoNCiAgZm9yKGkgPSAwIDsgaSA8IDIzIDsgaSsrKSB7DQog
ICAgcmVzY291bnRbaV0gPSAwOw0KICB9DQoNCiAgd2hpbGUoZmdldHMoYnVm
ZmVyLCBzaXplb2YoYnVmZmVyKSwgZnApICE9IE5VTEwgJiYgYnVmZmVyWzBd
ICE9ICc+Jykgew0KICAgIGZvcihpID0gMCA7IGkgPCAyMyA7IGkrKykgew0K
ICAgICAgd2hpbGUgKChqID0gc3RyY2hyKGJ1ZmZlciwgYWxwaGFbaV0pKSAh
PSBOVUxMKSB7DQoJcmVzY291bnRbaV0rKzsNCgkqaiA9ICcgJzsgLyogd2lw
ZSBvdXQgdGhhdCBwb3NpdGlvbiBpbiBidWZmZXIgKi8NCiAgICAgIH0NCiAg
ICB9DQogIH0NCg0KICAvKiBzYXZlIGJlZ2lubmluZyBvZiBuZXh0IHJlY29y
ZCwgaWYgaXQgZXhpc3RzICovDQogIGlmKGJ1ZmZlciAhPSBOVUxMKSB7DQog
ICAgc3RybmNweShzYXZlZF9idWZmZXIsIGJ1ZmZlciwgc2l6ZW9mKHNhdmVk
X2J1ZmZlcikpOw0KICB9IGVsc2Ugew0KICAgIHNhdmVkX2J1ZmZlclswXSA9
ICdcMCc7DQogIH0NCg0KICBzZXEgPSAoc3RydWN0IHNlcV9zdHIgKikgY2Fs
bG9jKDEsIHNpemVvZihzdHJ1Y3Qgc2VxX3N0cikpOw0KICBpZihzZXEgPT0g
TlVMTCkgew0KICAgIGZwcmludGYoc3RkZXJyLCAiQ291bGRuJ3QgY2FsbG9j
IHNlcSBzdHJ1Y3R1cmUuXG4iKTsNCiAgICBleGl0KDEpOw0KICB9DQoNCiAg
c2VxLT5pZCA9IGlkOw0KICBzZXEtPmRlc2MgPSBkZXNjOw0KDQogIGZvcihp
ID0gMCA7IGkgPCAyMyA7IGkrKykgew0KICAgIHNlcS0+cmVzY291bnRbaV0g
PSByZXNjb3VudFtpXTsNCiAgICBsZW5ndGggKz0gcmVzY291bnRbaV07DQog
IH0NCg0KICBzZXEtPmxlbmd0aCA9IGxlbmd0aDsNCg0KICByZXR1cm4gc2Vx
Ow0KfQ0KDQpmbG9hdCBjYWxjX3BJKHN0cnVjdCBzZXFfc3RyICpzZXEpIHsN
Cg0KICBkb3VibGUgKipib3hlczsNCiAgZG91YmxlICpjb2VmZnM7DQogIGRv
dWJsZSBwSTsNCg0KICBpbnQgbnJlcywgbnBvczsNCiAgZG91YmxlICpwS2Fz
Ow0KICBpbnQgYWFwb3NbM10gPSB7IDgsIDExLCAyIH07IC8qIEgsIEsgJiBO
ICovDQogIGludCBhYW5ldXRbNF0gPSB7IDMsIDYsIDQsIDE4IH07IC8qIEQs
IEUsIEMgJiBZICovDQogIGludCAqY291bnRzOw0KDQogIGludCBpLCBqOw0K
DQogIG5yZXMgPSBucG9zID0gMTsgLyogYWxsIHByb3RlaW5zIGhhdmUgTkg0
KyBhbWlubyB0ZXJtaW51cyAqLw0KICBmb3IoaSA9IDAgOyBpIDwgMyA7IGkr
KykNCiAgICBpZihzZXEtPnJlc2NvdW50W2FhcG9zW2ldXSA+IDApIHsNCiAg
ICAgIG5wb3MrKzsgbnJlcysrOw0KICAgIH0NCg0KICBucmVzKys7IC8qIGFs
bCBwcm90ZWlucyBoYXZlIENPT0ggY2FyYm94eSB0ZXJtaW51cyAqLw0KICBm
b3IoaSA9IDAgOyBpIDwgNCA7IGkrKykNCiAgICBpZihzZXEtPnJlc2NvdW50
W2FhbmV1dFtpXV0gPiAwKQ0KICAgICAgbnJlcysrOw0KDQogIGNvdW50cyA9
IChpbnQgKikgY2FsbG9jKG5yZXMsIHNpemVvZihpbnQpKTsNCiAgaWYoY291
bnRzID09IE5VTEwpIHsNCiAgICBmcHJpbnRmKHN0ZGVyciwgIkNvdWxkbid0
IGNhbGxvYyBjb3VudHNcbiIpOw0KICAgIGV4aXQoMSk7DQogIH0NCg0KICBw
S2FzID0gKGRvdWJsZSAqKSBjYWxsb2MobnJlcywgc2l6ZW9mKGRvdWJsZSkp
Ow0KICBpZihwS2FzID09IE5VTEwpIHsNCiAgICBmcHJpbnRmKHN0ZGVyciwg
IkNvdWxkbid0IGNhbGxvYyBwS2FzXG4iKTsNCiAgICBleGl0KDEpOw0KICB9
DQoNCiAgY291bnRzWzBdID0gMTsNCiAgcEthc1swXSA9IHN0b2NrX3BLYXNb
MF07DQoNCiAgY291bnRzW25wb3NdID0gMTsgLyogdGhlIENPT0ggcG9zaXRp
b24gKi8NCiAgcEthc1tucG9zXSA9IHN0b2NrX3BLYXNbNF07DQoNCiAgaiA9
IDE7DQogIGZvcihpID0gMCA7IGkgPCAzIDsgaSsrKSB7DQogICAgaWYoc2Vx
LT5yZXNjb3VudFthYXBvc1tpXV0gPiAwKSB7DQogICAgICBjb3VudHNbal0g
PSBzZXEtPnJlc2NvdW50W2FhcG9zW2ldXTsNCiAgICAgIHBLYXNbal0gPSBz
dG9ja19wS2FzW2kgKyAxXTsNCiAgICAgIGorKzsNCiAgICB9DQogIH0NCg0K
ICBqKys7IC8qIHdlJ3ZlIGFscmVhZHkgZmlsbGVkIG91dCB0aGUgQ09PSCBz
cG90ICovDQogIGZvcihpID0gMCA7IGkgPCA0IDsgaSsrKSB7DQogICAgaWYo
c2VxLT5yZXNjb3VudFthYW5ldXRbaV1dID4gMCkgew0KICAgICAgY291bnRz
W2pdID0gc2VxLT5yZXNjb3VudFthYW5ldXRbaV1dOw0KICAgICAgcEthc1tq
XSA9IHN0b2NrX3BLYXNbaSArIDVdOw0KICAgICAgaisrOw0KICAgIH0NCiAg
fQ0KDQoNCiAgc2V0dXBfY29lZmYoJmJveGVzLCBucmVzLCBucG9zLCBwS2Fz
KTsNCiAgY2FsY19jb2VmZihib3hlcywgY291bnRzLCAmY29lZmZzLCBucmVz
LCBucG9zKTsNCiAgcEkgPSBzb2x2ZV9jb2VmZihjb2VmZnMsIG5yZXMpOw0K
DQogIGlmKHBJID09IC0xLjApIHsNCiAgICAvKiAgICBmb3IoaSA9IDAgOyBp
IDwgbnJlcyA7IGkrKykgew0KICAgICAgZnByaW50ZihzdGRlcnIsICIlZFx0
IiwgY291bnRzW2ldKTsNCiAgICB9DQogICAgZnByaW50ZihzdGRlcnIsICJc
biIpOw0KICAgICovDQogIH0NCg0KICBmcmVlKGJveGVzWzBdKTsNCiAgZnJl
ZShib3hlcyk7DQogIGZyZWUoY29lZmZzKTsNCg0KICBmcmVlKGNvdW50cyk7
DQogIGZyZWUocEthcyk7DQoNCiAgcmV0dXJuIChmbG9hdCkgcEk7DQp9DQoN
CnZvaWQgc2V0dXBfY29lZmYoZG91YmxlICoqKmJveGVzLCBpbnQgbnJlcywg
aW50IG5wb3MsIGRvdWJsZSAqcEthcykgew0KDQogIGRvdWJsZSAqKm15Ym94
ZXMsIHZhbDsNCiAgaW50IGksIGosIGNvdW50LCBuY29tYjsNCiAgaW50ICpw
b3M7DQoNCiAgcG9zID0gKGludCAqKSBjYWxsb2MobnJlcywgc2l6ZW9mKGlu
dCkpOw0KICBpZihwb3MgPT0gTlVMTCkgew0KICAgIGZwcmludGYoc3RkZXJy
LCAiRXJyb3I6IGNvdWxkbid0IGNhbGxvYyBwb3MgYXJyYXlcbiIpOw0KICAg
IGV4aXQoMSk7DQogIH0NCg0KICAvKiBjb252ZXJ0IHBLYSdzIGludG8gSydz
ICovDQogIGZvcihpID0gMCA7IGkgPCBucmVzIDsgaSsrKSB7DQogICAgcEth
c1tpXSA9IHBvdygxMC4wLCAtcEthc1tpXSk7DQogIH0NCg0KICAvKiBhbGxv
Y2F0ZSB0aGUgYm94ZXMgMi1EIGFycmF5IHRoZSBmYW5jeSB3YXkgKi8NCiAg
bXlib3hlcyA9IChkb3VibGUgKiopIGNhbGxvYyhucmVzLCBzaXplb2YoZG91
YmxlICopKTsNCiAgaWYobXlib3hlcyA9PSBOVUxMKSB7DQogICAgZnByaW50
ZihzdGRlcnIsICJFcnJvcjogY291bGRuJ3QgY2FsbG9jIG15Ym94ZXMgYXJy
YXkgb2YgZG91Ymxlcy5cbiIpOw0KICAgIGV4aXQoMSk7DQogIH0NCg0KICBt
eWJveGVzWzBdID0gKGRvdWJsZSAqKSBjYWxsb2MobnJlcyAqIChucmVzICsg
MSksIHNpemVvZihkb3VibGUpKTsNCiAgaWYobXlib3hlc1swXSA9PSBOVUxM
KSB7DQogICAgZnByaW50ZihzdGRlcnIsICJFcnJvcjogY291bGRuJ3QgY2Fs
bG9jIG15Ym94ZXMgYXJyYXkgb2YgZG91Ymxlcy5cbiIpOw0KICAgIGV4aXQo
MSk7DQogIH0NCg0KICBmb3IoaiA9IDAgOyBqIDwgbnJlcyA7IGorKykgeyAN
CiAgICBteWJveGVzW2pdID0gbXlib3hlc1swXSArIChqICogKG5yZXMgKyAx
KSk7DQogIH0NCg0KICAvKiBkb25lIGJlaW5nIGZhbmN5IHdpdGggYWxsb2Nh
dGlvbiAqLw0KDQogIC8qIGZpcnN0LCBjYWxjdWxhdGUgYWxsIHBvc3NpYmxl
IGNvbWJpbmF0aW9ucyBvZiBLJ3MgYW5kIHRoZWlyIHByb2R1Y3RzICovDQog
IC8qIEhhdmluZyBkb25lIHNvLCBhZGQgdGhlbSB0byB0aGUgYXBwcm9wcmlh
dGUgYm94ZXMgKi8NCiAgZm9yKGkgPSAwLCBuY29tYiA9IDEgPDwgbnJlczsg
aSA8IG5jb21iIDsgaSsrKSB7DQogICAgdmFsID0gMS4wOw0KICAgIGNvdW50
ID0gMDsNCiAgICBmb3IoaiA9IDAgOyBqIDwgbnJlcyA7IGorKykgew0KICAg
ICAgcG9zW2pdID0gMDsNCiAgICAgIGlmICggaSAmICgxIDw8IGopICkgeyAv
KiBkb2VzIHRoaXMgSyBwYXJ0aWNpcGF0ZSBpbiB0aGlzIGNvbWJpbmF0aW9u
PyAqLw0KCXZhbCAqPSBwS2FzW2pdOw0KCXBvc1tqXSA9IDE7DQoJY291bnQr
KzsNCiAgICAgIH0NCiAgICB9DQoNCiAgICBmb3IoaiA9IDAgOyBqIDwgbnJl
cyA7IGorKykgew0KICAgICAgaWYgKCAoaiA8IG5wb3MgJiYgIXBvc1tqXSkg
fHwgKGogPj0gbnBvcyAmJiBwb3Nbal0pICkgew0KCW15Ym94ZXNbal1bbnJl
cyAtIGNvdW50XSArPSB2YWw7DQogICAgICB9DQogICAgfQ0KICB9DQoNCiAg
ZnJlZShwb3MpOw0KDQogICpib3hlcyA9IG15Ym94ZXM7DQp9DQoNCnZvaWQg
Y2FsY19jb2VmZihkb3VibGUgKipib3hlcywgaW50ICpjb3VudHMsIGRvdWJs
ZSAqKmNvZWZmcywgaW50IG5yZXMsIGludCBucG9zKSB7DQoNCiAgaW50IGks
IGo7DQogIGRvdWJsZSAqbXljb2VmZnM7DQoNCiAgbXljb2VmZnMgPSAoZG91
YmxlICopIGNhbGxvYyhucmVzICsgMSwgc2l6ZW9mKGRvdWJsZSkpOw0KICBp
ZihteWNvZWZmcyA9PSBOVUxMKSB7DQogICAgZnByaW50ZihzdGRlcnIsICJD
b3VsZG4ndCBjYWxsb2MgbXljb2VmZnNcbiIpOw0KICAgIGV4aXQoMSk7DQog
IH0NCg0KICBmb3IoaiA9IDAgOyBqIDw9IG5yZXMgOyBqKyspIHsNCiAgICBt
eWNvZWZmc1tqXSA9IDAuMDsNCiAgICBmb3IoaSA9IDAgOyBpIDwgbnJlcyA7
IGkrKykgew0KICAgICAgaWYoaSA8IG5wb3MpIHsNCglteWNvZWZmc1tqXSAr
PSAoZG91YmxlKSBjb3VudHNbaV0gKiBib3hlc1tpXVtqXTsNCiAgICAgIH0g
ZWxzZSB7DQoJbXljb2VmZnNbal0gLT0gKGRvdWJsZSkgY291bnRzW2ldICog
Ym94ZXNbaV1bal07DQogICAgICB9DQogICAgfQ0KICB9DQoNCiAgKmNvZWZm
cyA9IG15Y29lZmZzOw0KfQ0KDQpkb3VibGUgc29sdmVfY29lZmYoZG91Ymxl
ICpjb2VmZiwgaW50IG5yZXMpIHsNCg0KICBpbnQgaywgbTsNCiAgaW50IGl0
YWN0LCBxLCBpdG1heCA9IDEwMDsNCiAgZG91YmxlIHgsIHgxLCBkeCwgdSwg
ZiwgZjEsIHQxLCB0MiwgZGVyOw0KICBkb3VibGUgdG9sciA9IDFlLTEwOw0K
DQogIG0gPSBucmVzOw0KDQogIHdoaWxlICggbSA+IDEgKSB7DQogICAgaXRh
Y3QgPSAwOw0KICAgIHggPSAwOw0KICAgIGR4ID0gMC4xOw0KDQogICAgdSA9
IGNhbGNfcG9seSh4LCBjb2VmZiwgbSk7DQogICAgZiA9IGZhYnModSk7DQoN
CiAgICAvKiBtZXRob2Qgb2Ygc3RlZXBlc3QgZGVzY2VudCAqLw0KICAgIHdo
aWxlICggZmFicyhkeCkgPiB0b2xyICYmIGl0YWN0IDw9IGl0bWF4ICkgew0K
ICAgICAgeDEgPSB4Ow0KICAgICAgZjEgPSBmOw0KDQogICAgICBkZXIgPSBj
YWxjX2Rlcih4LCBjb2VmZiwgbSk7DQoNCiAgICAgIGlmICggZGVyICE9IDAu
MCApIHsNCglkeCA9IC0gdSAvIGRlcjsNCiAgICAgIH0gZWxzZSB7DQoJZHgg
Lz0gNDsNCiAgICAgIH0NCg0KICAgICAgLyogdGhpcyBpcyBhbiBvZGQgZG8t
d2hpbGUgbG9vcCB0aGF0IEkndmUgbXVuZ2VkLg0KCSBpdCdzIG9ubHkgc3Vw
cG9zZWQgdG8gaGFwcGVuIG9uY2UsIGJ1dCB3aWxsIGhhcHBlbg0KCSBtb3Jl
IGlmIHRoZSBmdW5jdGlvbiBpbmNyZWFzZXMgcmF0aGVyIHRoYW4gZGVjcmVh
c2VzICovDQogICAgICBmb3IgKCBxID0gMDsNCgkgICAgZmFicyhkeCkgPiB0
b2xyICYmIGYgPj0gZjEgJiYgcSA8IDIwIDsNCgkgICAgcSsrLCBkeCAvPSA0
KXsNCgl4ID0geDEgKyBkeDsNCgl1ID0gY2FsY19wb2x5KHgsIGNvZWZmLCBt
KTsNCglmID0gZmFicyh1KTsNCiAgICAgIH0NCiAgICAgIGl0YWN0Kys7DQog
ICAgfQ0KDQogICAgaWYocSA9PSAyMCB8fCBmYWJzKGR4KSA+IHRvbHIpIHsN
CiAgICAgIGZwcmludGYoc3RkZXJyLCAiQ2Fubm90IHNvbHZlIHBvbHlub21p
YWxcblE6ICVkXHRkeDogJWdcbiIsIHEsIGR4KTsNCiAgICAgIHJldHVybigt
Mi4wKTsNCiAgICB9DQoNCiAgICAvKg0KICAgIGZwcmludGYoc3RkZXJyLCAi
cm9vdCBmb3VuZDogJWdcbiIsIHgpOw0KICAgICovDQoNCiAgICBpZih4ID4g
MCkgeyAvKiBmb3VuZCBvbmUgcG9zaXRpdmUgcm9vdCEgKi8NCiAgICAgIHJl
dHVybigtbG9nMTAoeCkpOw0KICAgIH0NCg0KICAgIC8qIHJlZHVjZSBwb2x5
bm9taWFsIGJ5IHN5bnRoZXRpYyBkaXZpc2lvbiAqLw0KICAgIHQxID0gY29l
ZmZbbV07DQogICAgY29lZmZbbV0gPSAwOw0KDQogICAgZm9yKGsgPSBtLTEg
OyBrID49IDAgOyBrLS0pIHsNCiAgICAgIHQyID0gY29lZmZba107DQogICAg
ICBjb2VmZltrXSA9IHQxICsgeCAqIGNvZWZmW2srMV07DQogICAgICB0MSA9
IHQyOw0KICAgIH0NCg0KICAgIG0tLTsNCiAgfQ0KDQogIC8qIHNvbHZlIGxh
c3QgcG9zc2libGUgcm9vdCBhbGdlYnJhaWNhbGx5ICovDQogIHggPSAtIGNv
ZWZmWzBdIC8gY29lZmZbMV07DQoNCiAgaWYoeCA+IDApIHsNCiAgICByZXR1
cm4oLWxvZzEwKHgpKTsNCiAgfSBlbHNlIHsNCiAgICAvKiAgICBmcHJpbnRm
KHN0ZGVyciwgIk5vIHBvc2l0aXZlIHJvb3RzIGZvciBwb2x5bm9taWFsIVxu
Iik7ICovDQogICAgcmV0dXJuKC0xLjApOw0KICB9DQp9DQoNCmRvdWJsZSBj
YWxjX3BvbHkoZG91YmxlIHgsIGRvdWJsZSAqY29lZmYsIGludCBtKSB7DQoJ
DQogIGludCBrOw0KICBkb3VibGUgdSA9IDAuMDsNCgkNCiAgZm9yKGsgPSBt
IDsgayA+IDAgOyBrLS0pIHsNCiAgICB1ICs9IGNvZWZmW2tdOw0KICAgIHUg
Kj0geDsNCiAgfQ0KICB1ICs9IGNvZWZmWzBdOw0KDQogIHJldHVybih1KTsN
Cn0NCg0KZG91YmxlIGNhbGNfZGVyKGRvdWJsZSB4LCBkb3VibGUgKmNvZWZm
LCBpbnQgbSkgew0KDQogIGludCBrOw0KICBkb3VibGUgZGVyID0gMC4wOw0K
DQogIGZvcihrID0gbSA7IGsgPiAxIDsgay0tKSB7DQogICAgZGVyICs9IGsg
KiBjb2VmZltrXTsNCiAgICBkZXIgKj0geDsNCiAgfQ0KICBkZXIgKz0gY29l
ZmZbMV07DQoNCiAgcmV0dXJuKGRlcik7DQp9DQoNCmludCBjYWxjX01XKHN0
cnVjdCBzZXFfc3RyICpzZXEpIHsNCg0KICBmbG9hdCBNVyA9IDAuMDsNCiAg
aW50IGk7DQoNCiAgZm9yKGkgPSAwIDsgaSA8IDIzIDsgaSsrKSB7DQogICAg
TVcgKz0gKGZsb2F0KSBzZXEtPnJlc2NvdW50W2ldICogYWFtYXNzW2ldOw0K
ICB9DQoNCiAgcmV0dXJuIChpbnQpIE1XICsgMTY7IC8qICsgb25lIEgyMCAq
Lw0KDQp9DQoNCnZvaWQgc2F2ZV9zZXEoc3RydWN0IHNlcV9zdHIgKnNlcSkg
ew0KDQogIGlmKCsrbnNlcSA+IG5zYXZlZCkgeyAvKiBuZWVkIHRvIGFsbG9j
YXRlIG1vcmUgc2VxIHN0cnVjdHMgKi8NCiAgICBzYXZlZF9zZXFzID0gKHN0
cnVjdCBzZXFfc3RyICoqKSByZWFsbG9jKHNhdmVkX3NlcXMsIChuc2F2ZWQg
KyAxMDApICogc2l6ZW9mKHN0cnVjdCBzZXFfc3RyICopKTsNCiAgICBpZihz
YXZlZF9zZXFzID09IE5VTEwpIHsNCiAgICAgIGZwcmludGYoc3RkZXJyLCAi
Q291bGRuJ3QgcmVhbGxvYyBzYXZlZF9zZXFzXG4iKTsNCiAgICAgIGV4aXQo
MSk7DQogICAgfQ0KICAgIG5zYXZlZCArPSAxMDA7DQogIH0NCg0KICBzYXZl
ZF9zZXFzW25zZXEtMV0gPSBzZXE7DQp9DQoNCnZvaWQgZHVtcF9zZXEoRklM
RSAqZnAsIHN0cnVjdCBzZXFfc3RyICpzZXEpIHsNCg0KICBpbnQgaTsNCg0K
ICBmcHJpbnRmKGZwLCAiJXNcdCVkXHQlLjNnXHQlZCIsIHNlcS0+aWQsIHNl
cS0+bGVuZ3RoLCBzZXEtPnBJLCBzZXEtPk1XKTsNCg0KICBmb3IoaSA9IDAg
OyBpIDwgMjMgOyBpKyspIHsNCiAgICBmcHJpbnRmKGZwLCAiICVkIiwgc2Vx
LT5yZXNjb3VudFtpXSk7DQogIH0NCiAgZnByaW50ZihmcCwgIlxuIik7DQoN
CiAgZnJlZShzZXEtPmlkKTsNCiAgZnJlZShzZXEtPmRlc2MpOw0KICBmcmVl
KHNlcSk7DQp9DQo=
---2138111441-92958057-970587499=:75456--