text:
# 18.6: Gibbs Free Energy

## Introduction

In the previous section we derived Gibbs Free Energy from the Second Law of Thermodynamics and showed that a system will spontaneously react in the direction that lowers its Free Energy We showed that processes that reduced enthalpy (exothermic processes) or increased the entropy of the system contributed to spontaneity. We also showed that for a system at equilibrium, the change in free energy is zero.

Summary of Free Energy Equations

\begin{align} G &=H-TS \\[5pt] \Delta G &= \Delta H -T\Delta S \\[5pt] (\Delta G^o & = \Delta H^o - T\Delta S^o) \\[5pt] \Delta G & = \Delta G^o + RT\ln Q \\[5pt] \Delta G^o & = -RT\ln K \\[5pt] K &=e^{\frac{-\Delta G^o}{RT}} \end{align}

## Standard State Calculations

#### Equilibrium Constant at 298 K

Free energy values at standard state can be used to calculate equilibrium constants (using eq. 18.5.6).

Exercise $$\PageIndex{1}$$

Using the table of standard state molar thermodynamic values (Table T.1), calculate the equilibrium constant K for the following reaction at 25o C.

$2Ag_2O(s) \leftrightharpoons 4Ag(s) + O_2(g) \nonumber$

$K =e^{\frac{-\Delta G^o}{RT}} \nonumber$

Noting, $$\Delta G^o_{rxn}= 4(0) + 0 -[2(-11.2kJ/mol)]=22.4kJ$$, gives:

$\large{K=e^{\frac{-22.4kJ/mol}{\left (0.008314 \frac{kJ}{mol \cdot K} \right )298K}} \nonumber =1.19\times 10^{-4}}$

What does the above problem tell us about the stability of silver in the presence of oxygen? The positive $$\Delta G^o$$ tells us that at standard state conditions silver oxidide will not spontaneously form pure silver and oxygen. On the other hand, it says that silver will spontaneously react with oxygen and form the oxidized silver oxide. That is, silver sulfide is stable, and silver is thermodynamically reactive with oxygen. How fast the reaction occurs depends on the kinetics and specifically, the activation energy, but silver will spontaneously form silver oxide.

#### Equilibrium Constant at other Temperatures

In this class we will consider $$\Delta H_{rxn}$$ and $$\Delta S_{rxn}$$ to be independent of temperature. This is not a completely legitimate assumption, and is in fact really bad if the system undergoes a phase change.

Exercise $$\PageIndex{2}$$

Consider the reaction

$N_2(g) +3H_2(g) \leftrightharpoons 2NH_3(g) \nonumber$

Using Table T1, calculate $$\Delta H^o_{rxn}$$ and $$\Delta S^o_{rxn}$$ at 25 ºC.

$\Delta H^o_{rxn} = 2(-45.9\frac{kJ}{mol}) -[1(0) +3(0)]=-91.8 \frac{kJ}{mol} \nonumber$.

$\Delta S^o_{rxn} = 2(0.1928 \frac{kJ}{mol \cdot K}) -[1(0.1916\frac{kJ}{mol \cdot K}) +3(0.1307)\frac{kJ}{mol \cdot K}]=-0.1981 \frac{kJ}{mol \cdot K} \nonumber$.

from the previous exercise we get $$\Delta H^o_{rxn}=-91.8 \frac{kJ}{mol}$$ and $$\Delta S^o_{rxn}=-198.1 \frac{J}{mol \cdot K}$$

Let's compare these values to the values at 800 K and 1300 K

Temperature (K) $$\Delta H^o_{rxn}\frac{kJ}{mol}$$ $$\Delta S^o_{rxn}\frac{J}{mol \cdot K}$$
298 -91.8 -198.1
800 -107.4 -225.4
1300 -112.4 -228.0

Exercise $$\PageIndex{3}$$

Calculate $$\Delta G^o_{rxn}$$ and K at each temperature using thermodynamic values at that temperature.

$\Delta G^o_{rxn}(298K) = -91.8\frac{kJ}{mol} -(298K)(-0.1981)\frac{kJ}{mol \cdot K} = -32.8 \frac{kJ}{mol} \nonumber \\ \large{ K_{eq}= e^{\frac {-\Delta G^o_{rxn}}{RT}} = e^{\frac {-(-32.8 \frac{kJ}{mol})}{(0.008314\frac{kJ}{mol \cdot K} )298K}} =5.62\times 10^5 }$

$\Delta G^o_{rxn}(800K) = -107.4\frac{kJ}{mol} -(800K)(-0.2254)\frac{kJ}{mol \cdot K} = 72.92 \frac{kJ}{mol} \nonumber \\ \large{ K_{eq}= e^{\frac {-\Delta G^o_{rxn}}{RT}} = e^{\frac {-(72.92 \frac{kJ}{mol})}{(0.008314\frac{kJ}{mol \cdot K} )800.K}} =2\times 10^{-5} }$

$\Delta G^o_{rxn}(1300K) = -112.4\frac{kJ}{mol} -(1300K)(-0.2280)\frac{kJ}{mol \cdot K} = 184.0 \frac{kJ}{mol} \nonumber \\ \large{ K_{eq}= e^{\frac {-\Delta G^o_{rxn}}{RT}} = e^{\frac {-(184.0 \frac{kJ}{mol})}{(0.008314\frac{kJ}{mol \cdot K} )1300.K}} =4.0\times 10^{-8} }$

So from the above, we see that we have the following K values,

• $$K(298K) = 5.62\times 10^5$$
• $$K(800K) = 2\times 10^{-5}$$
• $$K(1300K) = 4.0\times 10^{-8} .$$

This shows us several things. This is an enthalpy driven reaction and at low temperature it is favorable. But it is entropy impeded, and at high temperature becomes unfavorable.

Often times we do not have thermodynamic values outside of 298 K, and can still approximate $$\Delta G^o_{rxn}$$ by using the values of $$\Delta H^o_{rxn}$$ and $$\Delta S^o_{rxn}$$ at 25 ºC, that is, we assume standard entropy and enthalpy are constant. Lets calculate Keq at 800 K and 1300 K using the $$\Delta H^o_{rxn}$$ and $$\Delta S^o_{rxn}$$ at 25 ºC (assuming they are constant over the temperature ranges).

Exercise $$\PageIndex{4}$$

Calculate Keq at 800 K and 1300 K using the $$\Delta H^o_{rxn}$$ and $$\Delta S^o_{rxn}$$ at 25 ºC .

$\Delta G^o_{rxn}(800K) = -91.8\frac{kJ}{mol} -(800K)(-0.1981)\frac{kJ}{mol \cdot K} = 66.7 \frac{kJ}{mol} \nonumber \\ \large{ K_{eq}= e^{\frac {-\Delta G^o_{rxn}}{RT}} = e^{\frac {-(66.7 \frac{kJ}{mol})}{(0.008314\frac{kJ}{mol \cdot K} )800.K}} =4.4\times 10^{-5} }$

$\Delta G^o_{rxn}(1300K) = -91.8\frac{kJ}{mol} -(1300K)(-0.1981)\frac{kJ}{mol \cdot K} = 165.7 \frac{kJ}{mol} \nonumber \\ \large{ K_{eq}= e^{\frac {-\Delta G^o_{rxn}}{RT}} = e^{\frac {-(165.7 \frac{kJ}{mol})}{(0.008314\frac{kJ}{mol \cdot K} )1300.K}} =2.2\times 10^{-7} }$

Note that now we get

• $$K(800\,K) = 4 \times 10^{-5}$$ (it is really $$2 \times 10^{-5}$$)
• $$K(1300\,K) = 2.2 \times 10^{-7}$$ (it is really $$4 \times 10^{-8}$$)

What we see here is that using standard entropy and enthalpy values at 298K gives us reasonably close K values at other temperatures, but the farther away we are from 298, the worse the results. Thus it is common to use the values of $$\Delta H^o_{rxn}$$ and $$\Delta S^o_{rxn}$$ at 25 degree C for other temperatures to calculate the free energy at the other temperature $\Delta G^o_{rxn} =\Delta H^o_{rxn} -T \Delta S^o_{rxn} \nonumber$.

## Two Meanings of Spontaneous

You will observe that there are two commonly used meanings for spontaneous. In the first context you are asking if a reaction is product favored, in the sense that once equilibrium is achieved, the reactants have converted to products. The second context is that of describing an actual mixture of reactants and products and asking in what direction (if any) will a reaction proceed, that is, is the system Reactant Loaded or Product Loaded.

### Product/Reactant Favored Reactions

Here you are looking at the values of $$\Delta G^o_{rxn}$$ and Keq, and asking do the equilibria favor reactants or products

Product Favored Reactions
$$\Delta G^o_{rxn}$$<<0 (it is very negative) and $$K \gg 1$$ (it is a very large number).

Reactant Favored Reactions
$$\Delta G^o_{rxn}$$ >>0 (it is very large and positive) and $$K \ll 1$$ (it is a very small fraction).

Exercise $$\PageIndex{5}$$

Does silver chloride dissolve in water?

Silver chloride has a very small K, Ksp = 1.8 x 10-10 .

$\Delta G^o_{rxn}=-RTlnK=-(0.008314\frac{kJ}{mol \cdot K} )298Kln(1.8\times 10^{-10}) = 55.6kJ/mol$

Note, from Exercise 5 that for silver chloride, $$\Delta G^o$$=55.6kJ/mol, which is a very large number and corresponds to a very small equilibrium constant, Ksp = 1.8 x 10-10, and so we would say that silver chloride does not dissolve.

Here you are given concentrations of reactants and products and need to determine if $$\Delta G$$ is greater than, less than, or equal to Zero.

$\Delta G_{rxn} = \Delta G^o_{rxn} +RT \ln Q$

Where Q is the reaction quotient. If

$$\Delta G_{rxn} < 0$$ - Forward reaction is spontaneous
$$\Delta G_{rxn} >0$$ - Reverse reaction is spontaneous
$$\Delta G_{rxn} = 0$$ - System is at Equilibrium

This meaning of spontaneous is different than the above meaning, and not stating whether an equilibrium is product or reactant favored, but if a reaction will occur. In the next example we will see that at very dilute (nanomolar) concentrations, even an insoluble salt will dissolve.

Exercise $$\PageIndex{6}$$

Will 100 nmoles of silver chloride dissolve in one liter of water? (Can you make a 100. nM solution of AgCl?)

As we are given concentrations we need to look at $$\Delta G_{rxn}$$ and not $$\Delta G^o_{rxn}$$, although we can use $$\Delta G^o_{rxn}$$ from the problem above that asked if silver chloride was a soluble salt.

$\Delta G_{rxn} = \Delta G^o_{rxn} +RTlnQ$

note, 100nM =100(10-9M) =1\times 10-7M, and Q=x2.

\begin{align}\Delta G_{rxn} &= 55.6kJ/mol -(0.008314\frac{kJ}{mol \cdot K} )298Kln(1.0\times 10^{-7})^2 \nonumber \\ & = 55.6kJ/mol + (-79.9kJ/mol) \nonumber \\ &=-24.3kJ/mol\end{align}

What you notice in the above is that there are two terms contributing to $$\Delta G$$, that which describes the equilibrium ($$\Delta G^o$$), and that which describes the "loading" of the system, RTlnQ. As silver chloride is a very insoluble salt the first term is 55.6 kJ and positive. If the reaction quotient (Q) is a fraction (meaning few products and many reactants) its log is negative and it contributes towards spontaneity. If it is more negative than the first term is positive, the system is reactant loaded and will spontaneously make products. In the above exercise, the second term was -79.9kJ/mol and so the net $$\Delta G$$ is -23.4kJ/mol and the reaction proceeds, with the silver chloride spontaneously dissolving, even though we would call it an insoluble salt.

## Driving NonSpontaneous Reactions

In General Chemistry 1, section 5.7.1, Hess's Law we noted that if we coupled two reactions the energy is additive, and this principle also holds for other state functions like Gibbs Free Energy. That is, Free Energies of Reactions are additive. What this means is that a nonspontaneous process ($$\Delta G > O$$) can become spontaneous if it is coupled to a second spontaneous process ($$\Delta G < O$$), if the second process is more negative than the first process is positive.

Consider the decomposition of chalcocite (Copper(i)sulfide).

Figure$$\PageIndex{1}$$: Chalcocite is a copper ore of Cu2S, (image from Wikimedia)

Let's say we want to extract the copper from Chalcocite. The first question is, is it stable?

$Cu_2S(s) \rightarrow 2Cu(s) + S(s)$

From the table of standard molar Free Energies of formation (Table T1) the enthalpy of formation of chalcocite is -82.6kJ/mol.

$2Cu(s) + S(s) \rightarrow 2Cu_2S(s) \; \; \; \Delta G^o_f= -82.6kJ/mol$

Noting in the above equation that copper and silver are in their standard states ($$\Delta G^o_f = O$$), means the free energy change for the first reaction (18.6.15) is the negative of its $$\Delta G^o_f$$, or 86.2kJ. (Note the last value is written in units of kJ and not kJ/mol, as it is related to eq.18.6.15, and the per mole is implicit (per one mole of chalcocite consumed, and per two moles of copper and one mole sulfur produced). This tells us that chalcocite is stable and will not spontaneously form copper and sulfur.

Since we want to extract copper, we could find a reaction that consumes the sulfur, a byproduct, and whose (\Delta G^o_f <-82.6kJ\)) . From (Table T1) we see that $$\Delta G^o_f (\text{sulfur dioxide})$$ is -300kJ/mol

$S(s) +O_2(g) \rightarrow SO_2(g) \; \; \; \Delta G^o_f= -300.1kJ/mol$

equation 1: Cu2S(s) --> 2Cu(s) + S(s) ΔH1 =+82.6kJ (non spontaneous)
equation 2: S(s) + O2 --> SO2 ΔH2 = -300.1kJ (spontaneous)

equation 3: Cu2S(s) + O2 --> 2Cu(s) + SO2 ΔH3 = 82.6kJ +(-300.1kJ)=-217.5kJ (spontaneous)

Now that we have a thermodynamically feasible process the next step is to find the reaction conditions (temperature, catalysts...) that would allow it to proceed at a viable rate.

## Enthalpically vs. Entropically Driving Reactions

Some textbooks and teachers say that the free energy, and thus the spontaneity of a reaction, depends on both the enthalpy and entropy changes of a reaction, and they sometimes even refer to reactions as "energy driven" or "entropy driven" depending on whether ΔH or the TΔS term dominates. This is technically correct but misleading because it disguises the important fact that ΔStotal, which this equation expresses in an indirect way, is the only criterion of spontaneous change.

Consider the following possible states for two different types of molecules with some attractive force:

There would appear to be greater entropy on the left (state 1) than on the right (state 2). Thus the entropic change for the reaction as written (i.e. going to the right) would be (-) in magnitude, and the energetic contribution to the free energy change would be (+) (i.e. unfavorable) for the reaction as written.

In going to the right, there is an attractive force and the molecules adjacent to each other have a lower energy state (heat energy, q, is liberated). To go to the left, we have to overcome this attractive force (input heat energy) and the left direction is unfavorable with regard to heat energy q. The change in enthalpy is (-) in going to the right (q released), and this enthalpy change is negative (-) in going to the right (and (+) in going to the left). This reaction as written, is therefore, enthalpically favorable and entropically unfavorable. Hence, it is enthalpically driven.

From Table 18.5.1, it would appear that we might be able to get the reaction to go to the right at low temperatures (lower temperature would minimize the energetic contribution of the entropic change). Looking at the same process from an opposite direction:

This reaction as written, is entropically favorable, and enthalpically unfavorable. It is entropically driven. From Table 18.5.1 , it would appear that we might be able to get the reaction to go to the right at high temperatures (high temperature would increase the energetic contribution of the entropic change).

## Relationship between ΔG and Work

Gibbs Free Energy is the maximum available energy to do non PV work like mechanical or electrical work. Gibbs Free Energy is also very important to understand bioenergetics, and a foundation topic that will be used in upper level chemistry courses. Let's show how $$\Delta G = W_{max}$$ for systems at constant pressure and temperature.

$\Delta G = \Delta H -T\Delta S \; \; \text{at constant temperature}$
$\Delta H = \Delta U + P \Delta V \; \; \text{at constant pressure}$

Substituting the definition of enthalpy (18.6.19) into the definition of Free Energy (18.6.18) gives

$\Delta G = \Delta U + P \Delta V -T\Delta S \; \; \text{at constant temperature and pressure}$

From the First Law of Thermodynamics we know

$\Delta U = Q + W$
substituting the First Law Internal Energy expression into the free energy equation gives

$\Delta G = Q + W + P \Delta V -T\Delta S \; \; \text{at constant temperature and pressure}$

For maximum work, a process must be reversible, and knowing the definition of entropy $$\Delta S = \frac{Q_{rev}}{T}\ \; gives \; Q_{rev}=T\Delta S$$, and substitution into the above eq. gives

\begin{align}\Delta G & = \cancel{T\Delta S} + W_{rev} + P \Delta V \cancel{-T\Delta S} \; \; \text{at constant temperature and pressure} \\ \Delta G & = W_{rev} + P\Delta V \end{align}

The reversible work (Wrev) may be of expansion (Wrev,exp) or non expansion (Wrev, nonexp), and noting from section 5.1.4.1, $$W_{rev,exp}=-P\Delta V$$ so $$W_{rev}= W_{rev,nonexp}-P\Delta V$$. Substituting for reversible work gives:

\begin{align}\Delta G & = W_{rev} + P\Delta V \\ &= W_{rev,nonexp}\cancel{-P\Delta V} + \cancel{P\Delta V} \\ & = W_{rev,nonexp} \end{align}

This is often written as $\Delta G = W_{max}, \text{the maximum amount of energy available to do work (at constant T & P)}$

One of the major challenges facing engineers is to maximize the efficiency of converting stored energy to useful work or converting one form of energy to another. As indicated in Table $$\PageIndex{2}$$, the efficiencies of various energy-converting devices vary widely. For example, an internal combustion engine typically uses only 25%–30% of the energy stored in the hydrocarbon fuel to perform work; the rest of the stored energy is released in an unusable form as heat. In contrast, gas–electric hybrid engines, now used in several models of automobiles, deliver approximately 50% greater fuel efficiency. A large electrical generator is highly efficient (approximately 99%) in converting mechanical to electrical energy, but a typical incandescent light bulb is one of the least efficient devices known (only approximately 5% of the electrical energy is converted to light). In contrast, a mammalian liver cell is a relatively efficient machine and can use fuels such as glucose with an efficiency of 30%–50%.

Table $$\PageIndex{2}$$: Approximate Thermodynamic Efficiencies of Various Devices
Device Energy Conversion Approximate Efficiency (%)
large electrical generator mechanical → electrical 99
chemical battery chemical → electrical 90
home furnace chemical → heat 65
small electric tool electrical → mechanical 60
space shuttle engine chemical → mechanical 50
mammalian liver cell chemical → chemical 30–50
spinach cell light → chemical 30
internal combustion engine chemical → mechanical 25–30
fluorescent light electrical → light 20
solar cell light → electricity 10
incandescent light bulb electricity → light 5
yeast cell chemical → chemical 2–4


text: Sequence Analysis I, Sun., January 21, 20:30-21:30 Multiple Alignment by Sequence Annealing Ariel S. Schwartz, EECS Computer Science Division, UC Berkeley, USA Lior Pachter, Department of Mathematics, UC Berkeley, USA Abstract: Motivation: We introduce a novel approach to multiple alignment that is based on an algorithm for rapidly checking whether single matches are consistent with a partial multiple alignment. This leads to a sequence annealing algorithm, which is an incremental method for building multiple sequence alignments one match at a time. Our approach improves significantly on the standard progressive alignment approach to multiple alignment. Results: The sequence annealing algorithm performs well on benchmark test sets of protein sequences. It is not only sensitive, but also specific, drastically reducing the number of incorrectly aligned residues in comparison to other programs. The method allows for adjustment of the sensitivity/specificity tradeoff, and can be used to reliably identify homologous regions among protein sequences. Availability: An implementation of the sequence annealing algorithm is available at http://bio.math.berkeley.edu/amap/ Tandem Repeats over the Edit Distance Dina Sokol and Justin Tojeira, Brooklyn College of the City University of New York, USA Gary Benson, Boston University, USA Abstract: A tandem repeat in DNA is a sequence of two or more contiguous, approximate copies of a pattern of nucleotides. Tandem repeats occur in the genomes of both eukaryotic and prokaryotic organisms. They are important in numerous fields including disease diagnosis, mapping studies, human identity testing (DNA fingerprinting), sequence homology, and population studies. Although tandem repeats have been used by biologists for many years, there are few tools available for performing an exhaustive search for all tandem repeats in a given sequence. In this paper we describe an efficient algorithm for finding all tandem repeats within a sequence, under the edit distance measure. The contributions of this paper are two-fold: theoretical and practical. We present a precise definition for tandem repeats over the edit distance, and an efficient, deterministic algorithm for finding these repeats. The algorithm has been implemented in C++, and a website for the program is under construction. The use of this tool will assist biologists in discovering new ways that tandem repeats affect both the structure and function of DNA and protein molecules. Molecular Recognition and Computer Aided Drug Design, Mon., January 22, 10:00-11:30 Analysis of Binding Site Similarity, Small-Molecule Similarity and Experimental Binding Profiles in the Human Cytosolic Sulfotransferase Family Rafael J. Najmanovich, European Bioinformatics Institute (EMBL-EBI), UK and Structural Genomics Consortium, University of Toronto, Canada Richard J. Morris and Janet M. Thornton, European Bioinformatics Institute (EMBL-EBI), UK Abdellah Allali-Hassani, Ludmila Dombrovsky and Masoud Vedadi, Structural Genomics Consortium, University of Toronto, Canada Patricia W. Pan, Medical Biophysics Department and Structural Genomics Consortium, University of Toronto, Canada Alexander N. Plotnikov, Physiology Department and Structural Genomics Consortium, University of Toronto, Canada Aled Edwards and Cheryl Arrowsmith, Structural Genomics Consortium and Banting & Best Department of Medical Research, University of Toronto, Canada Abstract: Motivation: In the present work we combine computational analysis and experimental data to explore the extent to which binding site similarities between members of the human cytosolic sulfotransferase family correlate with small-molecule binding profiles. Conversely, from a small-molecule point of view, we explore the extent to which structural similarities between small--molecules correlate to protein binding profiles. Results: The comparison of binding site structural similarities and small-molecule binding profiles shows that proteins with similar small-molecule binding profiles tend to have a higher degree of binding site similarity but the later is not sufficient to predict small-molecule binding patterns, highlighting the difficulty of predicting small-molecule binding patterns from sequence or structure. Likewise, from a small-molecule perspective, small-molecules with similar protein binding profiles tend to be topologically similar but topological similarity is not sufficient to predict their protein binding patterns. These observations have important consequences for function prediction and drug design. Electrostatic Potentials of Proteins in Water: A Structured Continuum Approach Andreas Hildebrandt and Hans-Peter Lenhof, Center for Bioinformatics, Saarland University, Germany Ralf Blossey, Interdisciplinary Research Institute Lille, Germany Sergej Rjasanow, Dept. of Mathematics, Saarland University, Germany Oliver Kohlbacher, Dept. for Simulation of Biological Systems, University Tübingen, Germany Abstract: Electrostatic interactions play a crucial role in many biomolecular processes, including molecular recognition and binding. Biomolecular electrostatics is modulated to a large extent by the water surrounding the molecules. Here, we present a novel approach to the computation of electrostatic potentials which allows the inclusion of water structure into the classical theory of continuum electrostatics. Based on our recent purely differential formulation of nonlocal electrostatics (Hildebrandt et al., Phys. Rev. Lett. {\bf 93} (2004) 108104) we have developed a new algorithm for its efficient numerical solution. The key component of this algorithm is a boundary element solver, having the same computational complexity as established boundary element methods for local continuum electrostatics. This allows, for the first time, the computation of electrostatic potentials and interactions of large biomolecular systems immersed in water including effects of the solvent's structure in a continuum description. We illustrate the applicability of our approach with two examples, the enzymes trypsin and acetylcholinesterase (AChE). The approach is applicable to all problems requiring precise prediction of electrostatic interactions in water, such as protein-ligand and protein-protein docking, folding, and chromatin regulation. Initial results indicate that this approach may shed a new light on biomolecular electrostatics and on aspects of molecular recognition that classical local electrostatics cannot reveal. EBIMed - Text Crunching to Gather Facts for Proteins from Medline Dietrich Rebholz-Schuhmann, Harald Kirsch, Miguel Arregui, Sylvain Gaudan, Mark Riethoven, and Peter Stoehr, European Bioinformatics Institute, UK Abstract: To allow efficient and systematic retrieval of statements from Medline, we have developed EBIMed, a service that combines document retrieval with co-occurrence-based analysis of Medline abstracts. Upon keyword query, EBIMed retrieves the abstracts from EMBL-EBI's installation of Medline and filters for sentences that contain biomedical terminology maintained in public bioinformatics resources. The extracted sentences and terminology are used to generate an overview table on proteins, GO annotations, drugs and species used in the same biological context. All terms in retrieved abstracts and extracted sentences are linked to their entries in biomedical databases. We assessed the quality of the identification of terms and relations in the retrieved sentences. More than 90% of the protein names found indeed represented a protein. According to the analysis of 4 protein/protein pairs from the Wnt pathway we estimated that 37% of the statements containing such a pair mentioned a meaningful interaction and clarified the interaction of Dkk with LRP. We conclude that EBIMed improves access to information where proteins and drugs are involved in the same biological process, e.g. statements with GO annotations of proteins, protein/protein interactions and effects of drugs on proteins. Access: http://www.ebi.ac.uk/Rebholz-srv/ebimed Computational Genomics I, Mon., January 22, 12:00-14:00 Optimization of Probe Coverage for High-Resolution Oligonucleotide aCGH Doron Lipson, Computer Science Dept., Technion, Israel Zohar Yakhini, Agilent Technologies, Israel Yonatan Aumann, Computer Science Dept., Bar-Ilan University, Israel Abstract: Motivation: The resolution at which genomic alterations can be mapped by means of oligonucleotide aCGH (array-based Comparative Genomic Hybridization) is limited by two factors: the availability of high-quality probes for the the target genomic sequence and the array real-estate. Optimization of the probe selection process is required for arrays that are designed to probe specific genomic regions in very high resolution without compromising probe quality constraints. Results: In this paper we describe a well-defined optimization problem associated with the problem of probe selection for high-resolution aCGH arrays. We propose the "whenever possible epsilon-cover" as a formulation that faithfully captures the requirement of probe selection problem, and provide a fast randomized algorithm that solves the optimization problem in O(n log n) time, as well as a deterministic algorithm with the same asymptotic performance. We apply the method in a typical high-definition array design scenario and demonstrate its superiority with respect to alternative approaches. Simultaneous Alignment and Annotation of cis-Regulatory Regions Abha Singh Bais, Steffen Grossmann, and Martin Vingron, Max Planck Institute for Molecular Genetics, Germany Abstract: Motivation: Current methods that annotate conserved transcription factor binding sites in an alignment of two regulatory regions perform the alignment and annotation step separately and combine the results in the end. If the site descriptions are weak or the sequence similarity is low, the local gap structure of the alignment poses a problem in detecting the conserved sites. It is therefore desirable to have an approach that is able to simultaneously consider the alignment as well as possibly matching site locations. Results: With SimAnn we have developed a tool that serves exactly this purpose. By combining the annotation step and the alignment of the two sequences into one algorithm, it detects conserved sites more clearly. It has the additional advantage that all parameters are calculated based on statistical considerations.  This allows for its successful application with any binding site model of interest.  We present the algorithm and the approach for parameter selection and compare its performance with that of other, non-simultaneous methods on both simulated and real data. Availability: A command-line based C++ implementation of SimAnn is available from the authors upon request. Additionally, we provide Perl scripts for calculating the input parameters based on statistical considerations. Genetic Code Symmetry and Efficient Design of GC-Constrained Coding Sequences Matan Gavish, School of Physics, Tel Aviv University, Israel Amnon Peled, Goldyne Savad Gene Therapy Institute, Hadassah, Israel Benny Chor, School of Computer Science, Tel Aviv University, Israel Abstract: Motivation: Cloning of long DNA sequences (40-60 bases) into phage display libraries using PCR is a low efficiency process, in which PCR is used to incorporate a DNA insert, coding for a certain peptide, into the amplified sequence. The PCR efficiency in this process is strongly affected by the distribution of G-C bases in the amplified sequence. As any DNA insert coding for the target peptide may be attempted, there is a flexibility in choosing part of the amplified sequence. Since the number of inserts coding for the same peptide is exponential in the peptide length, a computational problem naturally arises - that of efficiently finding an insert, whose parameters are optimal for PCR cloning. Results: The GC distribution requirements are formulated as a search problem. We developed an efficient, linear time “one pass” algorithm for this problem. Interestingly, our algorithm strongly relies on a novel symmetry, which we discovered in the standard genetic code. Most nonstandard genetic codes examined possess this symmetry as well, yet some do not. We generalize the search problem and consider the case of a nonstandard, or arbitrary, genetic code where this symmetry does not necessary hold. We solve the generalized problem in polynomial, but non-linear, time. Discovering Tightly Regulated and Differentially Expressed Gene Sets in Whole Genome Expression Data Chun Ye and Eleazar Eskin, University of California, San Diego, USA Abstract: Motivation: Recently, a new type of expression data is being collected which aims to measure variation of pathways due to genetic variation. In these datasets, expression profiles are constructed for multiple strains of the same model organism under the same condition. The goal of analyses of this data is to find differences in regulatory patterns due to genetic variation between strains, often without a phenotype of interest in mind. We present a new method based on notions of correlated expression and differential expression to look for significant sets of genes. Results: When we use categorical phenotype information, as in the Alzheimer's and diabetes datasets, our method finds many of the same gene sets as GSEA. But the notion of correlated gene sets allows us to focus our efforts on biological processes subjected to tight regulation. In murine hematopoietic stem cells, we are able to discover significant gene sets independent of a phenotype of interest. Some of these gene sets are associated with several blood related phenotypes. Networks, Pathways and Systems, Mon., January 22, 15:30-18:00 Biological Network Comparison using Graphlet Degree Distribution Natasa Przulj, Computer Science Department, University of California, Irvine, USA Abstract: Motivation: Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics, such as the degree distribution, clustering coefficient, diameter, and relative graphlet frequency distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in all of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar. Results: We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes "touching'' k edges, into distributions measuring the number of nodes "touching'' k "graphlets'', where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 "graphlet degree distributions'' of graphlets with 2, 3, 4, and 5 nodes, but it is easily extendible to a greater number of constraints (i.e, graphlets), if necessary, and the extensions are limited only by the available CPU. Furthermore, we show a way to combine the 73 graphlet degree distributions into a network "agreement'' measure which is a number between 0 and 1, where 1 means that networks have identical distributions and 0 means that they are far apart. Based on this new network agreement measure, we show that almost all of the fourteen eukaryotic PPI networks, including human, resulting from various high-throughput experimental techniques, as well as from curated databases, are better modeled by geometric random graphs than by Erdos-Renyi, random scale-free, or Barabasi-Albert scale-free networks. Availability: Software executables are available upon request. Identification of Conserved Protein Complexes Based on a Model of Protein Network Evolution Eitan Hirsh and Roded Sharan, School of Computer Science, Tel Aviv University, Israel Abstract: Motivation: Data on protein-protein interactions are increasing exponentially. To date, large scale protein interaction networks are available for human and most model species. The arising challenge is to organize these networks into models of cellular machinery. As in other biological domains, a comparative approach provides a powerful basis for addressing this challenge. Results: We develop a probabilistic model for protein complexes that are conserved across two species. The model describes the evolution of conserved protein complexes from an ancestral species by protein interaction attachment and detachment and gene duplication events. We apply our model to search for conserved protein complexes within the protein-protein interaction networks of yeast and fly, which are the largest networks in public databases. We detect 150 conserved complexes that match well known complexes in yeast and are coherent in their functional annotations both in yeast and in fly. In comparison to two previous approaches, our model yields higher specificity and sensitivity levels in protein complex detection. Phylogenetic Reconstruction from Non-Genomic Data Jose C. Clemente and Kenji Satou, Japan Advanced Institute of Science and Technology, Japan Gabriel Valiente, Technical University of Catalonia, Spain Abstract: Recent results related to horizontal gene transfer suggest that phylogenetic reconstruction cannot be determined conclusively from sequence data, resulting in a shift from approaches based on polymorphism information in DNA or protein sequence to studies aimed at understanding the evolution of complete biological processes. The increasing amount of available information on metabolic pathways for several species makes it of greater relevance to understand the similarities and differences among such pathways. These similarities can then be used to infer phylogenetic trees not based exclusively in sequence data, therefore avoiding the previously mentioned problems. In this paper, we present a method to assess the structural similarity of metabolic pathways for several organisms. Our algorithms work by using one of three possible enzyme similarity measures (hierarchical, information content, gene ontology), and one of two clustering methods (neighbor-joining, unweighted pair group method with arithmetic mean), to produce a phylogenetic tree both in Newick and graphic format. The web server implementing our algorithms is optimized to answer queries in linear time. The software is available for free public use on a web server, at the contact address. It is available on demand in source code form for research use to educational institutions, non-profit research institutes, government research laboratories, and individuals, for non-exclusive use, without the right of the licensee to further redistribute the source code. Similarities and Differences of Gene Expression in Yeast Stress Conditions Oleg Rokhlenko and Ydo Wexler, Computer Science Dept., Technion, Israel Zohar Yakhini, Agilent Technologies, Israel Abstract: Motivation and Methods: All living organisms and the survival of all cells critically depend on their ability to sense and quickly adapt to changes in the environment and to other stress conditions. We study stress response mechanisms in Saccharomyces cerevisiae by identifying genes that, according to very stringent criteria, have persistent co-expression under a variety of stress conditions. This is enabled through a fast clique search method applied to the intersection of several co-expression graphs calculated over the data of Gasch et al. [3]. This method exploits the topological characteristics of these graphs. Results: We observe cliques in the intersection graphs that are much larger than expected under a null model of changing gene identities for different stress conditions but maintaining the co-expression topology within each one. Persistent cliques are analyzed to identify enriched function as well as enriched regulation by a small number of TFs. These TFs therefore characterize a universal and persistent reaction to stress response. We further demonstrate that the vertices (genes) of many cliques in the intersection graphs are colocalized in the yeast genome, to a degree far beyond the random expectation. Co-localization can hypothetically contribute to a quick co-ordinated response. We propose the use of persistent cliques in further study of properties of co-regulation. Efficient Inference on Phylogenetic Trees Using Poisson Regression Saharon Rosset, IBM T. J. Watson Research Center, USA Abstract: We suggest the use of Poisson regression for time inference and hypothesis testing on a bifurcating Phylogenetic tree with known topology. This method is computationally simple and naturally accommodates variable substitution rates across different sites, without requiring estimation of these rates. We identify the assumptions under which this is a maximum likelihood inference approach and show that in some realistic situations --- in particular, when the probability of repeated mutation within each branch of the tree is small --- these assumptions hold with high probability. Our motivating domain is human mitochondrial DNA trees, and we illustrate our method on a problem of estimating the time to most recent common ancestor of all non-African mtDNA, using publicly available data. We test for molecular clock violations using multiple comparisons, and conclude that the global molecular clock hypothesis cannot be rejected based on this data. Structural Bioinformatics I, Tue., January 23, 10:00-11:30 Vorolign - Fast Structural Alignment Using Voronoi Contacts Fabian Birzele, Jan Erik Gewehr, Gergely Csaba, and Ralf Zimmer, Practical Informatics and Bioinformatics Group, LMU Munich, Germany Abstract: Summary: Vorolign, a fast and flexible structural alignment method for two or more protein structures is introduced. The method aligns protein structures using double dynamic programming and measures the similarity of two residues based on the evolutionary conservation of their corresponding Voronoi-contacts in the protein structure. This similarity function allows to align protein structures even in cases where structural flexibilities exist. Multiple structural alignments are generated from a set of pairwise alignments using a consistency-based, progressive multiple alignment strategy. Results: The performance of Vorolign is evaluated for several different applications of protein structure comparison, including automatic family detection as well as pairwise and multiple structure alignment. Vorolign accurately detects the correct family, superfamily or fold of a protein with respect to the SCOP classification on a set of difficult target structures. A scan against a database of 4358 proteins takes on average 1 minute per target. The performance of Vorolign in calculating pairwise and multiple alignments is found to be comparable to other pairwise and multiple protein structure alignment methods. Availability: Vorolign is freely available for academic users as a Web server at http://www.bio.ifi.lmu.de/Vorolign Prediction and Simulation of Motion in Pairs of Transmembrane Alpha-Helices Angela Enosh, Sarel J. Fleishman, Nir Ben-Tal, and Dan Halperin, Tel Aviv University, Israel Abstract: Motivation: Motion in transmembrane-proteins plays an essential role in a variety of biological phenomena, including signal transduction, transport of metabolites, ligand binding and molecular recognition of hormones and neurotransmitters. Thus, developing an automated method for predicting and simulating motion in this class of proteins should result in an increased level of understanding of their biochemical mechanisms. We have developed an algorithm for predicting and simulating motion in transmembrane (TM) proteins. We used probabilistic motion-planning techniques to sample possible motion paths. For each conformation we computed the buried-surface area between the helices, providing a rudimentary assessment of the free-energy of helix association. Our algorithm considers a wide range of degrees of freedom (dofs) involved in the motion, including external and internal moves. However, in order to handle the vast dimensionality of the problem, we employed some relaxations on these dofs in a way that is unlikely to demolish the native motion that the protein undergoes. Results: Overexpression of the receptor tyrosine kinase (RTK) ErbB2 was implicated in causing a variety of human cancers. Recently, a molecular mechanism for rotation-coupled activation of the receptor was suggested. We applied our algorithm to investigate the TM domain of this protein, and compared our results to this mechanism. Our algorithm yielded several motion pathways and among them a motion similar to the proposed mechanism was ranked first. Our algorithm simulates the motion including all the dofs involved in this process and can automatically produce movies that demonstrate such motions. Rediscovering Secondary Structures as Network Motifs - An Unsupervised Learning Approach Barak Raveh, Ofer Rahat, Ronen Basri, and Gideon Schreiber, Weizmann Institute of Science, Israel Abstract: Motivation: Secondary structures are key descriptors of a protein fold and its topology. In recent years, they facilitated intensive computational tasks for finding structural homologues, fold prediction and protein design. Their popularity stems from an appealing regularity in patterns of geometry and chemistry. However, the definition of secondary structures is of subjective nature. An unsupervised de-novo discovery of these structures would shed light on their nature, and improve the way we use these structures in algorithms of structural bioinformatics. Methods: We developed a new method for unsupervised partitioning of undirected graphs, based on patterns of small recurring network motives. Our input was the network of all H-bonds and covalent interactions of protein backbones. This method can be also used for other biological and non-biological networks. Results: In a fully unsupervised manner, and without assuming any explicit prior knowledge, we were able to rediscover the existence of conventional alpha-helices, parallel beta-sheets, anti-parallel sheets and loops, as well as various non-conventional hybrid structures. The relation between connectivity and crystallographic temperature factors establishes the existence of novel secondary structures. Contact: barak.raveh@weizmann.ac.il Structural Bioinformatics II, Tue., January 23, 12:00-14:00 A Tale of Two Tails: Why are Terminal Residues of Proteins Exposed? Etai Jacob and Ron Unger, Faculty of Life Sciences, Bar Ilan University, Israel Abstract: Motivation: It is widely known that terminal residues of proteins (i.e. the N and C termini) are predominantly located on the surface of proteins and exposed to the solvent. However, there is no good explanation as to the forces driving this phenomenon. The common explanation that terminal resi-dues are charged, and charged residues prefer to be on the surface, can not explain the magnitude of the phenomenon. Here, we survey a large number of proteins from the PDB in order to explore, quantitatively, this phenomenon, and then we use a lattice model to study the mechanisms involved. Results: The location of the termini was examined for 425 small monomeric proteins (50-200 AA) and it was found that the average solvent accessibility of termini residues is 87.1% compared with 49.2% of charged residues and 35.9% of all residues. Using a cutoff of 50% of the maximal possible exposure, 80.3% of the N-terminal and 86.1% of the C-terminal residues are exposed compared to 32% for all residues. In addition, terminal residues are much more distant from the center of mass of their proteins than other residues. Using a 2D lattice, a large population of model proteins was studied on three levels: structural selection of compact structures, thermodynamic selection of conformations with a pronounced energy gap, and kinetic selection of fast folding proteins using Monte-Carlo simulations. Progressively, each selection raises the proportion of proteins with termini on the surface, resulting in similar proportions to those observed for real proteins. A Novel Pattern Recognition Algorithm to Classify Membrane Protein Unfolding Pathways with High-Throughput Single Molecule Force Spectroscopy Annalisa Marsico, Dirk Labudde, Tanuj Sapra, Daniel Muller, and Michael Schroeder, Biotechnologisches Zentrum der TU Dresden, Germany Abstract: Motivation: Misfolding of membrane proteins plays an important role in many human diseases such as retinitis pigmentosa, hereditary deafness, and diabetes insipidus. Little is known about membrane proteins as there are only a very few high-resolution structures. Single molecular force spectroscopy is a novel technique, which measures the force necessary to pull a protein out of a membrane. Such force curves contain valuable information on the protein's structure, conformation, and inter- and intra-molecular forces. High-throughput force spectroscopy experiments generate hundreds of force curves including spurious ones and good curves, which correspond to different unfolding pathways. Manual analysis of these data is a bottleneck and source of inconsistent and subjective annotation. Results: We propose a novel algorithm for the identification of spurious curves and curves representing different unfolding pathways. Our algorithm proceeds in three stages: First, we reduce noise in the curves by applying dimension reduction; second, we align the curves with dynamic programming and compute pairwise distances; third, we cluster the curves based on these distances. We apply our method to a hand curated dataset of 135 force curves of bacteriorhodopsin mutant P50A. Our algorithm achieves a success rate of 81% distinguishing spurious from good curves and a success rate of 76% classifying unfolding pathways. As a result, we discuss five different unfolding pathways of bacteriorhodopsin including three main unfolding events and several minor ones. Finally, we link folding barriers to the degree of conservation of residues. Overall, the algorithm tackles the force spectroscopy bottleneck and leads to more consistent and reproducible results paving the way for high-throughput analysis of structural features of membrane proteins. Using an Alignment of Fragment Strings for Comparing Protein Structures Iddo Friedberg, Tim Harder, Zhanwen Li, and Adam Godzik, Burnham Institute for Medical Research, USA Rachel Kolodny, Columbia University and Howard Hughes Medical Institute, USA Einat Sitbon, Weizmann Institute of Science, Israel Abstract: Motivation: Most methods which are used to compare protein structures use 3D structural information to do so. At the same time, it has been shown that a 1D string representation of local protein structure retains a degree of structural information. This type of representation can be a powerful tool for protein structure comparison and classification, given the arsenal of sequence comparison tools developed by computational biology. However, in order to do so, there is a need to first understand how much information is contained in various possible 1D representations of protein structure. Results: Here we describe the use of a particular structure fragment library, denoted here as KL strings, for the 1D representation of protein structure. Using KL strings, we develop an infrastructure for comparing protein structures with a 1D representation. This study focuses on the added value gained from such a description. We show the new local structure language adds resolution to the traditional three state (helix, strand and coil) secondary structure description, and provides a high degree of accuracy in recognizing structural similarities when used with a pairwise alignment benchmark. The results of this study have immediate applications towards fast structure recognition, and for fold prediction and classification. Supplementary material: http://iddo-friedberg.org/ECCB06-supplement ISIS: Interaction Sites Identified from Sequence Yanay Ofran and Burkhard Rost, Columbia University, USA Abstract: Motivation: Large-scale experiments reveal pairs of inter-acting proteins but leave the residues involved in the inter-actions unknown. These interface residues are essential for understanding the mechanism of interaction and are often desired drug targets. Reliable identification of residues that reside in protein-protein interface typically requires analysis of protein structure. Therefore, for the vast majority of pro-teins, for which there is no high resolution structure, there is no effective way of identifying interface residues. Results: Here, we present a knowledge-based method that identifies interacting residues from sequence. The method is based on a detailed characterization of protein-protein inter-faces in known high-resolution complexes. We use pre-dicted structural features and evolutionary information, combined with the sequence of the protein. Our strongest predictions reached above 90% accuracy in a cross-validation experiment. Our results suggested that despite the significant diversity in the nature of protein-protein interac-tions, they all share common basic principles identifiable even at the sequence level. Sequence Analysis II, Tue., January 23, 15:30-17:30 Incremental Window-Based Protein Sequence Alignment Algorithms Huzefa Rangwala and George Karypis, Department of Computer Science and Engineering, University of Minnesota-Twin Cities, USA Abstract: Motivation: Protein sequence alignment plays a critical role in computational biology as it is an integral part in many analysis tasks designed to solve problems in compartive genomics, structure and function prediction, and homology modeling. Methods: We have developed novel sequence alignment algorithms that compute the alignment between a pair of sequences based on short fixed- or variable-length highscoring subsequences. Our algorithms build the alignments by repeatedly selecting the highest scoring pairs of subsequences and using themto construct small portions of the final alignment. We utilize PSI-BLAST generated sequence profiles and employ a profile-to-profile scoring scheme derived from PICASSO. Results: We evaluated the performance of the computed alignments on two recently published benchmark datasets and compared them against the alignments computed by existing state-of-the-art dynamic programming-based profile-to-profile local and global sequence alignment algorithms. Our results show that the new algorithms achieve alignments that are comparable or better to those achieved by existing algorithms. Moreover, our results also showed that these algorithms can be used to provide better information as to which of the aligned positions are more reliable - a critical piece of information for comparative modeling applications. Designing Patterns for Profile HMM Search Yanni Sun and Jeremy Buhler, Washington University in Saint Louis, USA Abstract: Motivation: Profile HMMs are a powerful tool for modeling conserved motifs in proteins. These models are widely used by search tools to classify new protein sequences into families based on domain architecture. However, the proliferation of known motifs and new proteomic sequence data poses a computational challenges for search, potentially requiring days of CPU time to annotate an organism's proteome. Results: We use PROSITE-like patterns as a filter to speed up the comparison between protein sequence and profile HMM. A set of patterns is designed starting from the HMM, and only sequences matching one of these patterns are compared to the HMM by full dynamic programming. We give an algorithm to design patterns with maximal sensitivity subject to a bound on the false positive rate. Experiments show that our patterns typically retain at least 90% of the sensitivity of the source HMM while accelerating search by an order of magnitude. Simulating Multiplexed SNP Discovery Rates using Base-Specific Cleavage and Mass Spectrometry Sebastian Böcker, Bielefeld University, Germany Abstract: Single Nucleotide Polymorphisms (SNPs) are believed to contribute strongly to the genetic variability in living beings, and SNP and mutation discovery is of great interest in today's Life Sciences. A comparatively new method to discover such polymorphisms is based on base-specific cleavage, where resulting cleavage products are analyzed by mass spectrometry. One particular advantage of this method is the possibility of multiplexing the biochemical reactions, that is, examining multiple genomic regions in parallel. Simulations can help estimating the performance of a method for polymorphism discovery, and allow us to evaluate the influence of method parameters on the discovery rate, and also to investigate whether the method is well-suited for a certain genomic region. We show how to efficiently conduct such simulations for polymorphism discovery using base-specific cleavage and mass spectrometry. Simulating multiplexed polymorphism discovery leads us to the problem of uniformly drawing a multiplex: Given a multiset of natural numbers we want to uniformly draw a subset of fixed cardinadinality so that the elements sum up to some fixed total length. We show how to enumerate multiplex layouts using dynamic programming what allows us to uniformly draw a multiplex. Learning Probabilistic Models of cis-Regulatory Modules that Represent Logical and Spatial Aspects Keith Noto and Mark Craven, University of Wisconsin, Madison, USA Abstract: Motivation: The process of transcription is controlled by systems of factors which bind in a specific arrangement, called a {\em cis-regulatory module} (CRM), in a set of promoter regions. We present a discriminative learning algorithm which simultaneously learns the DNA binding site motifs as well as the logical structure and spatial aspects of a CRM. Results: Our results on yeast data sets show better predictive accuracy than a current state-of-the-art approach on the same data sets. Our results on yeast, fly, and human data sets show that the inclusion of logical and spatial aspects improve the predictive accuracy of our learned models. Availability: Source code will be made available at: http://www.biostat.wisc.edu Contact: noto@cs.wisc.edu Proteomics, Wed., January 24, 10:00-11:30 TOPP - The OpenMS Proteomics Pipeline Oliver Kohlbacher, Nico Pfeifer, and Marc Sturm, Universität Tübingen, Germany Knut Reinert, Clemens Gröpl, and Eva Lange, Freie Universität Berlin, Germany Ole Schulz-Trieglaff, Freie Universität Berlin / Max Planck Research School for Computational Biology, Germany Abstract: Motivation: Experimental techniques in proteomics have seen rapid development over the last few years. Volume and complexity of the data have both been growing at a similar rate. Accordingly, data management and analysis are one of the major challenges in proteomics. Flexible algorithms are required to handle changing experimental setups and to assist in developing and validating new methods. In order to facilitate these studies, it would be desirable to have a flexible 'toolbox' of versatile and user-friendly applications allowing for rapid construction of computational workflows in proteomics. Results: We describe a set of tools for proteomics data analysis -- TOPP, The OpenMS Proteomics Pipeline. TOPP provides a set of computational tools which can be easily combined into analysis pipelines even by non-experts and can be used in proteomics workflows. These applications range from useful utilities (file format conversion, peak picking) over wrapper applications for known applications (e.g. Mascot) to completely new algorithmic techniques for data eduction and data analysis. We anticipate that TOPP will greatly facilitate rapid prototyping of proteomics data evaluation pipelines. As such, we describe the basic concepts and the current abilities of TOPP and illustrate these concepts in the context of two example applications: the identification of peptides from a raw data set through database search and the complex analysis of a standard addition experiment for the absolute quantitation of biomarkers. The latter example demonstrates TOPP's ability to construct flexible analysis pipelines in support of complex experimental setups. Availability: The TOPP components are available as open-source software under the lesser GNU public license (LGPL). Source code is available from the project web site at www.OpenMS.de Difference Detection in LC-MS Data for Protein Biomarker Discovery Jennifer Listgarten and Sam T. Roweis, Department of Computer Science, University of Toronto, Canada Radford M. Neal, Department of Statistics and Department of Computer Science, University of Toronto, Canada Peter Wong and Andrew Emili, Banting and Best Department of Medical Research, University of Toronto, Canada Abstract: Motivation: There is a pressing need for improved proteomic screening methods allowing for earlier diagnosis of disease, systematic monitoring of physiological responses, and the uncovering of fundamental mechanisms of drug action. The combined platform of LC-MS (Liquid-Chromatography-Mass-Spectrometry) has shown promise in moving toward a solution in these areas. In this paper we present a technique for discovering differences in protein signal between two classes of samples of LC-MS serum proteomic data without use of tandem mass spectrometry, gels, or labelling. This method works on data from a lower-precision MS instrument, the type routinely used by and available to the community at large today. We test our technique on a controlled (spike-in) but realistic (serum biomarker discovery) experiment which is therefore verifiable. We also develop a new method for helping to assess the difficulty of a given spike-in problem. Lastly, we show that the problem of class prediction, sometimes mistaken as a solution to biomarker discovery, is actually a much simpler problem. Results: Using precision-recall curves with experimentally extracted ground truth, we show that i) our technique has good performance using 7 replicates from each class, ii) performance degrades with decreasing number of replicates, iii) the signal that we are teasing out is not trivially available (i.e., the differences are not so large that the task is easy). Lastly, we easily obtain perfect classification results for data in which the problem of extracting differences does not produce absolutely perfect results. This emphasizes the different nature of the two problems and also their relative difficulties. Availability Our data is publically available as a benchmark for further studies of this nature, along with supplementary information, at http://www.cs.toronto.edu/~jenn/LCMS.html. Identifying HLA Supertypes by Learning Distance Functions Tomer Hertz and Chen Yanover, Hebrew University of Jerusalem, Israel Abstract: The development of epitope-based vaccines crucially relies on the ability to classify Human Leukocyte Antigen (HLA) molecules into sets that have similar peptide binding specificities, termed supertypes. In their seminal work, Sette and Sidney defined 9 HLA class I supertypes, and claimed that  these provide an almost perfect coverage of the entire repertoire of HLA class I molecules. HLA alleles are highly polymorphic and polygenic and therefore experimentally classifying each of these molecules to supertypes is at present an impossible task. Recently, a number of computational methods have been proposed for this task. These methods are based on defining protein similarity measures, derived from analysis of binding peptides or from analysis of the proteins themselves. In this paper we define both peptide derived and protein derived similarity measures, which are based on learning distance functions. The peptide driven measure is defined using a peptide-peptide distance function, which is learnt using information about known binding and non-binding peptides. The protein similarity measure is defined using a protein-protein distance function, which is learnt using information about alleles previously classified into supertypes by Sette and Sidney. We compare the classification obtained by these two complimentary methods to previously suggested classification methods. In general, our results are in excellent agreement with the classifications suggested by Sette and Sidney and with those reported by Lund et. al. There are two important advantages of our proposed distance-based approach. First, it makes use of two different and important immunological sources of information -- HLA alleles and peptides that are known to bind or not bind to these alleles. Second, since each of our distance measures is trained using a different source of information, their combination can provide a more confident classification of alleles into supertypes. Comparative and Computational Genomics, Wed., January 24, 12:00-14:00 A Comparative Genome Approach to Marker Ordering Thomas Faraut, Simon de Givry, Patrick Chabrier, and Thomas Schiex, INRA, France Thomas Derrien, Francis Galibert, and Christophe Hitte, CNRS-Université de Renes 1, France Abstract: Motivation: Genome maps are fundamental to the study of an organism and essential in the process of genome sequencing which in turn provides the ultimate map of the genome. The increased number of genomes being sequenced offers new opportunities for the mapping of closely related organisms. We propose here an algorithmic formalization of a genome comparison approach to marker ordering. Results: In order to integrate a comparative mapping approach in the algorithmic process of map construction and selection, we propose to extend the usual statistical model describing the experimental data, here radiation hybrids (RH) data, in a statistical framework that models additionally the evolutionary relationships between a proposed map and a reference map: an existing map of the corresponding orthologous genes or markers in a closely related organism. This has concretely the effect of exploiting, in the process of map selection, the information of marker adjacencies in the related genome when the information provided by the experimental data is not conclusive for the purpose of ordering. In order to compute efficiently the map, we proceed to a reduction of the maximum likelihood estimation to the Traveling Salesman Problem. Experiments on simulated RH data sets as well as on a real RH data set from the canine RH project show that maps produced using the likelihood defined by the new model are significantly better than maps built using the traditional RH model. Family Relationships: Should Consensus Reign?-Consensus Clustering for Protein Families Macha Nikolski and David James Sherman, CNRS/LaBRI, Université Bordeaux 1, France Abstract: Motivation: Reliable identification of protein families is key to phylogenetic analysis, functional annotation and the exploration of protein function diversity in a given phylogenetic branch. As more and more complete genomes are sequenced, there is a need for powerful and reliable algorithms facilitating protein families fabrication. Results: We have formulated the problem of protein families construction as an instance of consensus clustering, for which we designed a novel algorithm that is computationally efficient in practice and produces high quality results. Our algorithm uses an election method to construct consensus families from competing clustering computations. Our consensus clustering algorithm is tailored to serve the specific needs of comparative genomics projects. First, it provides a robust means to incorporate results from different and complementary clustering methods, thus avoiding the need for an a priori choice that may introduce computational bias in the results. Second, it is suited to large-scale projects due to the practical efficiency. And third, it produces high quality results where families tend to represent groupings by biological function. Availability: This method has been used for Genolevures project to compute protein families of Hemiascomycetous yeasts. The data is available online at http://cbi.labri.fr/Genolevures/fam/ Merging Microarray Cell Synchronization Experiments through Curve Alignment Filip Hermans and Elena Tsiporkova, Dept. of Plant Systems Biology, Flanders Institute for Biotechnology, Belgium Abstract: The validity of periodic cell-cycle regulation studies in plants is seriously compromised by the relatively poor quality of cell synchrony that is achieved for plant suspension cultures in comparison to yeast and mammals. The present state-of-the-art plant synchronization techniques cannot offer a complete cell-cycle coverage and moreover a considerable loss of cell synchrony may occur toward the end of the sampling. One possible solution is to consider combining multiple data sets, produced by different synchronization techniques and thus covering different phases of the cell cycle, in order to arrive at a better cell-cycle coverage. We propose a method that enables pasting expression profiles from different plant cell synchronization experiments and results in an expression curve that spans more than one cell cycle. The optimal pasting overlap is determined via a dynamic time warping alignment. Consequently, the different expression time series are merged together by aggregating the corresponding expression values lying within the overlap area. We demonstrate that the periodic analysis of the merged expression profiles produces more reliable p-values for periodicity. Subsequent Gene Ontology analysis of the results confirms that merging synchronization experiments is a more robust strategy for the selection of potentially periodic genes. Additional validation of the proposed algorithm on yeast data is also presented. A Supervised Approach for Identifying Discriminating Genotype Patterns and its Application to Breast Cancer Data Nir Yosef and Roded Sharan, School of Computer Science, Tel Aviv University, Israel Zohar Yakhini and Anya Tsalenko, Agilent Technologies, Israel Vessela Kristensen, Department of Genetics, Institute of Cancer Research, Rikshospitalet-Radiumhospitalet Medical Center, Montebello, Norway Anne-Lise Børresen-Dale, Department of Genetics, Institute of Cancer Research, Rikshospitalet-Radiumhospitalet Medical Center, Montebello, Norway and Medical Faculty, University of Oslo, Norway Eytan Ruppin, School of Computer Science and School of Medicine, Tel Aviv University, Israel Abstract: Motivation: Large scale association studies, investigating the genetic determinants of a phenotype of interest, are producing increasing amounts of genomic variation data on human cohorts. A fundamental challenge in these studies is the detection of genotypic patterns that discriminate individuals exhibiting the phenotype under study from individuals that do not posses it. The difficulty stems from the large number of single nucleotide polymorphism(SNP) combinations that have to be tested. The discrimination problem becomes even more involved when additional high-throughput data, such as gene expression data, is available for the same cohort. Results: We have developed a graph theoretic approach for identifying discriminating patterns for a given phenotype in a genotyped population. The method is based on representing the SNP data as a bipartite graph of individuals and their SNP states, and identifying fully connected subgraphs of this graph that relate individuals enriched for a given phenotypic group. The method can handle additional data types such as expression profiles of the genotyped population. It is reminiscent of biclustering approaches with the crucial difference that its search process is guided by the phenotype under consideration in a supervised manner. We tested our approach in simulations and on real data. In simulations, our method was able to retrieve planted patterns with high success rate. We then applied our approach to a data set of 72 breast cancer patients with available gene expression profiles, genotyped over 695 SNPs. We detected several discriminating patterns thatwere highly significant with respect to various clinical phenotypes, and investigated the groups of patients and the groups of genes they defined. We found the patient groups to be highly enriched for other phenotypes and to display expression coherency among their profiles. The gene groups displayed functional coherency and involved genes with known role in cancer, providing additional support to their involvement. Evolution and Phylogenetics, Wed., January 24, 15:30-17:30 Inferring Phylogeny from Whole Genomes Pawel Gorecki and Jerzy Tiuryn, Warsaw University, Poland Abstract: Motivation: Inferring species phylogenies with a history of gene losses and duplications is a challenging and important task in computational biology. This problem can be solved by duplication-loss models in which the primary step is to reconcile a rooted gene tree with a rooted species tree. Most modern methods of phylogenetic reconstruction (from sequences) produce unrooted gene trees. This limitation leads to the problem of transforming unrooted gene tree into a rooted tree, and then reconciling rooted trees. The main questions are What about biological interpretation of choosing rooting?'', Can we find efficiently the optimal rootings?'', Is the optimal rooting unique?''. Results: In this paper we present a model of reconciling unrooted gene tree with a rooted species tree, which is based on a concept of choosing rooting which has minimal reconciliation cost. Our analysis leads to the surprising property that all the minimal rootings have identical distributions of gene duplications and gene losses in the species tree. It implies, in our opinion, that the concept of an optimal rooting is very robust, and thus biologically meaningful. Also, it has nice computational properties. We present a linear time and space algorithm for computing optimal rooting(s). This algorithm was used in two different ways to reconstruct the optimal species phylogeny of five known yeast genomes from approx. 4700 gene trees. Moreover, we determined locations (history) of all gene duplications and gene losses in the final species tree. It is interesting to notice that the top 5 species trees are the same for both methods. Using Median Sets for Inferring Phylogenetic Trees Matthias Bernt, Daniel Merkle, and Martin Middendorf, University of Leipzig, Germany Abstract: Motivation: Algorithms for phylogenetic tree reconstruction based on gene-order data typically repeatedly solve instances of the Reversal Median problem (RMP) which is to find for three given gene sequences a fourth sequence (called median) with a minimal sum of reversal distances. All existing algorithms of this type consider only one median for each RMP instance even when a large number of medians exist. A careful selection of one of the medians might lead to better phylogenetic trees. Results: We propose a heuristic algorithm amGRP for solving the Multiple Genome Rearrangement Problem (MGRP) by repeatedly solving instances of the RMP taking all medians into account. Algorithm amGRP uses a branch-and-bound method that branches over medians from a selected subset of all medians for each RMP instance. Different heuristics for selecting the subsets have been investigated. To show that the medians for RMP vary strongly with respect to different properties that are likely to be relevant for phylogenetic tree reconstruction, the set of all medians have been investigated for artificial data sets and mitochondrial DNA (mtDNA) sequences. Phylogenetic trees have been computed for a large set of random data sequences and two sets of mtDNA gene-order data for different animal taxa with amGRPg and with two standard algorithms (GRAPPA-DCM and MGR). The results show that amGRP outperforms both other algorithms with respect to solution quality and computation time on the test data. Availability: The source code of amGRP, additional results, and the test instances used in this paper are freely available from the authors of the paper. Efficient Parsimony-Based Methods for Phylogenetic Network Reconstruction Guohua Jin and Luay Nakhleh, Rice University, USA Sagi Snir, University of California, Berkeley, USA Tamir Tuller, Tel Aviv University, Israel Abstract: Phylogenies---the evolutionary histories of groups of organisms---play a major role in representing relationships among biological entities. Although many biological processes can be effectively modeled as a tree-like relationships, others, such as hybrid speciation, and horizontal gene transfer (HGT) result in networks of relationships rather than trees of relationships. Hybrid speciation is a significant evolutionary mechanism in plants, fish, and other groups of species. HGT plays a major role in bacterial genome diversification, and is a significant mechanism by which bacteria develop resistance to antibiotics. Maximum parsimony (MP) is one of the most commonly used criteria for phylogenetic tree inference. Roughly speaking, inference based on this criterion seeks the tree that minimizes the amount of evolution. In 1990, Jotun Hein proposed using this criterion for inferring the evolution of sequences subject to recombination. Preliminary results on small synthetic data sets (Nakhleh et al., 2005) demonstrated the criterion's application to phylogenetic network reconstruction in general, and HGT detection in particular. However, the naive algorithms used by the authors are inapplicable to large data sets due to their demanding computational requirements. Further, no rigorous theoretical analysis of computing the criterion was given, nor was it tested on biological data. In this work, we prove that the problem of scoring the parsimony of a phylogenetic network is NP-hard, and provide an improved fixed parameter tractable algorithm for it. Further, we devise an efficient heuristics for parsimony-based reconstruction of phylogenetic networks. We test our methods on both synthetic and biological data (rbcL gene in bacteria), and obtain very promising results. Phylogeny Reconstruction: Increasing the Accuracy of Pairwise Distance Estimation using Bayesian Inference of Evolutionary Rates Matan Ninio and Nir Friedman, The Hebrew University of Jerusalem, Israel Eyal Privman and Tal Pupko, Tel Aviv University, Israel Abstract: Distance-based methods for phylogeny reconstruction are the fastest and easiest to use, and their popularity is accordingly high. They are also the only known methods that can cope with huge datasets of thousands of sequences. These methods rely on evolutionary distance estimation, and are sensitive to errors in such estimations. In this study, a novel Bayesian method for estimation of evolutionary distances is developed. The proposed method enables the use of a sophisticated evolutionary model that better accounts for among-site rate variation (ASRV), thereby improving the accuracy of distance estimation. Rate variations are estimated within a Bayesian framework by extracting information from the entire dataset of sequences, unlike standard methods that can only use one pair of sequences at a time. We compare the accuracy of a cascade of distance estimation methods, starting from commonly used methods and moving towards the more sophisticated novel method. Simulation studies show significant improvements in the accuracy of distance estimation by the novel method over the commonly used ones. We demonstrate the effect of the improved accuracy on tree reconstruction using both real and simulated protein sequence alignments. Late Breaking Presentations Algorithms on Splicing Graphs for Identifying and Aligning Alternative Splicing Events Michael Sammeth and Sylvain Foissac, Genome Bioinformatics Laboratory, Centre for Genomic Regulation, Catalonia, EU Abstract: The complexity of molecular mechanisms involved in alternative splicing (AS) in literature grows continuously with new studies being published. This data requires an universal way, to describe AS events and to flexibly correlate them with each other. Herein, we describe a method to universally characterize AS events from gene annotations, and an algorithm to align gene structures in order to study the changes of AS events across homologous genes. An online visualization of the proposed methods AStaLaVista is being made available at: http://genome.imim.es/astalavista. Inferring Mechanistic Explanations for Transcription Factor Binding Changes Kenzie MacIsaac and Ernest Fraenkel, Massachusetts Institute of Technology, USA Abstract: We present an algorithm that determines the mechanisms underlying changes in transcriptional regulatory protein binding. The algorithm, called Bluebird, uses a probabilistic approach based on biophysical principles to jointly analyze high-throughput chromatin immunoprecipitation (ChIP-chip) data for multiple proteins in multiple conditions. Bluebird predicts how the observed binding changes are best explained: Do the binding specificities of the proteins change in different conditions? Are binding differences best explained by changes in the nuclear concentration of the proteins? Do several proteins interact? By probabilistically analyzing the raw ChIP-chip data, Bluebird avoids the use of arbitrary thresholds to define bound and unbound genes. Analysis of ChIP-chip data for 37 different yeast transcription factors gave motif predictions consistent with the known binding specificity for all factors. In addition, results for several factors yielded predictions about the underlying mechanism of binding changes between conditions that were in agreement with previously reported experimental results. Reconstructing Sibling Relationships from Microsatellite Data Saad Sheikh, Tanya Berger-Wolf, Bhaskar Dasgupta, and Mary Ashley, University of Illinois at Chicago, USA Wanpracha Chaovalitwongse, Rutgers University, USA Abstract: Reconstruction of sibling relationships from genetic data is an important component of many biological applications. Most current sibship reconstruction methods use statistical and heuristic techniques that rely on a priori knowledge about various parameter distributions. We present a deterministic algorithm that parsimoniously reconstructs sibling groups. We use Mendelian laws of inheritance to generate potential sibling groups. We then optimally select a minimum set of sibling groups necessary to explain the data. We validate our approach using both simulated and real biological data. Refinement and Expansion of Signaling Pathways: The Osmotic Response Network in Yeast Irit Gat-Viks, Tel Aviv University, Israel Abstract: The analysis of large scale genome-wide experiments carries the promise of dramatically broadening our understanding on biological networks. The challenge of systematic integration of experimental results with established biological knowledge on a pathway is still unanswered. Here we present a methodology that attempts to answer this challenge when investigating signaling pathways. We formalize existing qualitative knowledge as a probabilistic model that depicts known interactions between molecules (genes, proteins etc.) as a network and known regulatory relations as logics. We present algorithms that analyze experimental results (e.g., transcription profiles) vis-a-vis the model, and propose improvements to the model based on the fit to the experimental data. These algorithms refine the relations between model components, as well as expand the model to include new components that are regulated by components of the original network. Using our methodology, we have modeled together the knowledge on four established signaling pathways related to osmotic shock response in S. cerevisiae. Using over 100 published transcription profiles, our refinement methodology revealed three cross-talks in the network. The expansion procedure identified with high confidence large groups of genes that are co-regulated by transcription factors from the original network via a common logic. The results reveal a novel delicate repressive effect of the HOG pathway on many transcriptional target genes, and suggest an unexpected alternative functional mode of the MAP kinase Hog1. The analysis also predicts novel feed-forward and feedback loops in the regulatory network, which probably support cellular adaptation to osmotic stress. These results demonstrate that by integrated analysis of data and of well-defined knowledge on signaling pathways, one can generate concrete biological hypotheses about signaling cascades and their downstream regulatory programs. PROMO: A Method for Identifying Modules in Protein Interaction Networks Omer Tamuz, Yaron Singer, and Roded Sharan, Tel Aviv University, Israel Abstract: A major goal of systems biology is the dissection of protein machineries within the cell. The recent availability of genome-scale protein interaction networks provides a key resource for addressing this challenge. Current approaches to the problem are based on devising a scoring scheme for putative protein modules and applying a heuristic search for high-scoring modules. Here we develop a branch and bound approach to perform an exhaustive scan of the search space.We show that such a search is possible and enables detecting modules that are missed by previous approaches. The modules we identify are shown to be significantly coherent in their functional annotations and expression patterns. Our algorithm, PROMO, is shown to outperform the state-of-the-art MCODE and to provide results that are more in line with current biological knowledge. Temporal Aspects of Histone-Modifying Proteins Revealed by Sub-network Analysis Sabine Dietmann, Michael Mader, Hans-Werner Mewes, and Martin Münsterkötter, Institute for Bioinformatics, Germany Abstract: Network analysis has been recently applied to model not only static topological properties, but also temporal aspects of protein complexes on a genomic scale, e.g. during the yeast cell cycle. The topology of transcription factor networks, in particular, has been studied extensively. In eukaryotic genomes, the chromosomal context is crucial for transcriptional activity because of the regulatory effects of histones, around which DNA are wrapped to form the nucleosomes and further the chromatin. The properties of chromatin can be altered either by nucleosome remodeling or by covalently modifying the N-terminal tails of histones. Here, we present an integrative approach that extends the yeast transcription factor network by sub-networks of histone-modifying proteins and addresses temporal aspects of potentially recruiting transcription factors and their behavior under different cellular conditions. We provide a thorough benchmark of sub-networks extracted form protein-protein and protein-DNA interaction data sets against genome-wide location data sets.

format: plain


text:
# Cloth Swapping with Deep Learning: Implement Conditional Analogy GAN in Keras

The Conditional Analogy GAN: Swapping Fashion Articles on People Images (link)

Given three input images: human wearing cloth A, stand alone cloth A and stand alone cloth B, the Conditional Analogy GAN (CAGAN) generates a human image wearing cloth B. See figures below.

In my experiment, CAGAN was able to swap clothes in different categories, for example, long/short sleeve t-shirts (which is not shown in original paper). In other words, CAGAN not only changed color of clothes but had to generate human body part to transfer from long sleeve to short sleeve domain.

Preview:

## Dataset:

Images are crawled from zalora.com.tw. We gathered about 2000 human/article pairs as training data.
(*Due to copyright concern, some images in this post are replaced by illustrations or cropped.)

## Configuration

• Learning rate: 2e-4
• Batch size: 16 (CAGAN) or 8 (CAGAN+StackGAN-v2)
• Data augmentation: random cropping and flipping

## GitHub repo.

keras implementation of CAGAN can be found here.

• In CAGAN paper, a description about implementation detail writes: “In addition, we use always the last 6 channels of any intermediate layer (in both G and D) to store downsampled copies of the inputs $x_i,y_i$“. I am not totally understand what this means, so what I did was to concatenate $x_i$  and $y_i$ to every intermediate layers. However, I couldn’t get any successful result but saturated noises when concatenating $x_i$  and $y_i$ to the discriminator. Thus this concatenation is only applied on the generator.

## I. CycleGAN as our first try

Why CycleGAN? It’s a go-to solution (personally) for image-to-image generation. There’s already keras implementations on GitHub.
Did it work? Yes, but lack of diversity and fidelity.

Keras implementation of CycleGAN is borrowed from here.

Results:
Given stand alone article images as input, the above figure shows generated human images after training for ~10k iterations. CycleGAN failed to generate human face, and body shapes are far from real. There are also mode collapses (similar human pose) in the bottom row.

## II. Reimplement CAGAN

Why CAGAN? Want to generate realistic human images with different poses. Use full leverage of input human images.
Does it work? Yes.

Overview:

Given three input images: $x_i$, human wearing cloth A; $y_i$, stand alone cloth A; and $y_j$, stand alone cloth B, the Conditional Analogy GAN (CAGAN) generates a human image $x_{ij}$  that swap its cloth from A to B. A discriminator is applied to help improving generated result quality by classifying True/False on three example pairs.

Architecture:

The generator is a typical UNET, which concatenate early layer features to later layers. Output of the generator is a four channels tensor containing $\left [\alpha , \hat{x}{ij}^R, \hat{x}{ij}^G, \hat{x}_{ij}^B \right ]$, where superscription R, G and B means the corresponding color channel. This tensor is then merged with $x_i$ into one RGB images by $x_{ij}=\alpha \odot x_{ij}^{RGB} + (1-\alpha) \odot x_i$ . Symbol $\odot$  represents pixel-wise multiplication.

The discriminator is composed of several layers of Conv2D, and the output is a 8x8x1 sigmoid output (input size 128x96x3), a so-called PatchGAN approach.

Training loss function:

In CAGAN training, there are 3 losses applied: First, an adversarial loss $L_{cGAN}(G,D)$.
where $\lambda$  and $\mu$  are indices of spatial dimension, if the 8x8x1 sigmoid output. Second loss, the regularizaiton for alpha mask, $L_{id}(G)$:
where ||$\cdot$|| is the L1 norm. $L_{id}(G)$ “regularizes the outputs of G to change as little as possible from the original human image”. Third, the cycle loss $L_{cyc}(G)$ , also called reconstruction loss in some paper, that “force consistent results when swapping clothes”:

Cherry-picked Results:

So, what’s the problem?
When training for over 3000 updates, there were repetitive artifacts in the generated images, and sometimes human faces were distorted, which looks like this:

These artifacts can also be found in figure 6(c) and (d) of original CAGAN paper.
I think this is caused by small bottleneck dimension (1/16x of input size), so maybe the architectures and approaches used in super-resolution-related tasks can be helpful, which leads to the next section.

## III. CAGAN + StackGAN-v2

Why combined CAGAN with StackGan-v2? Want to generate high quality texture/graphics and also stabilize training.
Does it work? Kind of, it generated successful results more often. And its training is more stable.

Any tricks being used during training?
1. Add Gaussian noise to discriminator inputs.
2. Use mixup technique on discriminator inputs.
3. Change Conv2D kernel size to (4,3).
4. Add an identity loss to generator loss. See [Experiment Notes] 2 below.
5. Size 64×48 cyclic output is merged as $x_{ij(cyclic)}=\alpha \odot x_{ij(cyclic)^{RGB} + (1-\alpha) \odot \hat{x}_{ij}^{RGB}}$, while $\hat{x}_{ij}^{RGB}$ be $x_{ij}$ in the 128×96 and 256×192 cyclic outputs.
6. Concatenate $[x_i, y_j]$ instead of $[x_i, y_i]$ (as in CAGAN paper) to every intermediate layers.

Architecture:
Figure above shows model architecture in detail. The model takes three images as input and generates three human images (with alpha mask) in different sizes at its end. We did some modifications on the CAGAN architecture: First, inspired by this paper working on image completion, we substituted part of stride 2 Conv2D layers with dilated Conv2D layers so that feature map resolution halves only twice. This prevent output images from losing details. Second, a refiner network is introduced in the decoder. Refiner network consists of two stacks of residual blocks, it learns to add detail as well as improve realism of output image. Furthermore, we apply squeeze-and-excitation module on top of residual blocks that (hopefully learns to) increase sensitivity to informative features.

Another backbone of our model is StackGAN-v2 (StackGAN++). StackGAN-v2 consists of multiple generators and discriminators in a tree-like structure. In our model, we use three-stages of generators at different scales: 256 x 192, 128 x 96 and 64 x 48, while the deepest one generates the final output image. The StackGAN architecture helped to stabilize training and improve output color authenticity (e.g., skin color).

Notice that we feed input images, $x_i$  and $y_j$, to almost every intermediate layers. This further improved training stability. We also found in experiments that concatenating $x_i$  and $y_j$ (instead of $x_i$  and $y_i$ as suggested in CAGAN paper) preserves more detail such as graphics and textures of target article throughout the forward-pass.

(The discriminator has the same structure as of CAGAN. It is purposely kept simple.)

Training loss function:
In addition to loss functions used in CAGAN, we introduced two more loss functions: identity loss $L_{ident}$ and color consistency loss $L_{color}$ (from StackGAN-v2). They are defined as:

$L_{ident}=\left \| x_{ident}-x_i \right \|$, where $x_{ident}=G([x_i, y_i, y_i]),$
$L_{color}=\lambda_1\left \| m_l - m_{l-1} \right \|_2^2+ \left \| \Sigma _l - \Sigma_{l-1} \right \|_F^2$,

where $m=\sum _{k} x_k/N$  and $\Sigma =\sum_{k}(x_k-m)(x_k-m)^T$ are the mean and covariance of the given image, $x_k=(R,G,B)^T$ represents a pixel in a generated image.

The identity loss encourages model to focus on difference between $y_i$  and $y_j$. And color consistency loss is introduced to “keep samples generated from the same input at different generators more consistent in color and thus to improve the quality of the generated”.

Cherry-picked Results:

Input images are shown as the first three images. Following by corresponding generated human image(s) at the right. (Input images are replaced by illustrations)

Intra-category

Long sleeves to short sleeves

The above figure shows refinement of output image in each stage: the upper image shows refinement in skin color and the lower one shows refinement in graphic color.

Graphics

Our model is able to generate clearer graphic of target article than original CAGAN.

Others

We can see from the result images that there are no repetitive artifact being generated. (Although not being shown, the artifacts on human face are also reduced in our model.)

Great, what now?
Overall, I’m OK with the result since our model is trained on only ~2000 image pairs (<1/7x of CAGAN). But it generates higher quality image as a trade-off of increasing model complexity, in other word, longer training time. What’s more, the generated images are still far from perfect. For example, our model can not learn the distortion of wearing cloth (to stand alone cloth). Most of the swapping results look like just copy-pasting target clothes onto human images following by some refinements. So the placement of graphics are usually off position. We tried Spatial Transformer Layer (with Thin Plane Spline transform) but unfortunately failed to obtain good result. Anyway, there are lots of defections we can think of: blunt edges, low successful rate, unawareness of neck-lines, etc..

Also, we did not conduct any quantitative evaluation. We only judged performance by looking at its visual quality. Here I would like to quote from Generative Adversarial Networks: An Overview (as an excuse of me lacking knowledge of GANs): “How can one gauge the ﬁdelity of samples synthesized by a generative models? Should we use a likelihood estimation? Can a GAN trained using one methodology be compared to another (model comparison)? These are open-ended questions that are not only relevant for GANs, but also for probabilistic models, in general.”

## What I’ve learnt from implementing CAGAN:

1. To understand the concepts/insight behind certain architecture is more important than the architecture itself.
2. Spend too much time on tuning hyper-parameters, like kernel size and weighting factor of loss function, is unwise since it always leads to trivial improvement.
3. Intuition NEVER worked on neural networks. What I thought will improved the results were 99% failed.
4. Assign each layer a proper name so I can Ctrl+F to search them in model.summary().
5. Do unit test that check if weights are updated after an iteration.

Update 25 Nov., 2017:
A new paper titled “VITON: An Image-based Virtual Try-on Network” from UMD (Larry Davis’ lab) presents impressive result on cloth swapping, basically making this post worthless LOL. I believe TPS transform part in the paper can be replaced by a spatial transformer network.

Update 18 Feb., 2018:
Generative Adversarial Network-Based Virtual Try-On with Clothing Region: An ICLR workshop paper based on CAGAN, in which a human parsing network is introduced to segment out clothing region. i.e., the alpha mask is no longer generated by the generator but a pre-trained network.

Update 20 Nov., 2018:
SwapNet: Garment Transfer in Single View Images: An ECCV2018 paper in which the author proposes a framework that “transferring garments across images of people with arbitrary body pose, shape, and clothing”. The network leverages pose and cloth segmentation as prior information. It also uses warping (as in VITON) to improve texture details of the generated clothing.

[Experiment Notes]
1. Substitute Con2DTranspose with Nearest-neighbour up-sampling did not give better result images since cyclic $x_i$ is too blurry and the alpha mask can’t learn well.
2. Adding identity loss reduce checker board artifact and stabilize network from mode collapse as well. The identity loss is a L1 loss defined as: $loss_{L1}(idt, x_i)$, where $idt=G([x_i, y_i, y_i])$. (Further investigation is needed. I also modified loss function a little bit in the same experiment)
3. Perceptual loss (MobileNet in my experiment) did not help, too. Perhaps it is because cycle loss does not have much impact on result image. As the cycle loss weighting factor $\lambda$ is 10 in cycleGAN (tjwei’s keras implemetation) and 1 in CAGAN. Also tried perceptual adversarial loss (which substitute Discriminator with pre-trained CNNs), led to mode collapse. Updated 11 Nov.: After examing at output features maps from layers of MobileNet, I found that we can not judge if two human are wearing similar clothes by feature map distance between these two human images. The difference is also affected by color of clothes and human poses. For example, feature map difference of two human wearing similar plain red t-shirts is larger than difference of one human wearing black t-shirt and another gray.
4. StackGAN-v2 architecture might help. Still under experiment (tuning hyper-parameters). Only got similar result with original CAGAN till now. Done.
5. Models trained on images in Lab color space did not perform well on white articles.
6. Didn’t converge when using least square loss.
7. Concatenating input [$x_i, y_i$] to every intermediate layers is crucial to generate better image. I was wondering if there’s another way to do this, e.g., using residual block instead. But I guess the authors had tried it.
8. Using dilated convolution improves texture (e.g., graphics on t-shirts) quality a little bit.
9. Add an auxiliary local context discriminator (inspired by this paper) Did not find a good way to plug this into CAGANs.
10. Use more dilated Conv2D and less stride2 Conv2D layers in generator (same paper of 9).
11. Using cyclic loss in a StackGAN-v2 architecture is a concept similar to semantic consistency loss in XGAN (recently published paper from google brain): both of them use intermediate layers’ features distance as loss to encourage content consistency.
12. I’ve been wondering for a while if WGAN-GP will bring better result. After skimming through this paper that providing comparison between GAN and WGAN(-GP) on super resolution task, I decided to postpone experiment with WGAN.

## 4 thoughts on “Cloth Swapping with Deep Learning: Implement Conditional Analogy GAN in Keras”

1. Xintong Han says:

Hi, I am Xintong Han. I tried spatial transformer network (for at least two weeks) when working on the VITON paper. STN is very hard to converge even given the ground truth TPS parameters as part of the supervision, which makes it very hard to outperform shape context matching. If you make any progress on getting the STN work in this scenario, I am very glad to hear about that.

Like

1. Hi, Xintong.I tried STN on CAGAN and didn’t find successful result either.
Regarding training STN in a supervised manner, did you mean that given two binary mask as inputs: the cloth mask M and masked target clothing C (similar to the WarpNet cited in VITON paper), the STN can not learn TPS parameters well?

Like

2. tfxsuccess says:

i am struggling with virtual dressing room app. did any one know any such site having coode and detail technical stuff
tfxsuccess@gmail.com

Like

3. Anonymous says:

Long sleeves to short sleeves,it seems worse than others.

Like