Sztöchiometriai egyenletrendszerek minimális számú aktív változót tartalmazó megoldásainak meghatározása a P-gráf módszertan alkalmazásával

Bevezetés Reakcióút-szintézis feladat Lineáris algebrai és P-gráf megközelítés Integrált megoldó módszer Összefoglalás

Sztöchiometriai egyenletrendszerek minimális számú aktív változót tartalmazó megoldásainak meghatározása a P-gráf módszertan alkalmazásával

Kalauz K., Bertók B., Friedler F., L. T. Fan* Pannon Egyetem, M¶szaki Informatikai Kar, Számítástudomány Alkalmazása Tanszék *Kansas State University Manhattan, Department of Chemical Engineering, KS 66506, U.S.A. XXVII. MAGYAR OPERÁCIÓKUTATÁSI KONFERENCIA Balatonöszöd, 2007. Június 7-9.

Kalauz K., Bertók B., Friedler F., L. T. Fan

Gráfelméleti és lineáris algebrai módszerek integrálása


Bevezetés Célkit¶zéseink Tartalomjegyzék

Bevezetés

Inhomogén lineáris egyenletrendszer elemi megoldásainak tekintjük a változók egy olyan halmazát, ahol a halmazban nem szerepl® változók nulla értéke mellett, még az egyenletrendszer megoldható, de a halmazból bármely elemet elhagyva az egyenletrendszer már nem oldható meg úgy, hogy csak a halmazbeli változók nem nulla érték¶ek

Egy lineáris egyenletrendszer elemi megoldásainak kimerít® leszámlálása számos gyakorlati feladat megoldásának kulcsa. Ilyen például egy kémiai vagy biokémiai reakció mechanizmusát felépít® reakcióutak azonosítása





Célkit¶zéseink

Reakcióút azonosítás feladatának megoldására kidolgozott módszerek feltérképezése A különböz® megközelítések er®sségeit együttesen kihasználó megoldó módszer kidolgozása és implementálása nyílt forrású szoftverek felhasználásával





Tartalomjegyzék

1

Reakcióút-szintézis feladat

2

Lineáris algebrai és P-gráf megközelítés

3

Integrált megoldó módszer

4

Összefoglalás




Reakcióút azonosítás (RPI) Reakcióút-szintézis feladat Rakcióút-szintézis nehézségei Szakirodalmi áttekintés

Reakcióút azonosítás (RPI)

A reakcióút jelzi a reakció mechanizmusát Ered® reakció reakcióútjának vagy mechanizmusának meghatározása két szakaszból áll

az összes lehetséges mechanizmus azonosítása a pontos reakcióút vagy mechanizmus kiválasztása





Reakcióút-szintézis feladat

Minden reakcióút elemi reakciók lépéseinek hálózata A reakcióút szintézis feladata, adott sztöchiometriai együtthatókkal, az

elemi reakció lépések minden olyan ered® reakciót erdményezi

együttm¶ködését meghatározni, ami az





Rakcióút-szintézis nehézségei

A reakcióút szintézis feladat minden független megoldását (Direct Pathways) pontosan egyszer kell generálni A reagensekt®l a végtermékekig vezet® reakcióút felépítésében a valószín¶ elemi reakciók bármelyike részt vehet 1 2 3

el®refelé, fordított irányban vagy egyik irányban sem

n valószín¶ elemi reakció esetén a kombinációk száma: 3

n

−1

A nehézség forrása a válaszok kombinatorikus robbanása és a hatékony számítógépes megvalósítás bonyolultsága





Szakirodalmi áttekintés

Lineáris algebrai megközelítés

A feladat megfogalmazása Happel és Sellers, 1983. Peth®, 1990.

Független utak generálása Happel és Sellers, 1983.

Konvex elemzés S. Schuster et al., 1999. C. H. Schilling et al., 2000.

Szalkai, 1991. Jedlovszky, Bertók és Friedler, 2001.





Szakirodalmi áttekintés

P-gráf megközelítés

P-gráf módszertan

F. Friedler és L. T. Fan, '70-es évek P-gráf megközelítés a katalitikus reakcióutak azonosítására

L. T. Fan, B. Bertok és F. Friedler, Computers and Chemistry, 26, 265-292 (2002). P-gráf megközelítés a biokémiai reakcióuatak azonosítására

H. Seo, D.-Y. Lee, S. Park, L. T. Fan, S. Shae, B. Bertok és F. Friedler, Biotechnology Letters, 23, 1551-1557 (2001).




Reakcióutak lineáris algebrai leírása A példa lineáris algebrai megoldása Motiváció Reakcióutak P-gráf leírása Kombinatorikusan megengedett megoldásai a példának

Reakcióutak lineáris algebrai leírása Jelölések (Jedlovszky, Bertók és Friedler, 2001.) e: elemi reakció vektora E: ered® reakció vektora

Ered® reakció: C4 H10

↔ C4 H8 + H2

Elemi reakciók: 1 C4 H10

+ ` ↔ C4 H8 ` + H2

2 C4 H8 `

↔ C4 H8 + `

3 C4 H8 `

↔ C4 H6 ` + H2

4 C4 H6 `

↔ C4 H6 + `

5 C4 H10

+ ` + C4 H6 ` ↔ 2C4 H8 `





Reakcióutak lineáris algebrai leírása

Bázis transzformációk segítségével keressük az

Ax

=

E

lineáris

egyenletrendszer elemi megoldásait

Keressük az elemi reakcióvektorok (e-knek) mindazon lineáris

E

kombinációit, amelyek az ered® reakciót ( -t) eredményezik





A példa lineáris algebrai megoldása

E=

1

e1

1

+

0

0 0 0 0

e2

Reakcióút:

(1 →)C4 H10 + ` → C4 H8 ` + H2 (2 →)C4 H8 ` → C4 H8 + `

C4 H10 → C4 H8 + H2





Motiváció

Több száz lehetséges bázis transzformációs sorrend 2 független megoldás Cél:minden megoldást jól meghatározott módon, pontosan egyszer generálni





Reakcióutak P-gráf leírása

L. T. Fan, B. Bertók és F. Friedler, 2002. P-gráf: O-típusú csúcsok: elemi reakció lépések M-típusú csúcsok: részecskék

Példa Elemi reakciók:

(1 →)C4 H10 + ` → C4 H8 ` + H2 (2 →)C4 H8 ` → C4 H8 + ` Ered® reakció: C4 H10

→ C4 H8 + H2





Lehetséges reakcióutak kombinatorikus tulajdonságai L. T. Fan, B. Bertók és F. Friedler, 2002.

(T1) Az ered® reakció által el®állított minden kémiai részecske (végtermék) szerepel a gráfban. (T2) Az ered® reakció által felhasznált minden kémiai részecske (kiindulási reagens) szerepel a gráfban. (T3) Minden O-típusú csúcs a reakcióút-szintézis feladatban deniált elemi reakciólépést reprezentál. (T4) Minden kémiai vagy aktív átmeneti részecskét reprezentáló csúcsból vezet a gráfban út legalább egy végtermékig. (T5) Ha egy M-típusú csúcs része a gráfnak, akkor vezet hozzá él legalább egy O-típusú csúcsból vagy vezet bel®le él legalább egy O-típusú csúcsba. (T6) Ha egy M-típusú csúcsba nem vezet él a gráfban, akkor kiindulási reagenst reprezentál. (T7) Egy elemi reakció el®re és fordított lépése közül legfeljebb az egyik szerepel a gráfban. Kalauz K., Bertók B., Friedler F., L. T. Fan




PNS algoritmusok

P-gráf leírásra épül® algoritmusok (L. T. Fan, B. Bertók, és F. Friedler, 2002.)

kizárja azon elemi reakciókat, melyek egyetlen kombinatorikusan lehetséges struktúrában sem szerepelhetnek RPIMSG algoritmus:

az összes kombinatorikusan lehetséges struktúrát pontosan egyszer generálja RPISSG algoritmus:





A keresési tér sz¶kítése





Az RPISSG algoritmus lépései Példa

bután (C4 H10 ) dehidrogénezése buténné (C4 H8 )

Kombinatorikusan lehetséges reakcióutak generálódnak a 2, 3, 5, 6, 7 lépésben Kalauz K., Bertók B., Friedler F., L. T. Fan




Kombinatorikusan megengedett megoldásai a példának




Integrált megoldó módszer Az RPISSG alg. döntési fája a lin. algebrai modell alapján A példa megoldásai Megvalósítás Az eljárás gyakorlati alkalmazhatósága

Az integrált megoldó módszer

P-gráf alapján keresési fa a lineáris algebrai lépések irányítására: Döntések jól meghatározott sorozata Döntés arról, hogy bevesz vagy kizár egy elemi reakciólépést a felépítés alatt álló struktúrából Egy elemi reakciólépés bevitele a gráfba feltételezi, hogy a megfelel® vektor bevihet® a bázisba nem-nulla értékkel Egy elemi reakciólépés kivétele a hálózatból feltételezi, hogy a megfelel® vektor

nem szerepel a bázisban nulla együtthatóval szerepel a bázisban





Az integráció bemutatása Példa






Az integráció bemutatása

A

(2 →)

lépést bevonjuk a struktúrába a


C4 H8

el®állítására




Az integráció bemutatása A

(2 →)

lépést bevonjuk a struktúrába a


C4 H8

el®állítására




Az RPISSG alg. döntési fája a lin. algebrai modell alapján Példa


2, 5 lépésben független reakcióutak generálódnak 3, 6, 7 lépésben ellentmondás a lineáris algebrai modell alapján Kalauz K., Bertók B., Friedler F., L. T. Fan




A példa megoldásai A példa egyik lehetséges megoldása:


e1 + e2




A példa megoldásai A példa másik lehetséges megoldása:


e2 + e3 + e5




Megvalósítás

A bemutatott algoritmust implementáltuk ANSI ISO C++ nyelven Sablon alapú osztályokkal fordítási id®ben ellen®rizzük a strukturális leképezéseket tartalmazó kifejezések szemantikai helyességét Singleton pattern tervezési mintát használunk a reakciók és részecskék egyértelm¶ sorszámozásához A feladat betöltéséhez és az eredmények kimentéséhez XML formátumot alkalmazunk, melyhez a XERCES program könyvtárat használjuk





Az eljárás gyakorlati alkalmazhatósága

Lineáris algebrai modell: több száz lehetséges bázis transzformáció sorrend

Az RPISSG algoritmus alkalmazásával: 5 bázis transzformáció sorrend

Mindkét független megoldást pontosan egyszer eredményezi az integrált módszer




Összefoglalás További információk a P-gráf módszertanról

Összefoglalás

Bemutattam a reakcióút szintézis P-gráf leírásra és lineáris algebrai modellre épül® megoldásait

A két módszert integráltuk

Olyan módszert dolgoztunk ki, mely a

P-gráf

leírásra épül®

algoritmusoknak köszönhet®en a feladat minden

lineáris algebrai

eszközökkel generálható független megoldását pontosan egyszer eredményezi




Összefoglalás További információk a P-gráf módszertanról

További információk a P-gráf módszertanról

www.P-graph.com [email protected] [email protected]



Sztöchiometriai egyenletrendszerek minimális számú aktív változót tartalmazó megoldásainak meghatározása a P-gráf módszertan alkalmazásával

Recommend Documents