若手研究者インターナショナル・トレーニング・プログラム(ITP)
バイオインフォマティクスとシステムズバイオロジーの国際連携教育研究プログラム 報告書

Name：Yuki Narita
Title：Approximate Algorithm for Finding Elementary Modes of Metabolic Networks via Low-distortion
Embeddings
Institute：Mathematical Bioinformatics Lab., Bioinformatics Center, Kyoto University
Partner institute：AG Mathematics in Life Science, FB Mathematik und Informatik, Freie Universität Berlin
Duration：4. Jun. 2012 - 31. August. 2012
Report：With the support of ITP, I have stayed and studied at FB Mathematik und Informatik, Freie
Universität Berlin for three months in 2012 summer. During the stay the climate was relatively
colder than usual and the weather was rapidly changing, however, it was a very comfortable staythat quite a few people in Berlin are English-speaking and the whole city is fulfilled with artistic
atmosphere, including musicians, painters and various kinds of pop-artists.
The host research group, AG Mathematics in Life Science (Prof. Alexander Bockmayr’s group)
belongs to CSB (Computational Systems Biology) project Berlin, and therefore I have attended theweekly meetings of prof. Bockmayr’s group together with some other CSB seminars including
topics in recent experimental biology, such as RNA science. Especially, prof. Bockmayr advisedme that prof. Edda Klipp (Theoretical Biophysics, Institute for Biology, Humboldt-Universität
Berlin) and some of her graduate students are strongly and taking on a project on studying the useof information theory in biophysics, which is closely related to my previous research interest, and I
was permitted to participate in the weekly seminars of prof. Klipp’s group. As well as in prof.
Bockmayr’s group, some members in prof. Edda Klipp’s group including the people working on
information theory have finished their undergraduate or diploma studies in mathematics and so it
was a nice opportunity to share our interests in theoretical biology.

(Left) Konzerthaus Berlin and Gendarmenmarkt. One of the most famous views among Berlin people.
(Right) “The π-Buiding”, the building of the department of mathematics, Freie Universität Berlin. The circularproportion (3.14159…) is printed on the wall.

若手研究者インターナショナル・トレーニング・プログラム(ITP)
バイオインフォマティクスとシステムズバイオロジーの国際連携教育研究プログラム 報告書

Research Report.
Recent advances in molecular biology have revealed and enabled comprehensive studies on
various kinds of biological networks such as metabolic networks, gene regulation networks andprotein-protein interaction networks [1]. Among them, flux balance of the metabolic networks arewell studied and understood from theoretical viewpoints that the mathematical models of theirproperties are well-formulated by linear equalities and inequalities [2]:Let S be a stoichiometric matrix. The flux cone of S is defined as
C={v∈Rn: S·v = 0, vi ≥0 for all i },and e∈C is call an elementary mode if there exists no vector v∈C s.t. supp(v)⊂supp(e).
Recently, some members in prof. Bockmayr’s group proposed an algorithm to enumerate theelementary modes [3]; however, it was a hard task for execution in that the required computational
step grows exponentially according to the number of reactions included in the network.
During the stay, I have worked with Dr. Laszlo David (research associate of prof. Bockmayrgroup) and Aljoscha Palinkas (Ph.D. candidate) on the topic. First we have reviewed the basic
notions and mathematical formulations of the key concepts, as well as some notions in highdimension geometry. Thereafter we discussed the possibility to establish an approximate algorithm
for speeding up the enumeration of elementary modes: Let S (∈Rn×m) and C as above. We can see
S as a collection of n row (or m column) m-(n-, resp.)dimensional vectors, and by
Johnson-Lindenstrauss flattening lemma [4], there exists a good embedding of these points intologn-(m-)dimensional subspace with small distortion. Then denoting the embedded matrix by S′,
we have conjectured that the geometry of resulting cone C′ should be distorted within the order oflogn. While the proof for the estimation is not completed yet, the whole method give us animprovement in studying elementary modes.

(Left) A nice piece of joke on the door of our office, laughing at logical leaps, often found in mathematical
proofs: “I think you should be more explicit here in step two.”-“Then a miracle occurs…” .
(Right) From the left; Aljoscha Palinkas, Laszlo David, Yuki Narita discussing in the seminar room.

若手研究者インターナショナル・トレーニング・プログラム(ITP)
バイオインフォマティクスとシステムズバイオロジーの国際連携教育研究プログラム 報告書

References.
[1] KEGG: Kyoto Encyclopedia of Genes and Genomes, http://www.kegg.jp/[2] Sayed-Amir Marasi, Laszlo David and Alexander Bockmayr: On flux coupling analysis ofmetabolic subsystems, Journal of Theoretical Biology, 302 (2012) 62-69[3] Sayed-Amir Marasi, Laszlo David and Alexander Bockmayr: Analysis of Metabolic
Subnetworks by Flux Cone Projections, Algorithms for Molecular Biology, 2012, 7:17
[4] Jiří Matoušek: Lectures on Discrete Geometry (Chapter 14-15), Springer, 2002

Home parties involving CSB members and some Japanese people studying in Berlin as working holidays.

Acknowledgement.
Here I want to express my gratitude to prof. Akutsu and prof. Mamitsuka (Bioinformatics center,Kyoto university) for allowing me a great opportunity to have such a nice experience, and prof.
Bockmayr (FB Mathematik und Informatik, Freie Universität Berlin) for kindly hosting me. Also,
I want to thank nice coworkers, Laszlo David and Aljoscha Palinkas for kind daily discussions andnice coffee breaks, over interesting and useful mathematical talks.