~~Speaker: Alon Raveh, 
M.Sc. student under the supervision of Prof. Michael Margaliot

Wednesday, October 28th, 2015 at 15:30
Room 011, Kitot Bldg., Faculty of Engineering

A Model for Competition for Ribosomes in the Cell

Abstract

A single mammalian cell includes an order of 10^4−10^5 mRNA molecules and as many as 10^5−10^6 ribosomes. Large-scale simultaneous mRNA translation and the resulting competition for the available ribosomes has important implications to the cell’s functioning and evolution.  Developing a better understanding of the intricate correlations between these simultaneous processes, rather than focusing on the translation of a single isolated transcript, should help in gaining a better understanding of mRNA translation regulation and the way elongation rates affect organismal fitness.  A model of simultaneous translation is specifically important when dealing with highly expressed genes, as these consume more resources. In addition, such a model can lead to more accurate predictions that are needed in the interconnection of translational modules in synthetic biology.

We develop and analyze a general model for large-scale simultaneous mRNA translation and competition for ribosomes. This is based on combining several ribosome flow models (RFMs) interconnected via a pool of free ribosomes. We prove that the compound system always converges to a steady-state and that it always entrains or phase locks to periodically time-varying transition rates in any of the mRNA molecules. We use this model to explore the interactions between the various mRNA molecules and ribosomes at steady-state. We show that increasing the length of an mRNA molecule decreases the production rate of all the mRNAs. Increasing any of the codon translation rates in a specific mRNA molecule yields a local effect: an increase in the translation rate of this mRNA, and also a global effect: the translation rates in the other mRNA molecules all increase or all decrease.

These results suggest that the effect of codon decoding rates of endogenous and heterologous mRNAs on protein production is more complicated than previously thought.

Dominating induced matchings in graphs containing no long claw

Alain Hertz
Polytechnique Montréal, Canada

(Coauthors : V. Lozin, B. Ries, V. Zamaraev, D. de Werra)

Abstract:

An induced matching M in a graph G is dominating if every edge not in M shares exactly one vertex with an edge in M. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph G contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw-free graphs.

We study this problem for graphs containing no long claw, i.e. no induced subgraph obtained from the claw by subdividing each of its edges exactly once. To solve the problem in this class, we reduce it to the following question: given a graph G and a subset of its vertices, does G contain a matching saturating all vertices of the subset? We show that this question can be answered in polynomial time, thus providing a polynomial-time algorithm to solve the dominating induced matching problem for graphs containing no long claw.

Bio :

Holder of a diploma in Mathematical Engineering, Alain Hertz obtained a Ph.D in operations research at the École Polytechnqiue Fédérale de Lausanne. Since 2001, he is professor at the department of mathematics and industrial engineering at the École Polytechnique in Montréal. He is also member of the multi disciplinary GERAD research group that includes nearly sixty researchers and experts in operations research and discrete mathematics.

He is the author of about 180 scientific publications His main research domains are combinatorial optimization, graph theory, algorithmics, and the development of decision aid systems for scheduling and distribution problems.

ההרצאה תתקיים ביום שלישי 20.10.15, בשעה 14:00 בחדר 206, בנין וולפסון הנדסה, הפקולטה להנדסה, אוניברסיטת תל-אביב.