A stochastic local search algorithm for phylogenetic reconstruction

Francesca Tria

The reconstruction of the phylogenetic history belongs to a general class of inverse problems whose relevance is now well established in many different disciplines ranging from biology to linguistics and social sciences. In a generic inverse problem one is given with a set of data and one has to infer the most likely dynamical evolution processes that presumably produced the given data set. The problem that all the algorithms for phylogenetic reconstruction have to face is that of the deviations from a purely phylogenetic process. By phylogenetic process we mean a process on which information (i.e. genetic material) is transmitted from parents to offsprings. In many cases, however, a main source of evolution is horizontal transfer, that is exchange of information (i.e. of genetic material) within the same generation. The similarity of genomic sequences at a given instant does not, in this cases, reflect the evolutive distance in terms of closer common ancestor. Further, multiple changes on a given site, due to high rate of mutations, is also a confounding factor for a correct phylogenetic inference. Thus, despite the fact that the phylogenetic reconstruction is not a novel topic, many of the relevant problems, related to the lack of additivity in the recontructed distances between leaves, present an open challenge. We proposed a new stochastic local search algorithm (SLS) based on two properties of additive distances, the four points condition and the Pauplin formula (which I will discuss in the talk) and we studied its ability in presence of high level of deviation of additivity, due to both horizontal transfer and back-mutation processes.

Compressed sensing

Marco Righero

Compressed sensing, also known as compressive sensing, compressive sampling and sparse sampling, is a technique for acquiring and reconstructing a signal exploiting the prior knowledge that it is sparse or compressible -- that is, it contains many coefficients close to or equal to zero -- when represented in the appropriate base. (This is the same insight used in many forms of lossy compression.) Starting with taking a limited (possibly randomized) amount of samples in a basis different from the basis in which the signal is known to be sparse, the reconstruction of the original signal is then seen as an optimization problem. Some simple examples -- including a one-pixel camera -- will be presented to illustrate the basic ideas and some possible developments will be proposed. To have a rough idea, the talk will be based on 'An introduction to compressive sampling', IEEE Signal Processing Magazine, 21, by Emmanuel J. Candès and Michael B. Wakin. A valuable source of information is here.

Biological networks reconstruction algorithms and their benchmarking

Roberto Rodio

We review the state-of-the-art strategies to reconstruct the topology of biological networks. The algorithms we review try to infer unknown regulatory relationships exploiting the partial knowledge of the network. Most of them work on "local" pattern recognition problems and require to solve an optimization problem for each vertex. An important issue about this class of algorithms is how to validate and compare their results. For this purpose, some new synthetic benchmarks allow to run in-silico experiments with sufficient biological realism.

[1] Haynes, Brent: Benchmarking regulatory network reconstruction with GRENDEL, 2007
[2] Faith, Hayete et al.: Large scale mapping and validation of Escherichia coli transcriptional regulation from a compendium of expression profiles, 2007
[3] Vert: Reconstruction of biological networks by supervised machine learning approaches, 2008
[4] Mordelet, Vert: SIRENE: Supervised inference of regulatory networks

Phylogenetic supertrees

Blaise Li

One of the ultimate goals of phylogeny is to assemble the whole tree of life. It is however difficult to find characters allowing comparisons at such a large scale, and to gather data for all species for these few universal characters. A more reasonable approch is to combine the results of phylogenetic studies made at various scales. This problem (combining trees made on various sets of species into a single big tree) is called the supertree problem. During the last ten years, several kinds of methods have been developed for constructing supertrees. I will describe the principles of some of these methods. Then, I will present a few ideas derived from these methods, that I would like to apply to reliability analyses (using a set of independent phylogenetic trees to detect the most reliable relationships among species).

Systems approaches and algorithms for discovery of combinatorial therapies

Valentina Lanza

Effective therapy of complex diseases requires control of highly non-linear complex networks that remain incompletely characterized. In particular, drug intervention can be seen as control of signaling in cellular networks. Identification of control parameters presents an extreme challenge due to the combinatorial explosion of control possibilities in combination therapy and to the incomplete knowledge of the systems biology of cells. In this review we describe the main current and proposed approaches to the design of combinatorial therapies, including the empirical methods used now by clinicians and alternative approaches suggested recently by several authors. New approaches for designing combinations arising from systems biology are described.

[1] J.D.Feala, J.Cortes, P.M.Duxbury, C.Piermarocchi, A.D.McCulloch, G.Paternostro, Systems approaches and algorithms for discovery of combinatorial therapies, arXiv:0903.0662, 2009
[2] S. Nelander, W. Wang, B. Nilsson, Q. She, C. Pratilas, N. Rosen, P. Gennemark, and C. Sander, Models from experiments: combinatorial drug perturbations of cancer cells. Mol.Syst. Biol., 4:216, 2008
[3] D. Calzolari, S. Bruschi, L. Coquin, J. Schofield, J.D. Feala, J.C. Reed, A.D. McCulloch, and G. Paternostro, Search algorithms as a framework for the optimization of drug combinations. PLoS Comput Biol, 4(12): e1000249, 2008. .

Add to calendar
Syndicate content