@article{4547,
  abstract     = {We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Buechi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.},
  author       = {Krishnendu Chatterjee and Doyen, Laurent and Thomas Henzinger and Raskin, Jean-François},
  journal      = {Logical Methods in Computer Science},
  number       = {184},
  pages        = {1 -- 23},
  publisher    = {International Federation of Computational Logic},
  title        = {{Algorithms for omega-regular games with imperfect information}},
  doi          = {10.2168/LMCS-3(3:4)2007},
  volume       = {3},
  year         = {2007},
}

@phdthesis{4559,
  abstract     = {We study games played on graphs with omega-regular conditions specified as parity, Rabin, Streett or Muller conditions. These games have applications in the verification, synthesis, modeling, testing, and compatibility checking of reactive systems. Important distinctions between graph games are as follows: (a) turn-based vs. concurrent games, depending on whether at a state of the game only a single player makes a move, or players make moves simultaneously; (b) deterministic vs. stochastic, depending on whether the transition function is a deterministic or a probabilistic function over successor states; and (c) zero-sum vs. non-zero-sum, depending on whether the objectives of the players are strictly conflicting or not.

We establish that the decision problem for turn-based stochastic zero-sum games with Rabin, Streett, and Muller objectives are NP-complete, coNP-complete, and PSPACE-complete, respectively, substantially improving the previously known 3EXPTIME bound. We also present strategy improvement style algorithms for turn-based stochastic Rabin and Streett games. In the case of concurrent stochastic zero-sum games with parity objectives we obtain a PSPACE bound, again improving the previously known 3EXPTIME bound. As a consequence, concurrent stochastic zero-sum games with Rabin, Streett, and Muller objectives can be solved in EXPSPACE, improving the previously known 4EXPTIME bound. We also present an elementary and combinatorial proof of the existence of memoryless \epsilon-optimal strategies in concurrent stochastic games with reachability objectives, for all real \epsilon>0, where an \epsilon-optimal strategy achieves the value of the game with in \epsilon against all strategies of the opponent. We also use the proof techniques to present a strategy improvement style algorithm for concurrent stochastic reachability games.

We then go beyond \omega-regular objectives and study the complexity of an important class of quantitative objectives, namely, limit-average objectives. In the case of limit-average games, the states of the graph is labeled with rewards and the goal is to maximize the long-run average of the rewards. We show that concurrent stochastic zero-sum games with limit-average objectives can be solved in EXPTIME.

Finally, we introduce a new notion of equilibrium, called secure equilibrium, in non-zero-sum games which captures the notion of conditional competitiveness. We prove the existence of unique maximal secure equilibrium payoff profiles in turn-based deterministic games, and present algorithms to compute such payoff profiles. We also show how the notion of secure equilibrium extends the assume-guarantee style of reasoning in the game theoretic framework.},
  author       = {Krishnendu Chatterjee},
  pages        = {1 -- 247},
  publisher    = {University of California, Berkeley},
  title        = {{Stochastic ω-Regular Games}},
  year         = {2007},
}

@phdthesis{4566,
  abstract     = {Complex system design today calls for compositional design and implementation. However each component is designed with certain assumptions about the environment it is meant to operate in, and delivering certain guarantees if those assumptions are satisfied; numerous inter-component interaction errors are introduced in the manual and error-prone integration process as there is little support in design environments for machine-readably representing these assumptions and guarantees and automatically checking consistency during integration.

Based on Interface Automata we propose a framework for compositional design and analysis of systems: a set of domain-specific automata-theoretic type systems for compositional system specification and analysis by behavioral specification of open systems. We focus on three different domains: component-based hardware systems communicating on bidirectional wires. concurrent distributed recursive message-passing software systems, and embedded software system components operating in resource-constrained environments. For these domains we present approaches to formally represent the assumptions and conditional guarantees between interacting open system components. Composition of such components produces new components with the appropriate assumptions and guarantees. We check satisfaction of temporal logic specifications by such components, and the substitutability of one component with another in an arbitrary context. Using this framework one can analyze large systems incrementally without needing extensive summary information to close the system at each stage. Furthermore, we focus only on the inter-component interaction behavior without dealing with the full implementation details of each component. Many of the merits of automata-theoretic model-checking are combined with the compositionality afforded by type-system based techniques. We also present an integer-based extension of the conventional boolean verification framework motivated by our interface formalism for embedded software components.

Our algorithms for checking the behavioral compatibility of component interfaces are available in our tool Chic, which can be used as a plug-in for the Java IDE JBuilder and the heterogenous modeling and design environment Ptolemy II.

Finally, we address the complementary problem of partitioning a large system into meaningful coherent components by analyzing the interaction patterns between its basic elements. We demonstrate the usefulness of our partitioning approach by evaluating its efficacy in improving unit-test branch coverage for a large software system implemented in C.},
  author       = {Chakrabarti, Arindam},
  pages        = {1 -- 244},
  publisher    = {University of California, Berkeley},
  title        = {{A framework for compositional design and analysis of systems}},
  year         = {2007},
}

@article{4567,
  abstract     = {BLAST is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, BLAST either statically proves that the program satisfies the safety property, or provides an execution path that exhibits a violation of the property (or, since the problem is undecidable, does not terminate). BLAST constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. This paper gives an introduction to BLAST and demonstrates, through two case studies, how it can be applied to program verification and test-case generation. In the first case study, we use BLAST to statically prove memory safety for C programs. We use CCured, a type-based memory-safety analyzer, to annotate a program with run-time assertions that check for safe memory operations. Then, we use BLAST to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate execution scenarios that violate the assertions for the remaining run-time checks. In our second case study, we use BLAST to automatically generate test suites that guarantee full coverage with respect to a given predicate. Given a C program and a target predicate p, BLAST determines the program locations q for which there exists a program execution that reaches q with p true, and automatically generates a set of test vectors that cause such executions. Our experiments show that BLAST can provide automated, precise, and scalable analysis for C programs.},
  author       = {Beyer, Dirk and Thomas Henzinger and Jhala, Ranjit and Majumdar, Ritankar S},
  journal      = {International Journal on Software Tools for Technology Transfer},
  number       = {5},
  pages        = {505 -- 525},
  publisher    = {Springer},
  title        = {{The software model checker BLAST: Applications to software engineering}},
  doi          = {10.1007/s10009-007-0044-z},
  volume       = {9},
  year         = {2007},
}

@inproceedings{4570,
  abstract     = {We consider the minimum-time reachability problem in concurrent two-player timed automaton game structures. We show how to compute the minimum time needed by a player to reach a target location against all possible choices of the opponent. We do not put any syntactic restriction on the game structure, nor do we require any player to guarantee time divergence. We only require players to use receptive strategies which do not block time. The minimal time is computed in part using a fixpoint expression, which we show can be evaluated on equivalence classes of a non-trivial extension of the clock-region equivalence relation for timed automata.},
  author       = {Brihaye, Thomas and Thomas Henzinger and Prabhu, Vinayak S and Raskin, Jean-François},
  pages        = {825 -- 837},
  publisher    = {Springer},
  title        = {{Minimum-time reachability in timed games}},
  doi          = {10.1007/978-3-540-73420-8_71},
  volume       = {4596},
  year         = {2007},
}

@inproceedings{4571,
  abstract     = {The success of software verification depends on the ability to find a suitable abstraction of a program automatically. We propose a method for automated abstraction refinement which overcomes some limitations of current predicate discovery schemes. In current schemes, the cause of a false alarm is identified as an infeasible error path, and the abstraction is refined in order to remove that path. By contrast, we view the cause of a false alarm -the spurious counterexample- as a full-fledged program, namely, a fragment of the original program whose control-flow graph may contain loops and represent unbounded computations. There are two advantages to using such path programs as counterexamples for abstraction refinement. First, we can bring the whole machinery of program analysis to bear on path programs, which are typically small compared to the original program. Specifically, we use constraint-based invariant generation to automatically infer invariants of path programs-so-called path invariants. Second, we use path invariants for abstraction refinement in order to remove not one infeasibility at a time, but at once all (possibly infinitely many) infeasible error computations that are represented by a path program. Unlike previous predicate discovery schemes, our method handles loops without unrolling them; it infers abstractions that involve universal quantification and naturally incorporates disjunctive reasoning.},
  author       = {Beyer, Dirk and Thomas Henzinger and Majumdar, Ritankar S and Rybalchenko, Andrey},
  pages        = {300 -- 309},
  publisher    = {ACM},
  title        = {{Path invariants}},
  doi          = {10.1145/1250734.1250769},
  year         = {2007},
}

@inproceedings{4572,
  abstract     = {We present a constraint-based algorithm for the synthesis of invariants expressed in the combined theory of linear arithmetic and uninterpreted function symbols. Given a set of programmer-specified invariant templates, our algorithm reduces the invariant synthesis problem to a sequence of arithmetic constraint satisfaction queries. Since the combination of linear arithmetic and uninterpreted functions is a widely applied predicate domain for program verification, our algorithm provides a powerful tool to statically and automatically reason about program correctness. The algorithm can also be used for the synthesis of invariants over arrays and set data structures, because satisfiability questions for the theories of sets and arrays can be reduced to the theory of linear arithmetic with uninterpreted functions. We have implemented our algorithm and used it to find invariants for a low-level memory allocator written in C.},
  author       = {Beyer, Dirk and Thomas Henzinger and Majumdar, Ritankar S and Rybalchenko, Andrey},
  pages        = {378 -- 394},
  publisher    = {Springer},
  title        = {{Invariant synthesis for combined theories}},
  doi          = {10.1007/978-3-540-69738-1_27},
  volume       = {4349},
  year         = {2007},
}

@inproceedings{4573,
  abstract     = {In automatic software verification, we have observed a theoretical convergence of model checking and program analysis. In practice, however, model checkers are still mostly concerned with precision, e.g., the removal of spurious counterexamples; for this purpose they build and refine reachability trees. Lattice-based program analyzers, on the other hand, are primarily concerned with efficiency. We designed an algorithm and built a tool that can be configured to perform not only a purely tree-based or a purely lattice-based analysis, but offers many intermediate settings that have not been evaluated before. The algorithm and tool take one or more abstract interpreters, such as a predicate abstraction and a shape analysis, and configure their execution and interaction using several parameters. Our experiments show that such customization may lead to dramatic improvements in the precision-efficiency spectrum.},
  author       = {Beyer, Dirk and Thomas Henzinger and Théoduloz, Grégory},
  pages        = {504 -- 518},
  publisher    = {Springer},
  title        = {{Configurable software verification: Concretizing the convergence of model checking and program analysis}},
  doi          = {10.1007/978-3-540-73368-3_51},
  volume       = {4590},
  year         = {2007},
}

@inproceedings{4575,
  abstract     = {We present a case study to illustrate our formalism for the specification and verification of the method-invocation behavior of web-service applications constructed from asynchronously interacting multi-threaded distributed components. Our model is expressive enough to allow the representation of recursion and dynamic thread creation, and yet permits the algorithmic analysis of the following two questions: (1) Does a given service satisfy a safety specification? (2) Can a given service be substituted by a another service in an arbitrary context? Our case study is based on the Amazon.com E-Commerce Services (ECS) platform.},
  author       = {Beyer, Dirk and Chakrabarti, Arindam and Thomas Henzinger and Seshia, Sanjit A},
  pages        = {831 -- 838},
  publisher    = {IEEE},
  title        = {{An application of web-service interfaces}},
  doi          = {10.1109/ICWS.2007.32 },
  year         = {2007},
}

@article{4626,
  abstract     = {We consider concurrent two-player games with reachability objectives. In such games, at each round, player 1 and player 2 independently and simultaneously choose moves, and the two choices determine the next state of the game. The objective of player 1 is to reach a set of target states; the objective of player 2 is to prevent this. These are zero-sum games, and the reachability objective is one of the most basic objectives: determining the set of states from which player 1 can win the game is a fundamental problem in control theory and system verification. There are three types of winning states, according to the degree of certainty with which player 1 can reach the target. From type-1 states, player 1 has a deterministic strategy to always reach the target. From type-2 states, player 1 has a randomized strategy to reach the target with probability 1. From type-3 states, player 1 has for every real ε>0 a randomized strategy to reach the target with probability greater than 1−ε. We show that for finite state spaces, all three sets of winning states can be computed in polynomial time: type-1 states in linear time, and type-2 and type-3 states in quadratic time. The algorithms to compute the three sets of winning states also enable the construction of the winning and spoiling strategies.},
  author       = {de Alfaro, Luca and Thomas Henzinger and Kupferman, Orna},
  journal      = {Theoretical Computer Science},
  number       = {3},
  pages        = {188 -- 217},
  publisher    = {Elsevier},
  title        = {{Concurrent reachability games}},
  doi          = {10.1016/j.tcs.2007.07.008},
  volume       = {386},
  year         = {2007},
}

@article{8488,
  abstract     = {We demonstrate for different protein samples that three-dimensional HNCO and HNCA correlation spectra may be recorded in a few minutes acquisition time using the band-selective excitation short-transient sequences presented here. This opens new perspectives for the NMR structural investigation of unstable protein samples and real-time site-resolved studies of protein kinetics.},
  author       = {Schanda, Paul and Van Melckebeke, Hélène and Brutscher, Bernhard},
  issn         = {0002-7863},
  journal      = {Journal of the American Chemical Society},
  keywords     = {Colloid and Surface Chemistry, Biochemistry, General Chemistry, Catalysis},
  number       = {28},
  pages        = {9042--9043},
  publisher    = {American Chemical Society},
  title        = {{Speeding up three-dimensional protein NMR experiments to a few minutes}},
  doi          = {10.1021/ja062025p},
  volume       = {128},
  year         = {2006},
}

@article{8489,
  abstract     = {Structure elucidation of proteins by either NMR or X‐ray crystallography often requires the screening of a large number of samples for promising protein constructs and optimum solution conditions. For large‐scale screening of protein samples in solution, robust methods are needed that allow a rapid assessment of the folding of a polypeptide under diverse sample conditions. Here we present HET‐SOFAST NMR, a highly sensitive new method for semi‐quantitative characterization of the structural compactness and heterogeneity of polypeptide chains in solution. On the basis of one‐dimensional 1H HET‐SOFAST NMR data, obtained on well‐folded, molten globular, partially‐ and completely unfolded proteins, we define empirical thresholds that can be used as quantitative benchmarks for protein compactness. For 15N‐enriched protein samples, two‐dimensional 1H‐15N HET‐SOFAST correlation spectra provide site‐specific information about the structural heterogeneity along the polypeptide chain.},
  author       = {Schanda, Paul and Forge, Vincent and Brutscher, Bernhard},
  issn         = {0749-1581},
  journal      = {Magnetic Resonance in Chemistry},
  number       = {S1},
  pages        = {S177--S184},
  publisher    = {Wiley},
  title        = {{HET-SOFAST NMR for fast detection of structural compactness and heterogeneity along polypeptide chains}},
  doi          = {10.1002/mrc.1825},
  volume       = {44},
  year         = {2006},
}

@article{8490,
  abstract     = {We demonstrate the feasibility of recording 1H–15N correlation spectra of proteins in only one second of acquisition time. The experiment combines recently proposed SOFAST-HMQC with Hadamard-type 15N frequency encoding. This allows site-resolved real-time NMR studies of kinetic processes in proteins with an increased time resolution. The sensitivity of the experiment is sufficient to be applicable to a wide range of molecular systems available at millimolar concentration on a high magnetic field spectrometer.},
  author       = {Schanda, Paul and Brutscher, Bernhard},
  issn         = {1090-7807},
  journal      = {Journal of Magnetic Resonance},
  keywords     = {Nuclear and High Energy Physics, Biophysics, Biochemistry, Condensed Matter Physics},
  number       = {2},
  pages        = {334--339},
  publisher    = {Elsevier},
  title        = {{Hadamard frequency-encoded SOFAST-HMQC for ultrafast two-dimensional protein NMR}},
  doi          = {10.1016/j.jmr.2005.10.007},
  volume       = {178},
  year         = {2006},
}

@article{8513,
  author       = {Kaloshin, Vadim and Saprykina, Maria},
  issn         = {1553-5231},
  journal      = {Discrete & Continuous Dynamical Systems - A},
  number       = {2},
  pages        = {611--640},
  publisher    = {American Institute of Mathematical Sciences (AIMS)},
  title        = {{Generic 3-dimensional volume-preserving diffeomorphisms with superexponential growth of number of periodic orbits}},
  doi          = {10.3934/dcds.2006.15.611},
  volume       = {15},
  year         = {2006},
}

@article{8514,
  abstract     = {We study the extent to which the Hausdorff dimension of a compact subset of an infinite-dimensional Banach space is affected by a typical mapping into a finite-dimensional space. It is possible that the dimension drops under all such mappings, but the amount by which it typically drops is controlled by the ‘thickness exponent’ of the set, which was defined by Hunt and Kaloshin (Nonlinearity12 (1999), 1263–1275). More precisely, let $X$ be a compact subset of a Banach space $B$ with thickness exponent $\tau$ and Hausdorff dimension $d$. Let $M$ be any subspace of the (locally) Lipschitz functions from $B$ to $\mathbb{R}^{m}$ that contains the space of bounded linear functions. We prove that for almost every (in the sense of prevalence) function $f \in M$, the Hausdorff dimension of $f(X)$ is at least $\min\{ m, d / (1 + \tau) \}$. We also prove an analogous result for a certain part of the dimension spectra of Borel probability measures supported on $X$. The factor $1 / (1 + \tau)$ can be improved to $1 / (1 + \tau / 2)$ if $B$ is a Hilbert space. Since dimension cannot increase under a (locally) Lipschitz function, these theorems become dimension preservation results when $\tau = 0$. We conjecture that many of the attractors associated with the evolution equations of mathematical physics have thickness exponent zero. We also discuss the sharpness of our results in the case $\tau > 0$.},
  author       = {OTT, WILLIAM and HUNT, BRIAN and Kaloshin, Vadim},
  issn         = {0143-3857},
  journal      = {Ergodic Theory and Dynamical Systems},
  number       = {3},
  pages        = {869--891},
  publisher    = {Cambridge University Press},
  title        = {{The effect of projections on fractal sets and measures in Banach spaces}},
  doi          = {10.1017/s0143385705000714},
  volume       = {26},
  year         = {2006},
}

@inproceedings{8515,
  abstract     = {We consider the evolution of a set carried by a space periodic incompressible stochastic flow in a Euclidean space. We
report on three main results obtained in [8, 9, 10] concerning long time behaviour for a typical realization of the stochastic flow. First, at time t most of the particles are at a distance of order √t away from the origin. Moreover, we prove a Central Limit Theorem for the evolution of a measure carried by the flow, which holds for almost every realization of the flow. Second, we show the existence of a zero measure full Hausdorff dimension set of points, which
escape to infinity at a linear rate. Third, in the 2-dimensional case, we study the set of points visited by the original set by time t. Such a set, when scaled down by the factor of t, has a limiting non random shape.},
  author       = {Kaloshin, Vadim and DOLGOPYAT, D. and KORALOV, L.},
  booktitle    = {XIVth International Congress on Mathematical Physics},
  isbn         = {9789812562012},
  location     = {Lisbon, Portugal},
  pages        = {290--295},
  publisher    = {World Scientific},
  title        = {{Long time behaviour of periodic stochastic flows}},
  doi          = {10.1142/9789812704016_0026},
  year         = {2006},
}

@article{854,
  abstract     = {Phylogenetic relationships between the extinct woolly mammoth (Mammuthus primigenius), and the Asian (Elephas maximus) and African savanna (Loxodonta africana) elephants remain unresolved. Here, we report the sequence of the complete mitochondrial genome (16,842 base pairs) of a woolly mammoth extracted from permafrost-preserved remains from the Pleistocene epoch - the oldest mitochondrial genome sequence determined to date. We demonstrate that well-preserved mitochondrial genome fragments, as long as ∼1,600-1700 base pairs, can be retrieved from pre-Holocene remains of an extinct species. Phylogenetic reconstruction of the Elephantinae clade suggests that M. primigenius and E. maximus are sister species that diverged soon after their common ancestor split from the L. africana lineage. Low nucleotide diversity found between independently determined mitochondrial genomic sequences of woolly mammoths separated geographically and in time suggests that north-eastern Siberia was occupied by a relatively homogeneous population of M. primigenius throughout the late Pleistocene.},
  author       = {Rogaev, Evgeny I and Moliaka, Yuri K and Malyarchuk, Boris A and Fyodor Kondrashov and Derenko, Miroslava V and Chumakov, Ilya M and Grigorenko, Anastasia P},
  journal      = {PLoS Biology},
  number       = {3},
  pages        = {0403 -- 0410},
  publisher    = {Public Library of Science},
  title        = {{Complete mitochondrial genome and phylogeny of pleistocene mammoth Mammuthus primigenius}},
  doi          = {10.1371/journal.pbio.0040073},
  volume       = {4},
  year         = {2006},
}

@article{868,
  abstract     = {Background: The glyoxylate cycle is thought to be present in bacteria, protists, plants, fungi, and nematodes, but not in other Metazoa. However, activity of the glyoxylate cycle enzymes, malate synthase (MS) and isocitrate lyase (ICL), in animal tissues has been reported. In order to clarify the status of the MS and ICL genes in animals and get an insight into their evolution, we undertook a comparative-genomic study. Results: Using sequence similarity searches, we identified MS genes in arthropods, echinoderms, and vertebrates, including platypus and opossum, but not in the numerous sequenced genomes of placental mammals. The regions of the placental mammals' genomes expected to code for malate synthase, as determined by comparison of the gene orders in vertebrate genomes, show clear similarity to the opossum MS sequence but contain stop codons, indicating that the MS gene became a pseudogene in placental mammals. By contrast, the ICL gene is undetectable in animals other than the nematodes that possess a bifunctional, fused ICL-MS gene. Examination of phylogenetic trees of MS and ICL suggests multiple horizontal gene transfer events that probably went in both directions between several bacterial and eukaryotic lineages. The strongest evidence was obtained for the acquisition of the bifunctional ICL-MS gene from an as yet unknown bacterial source with the corresponding operonic organization by the common ancestor of the nematodes. Conclusion: The distribution of the MS and ICL genes in animals suggests that either they encode alternative enzymes of the glyoxylate cycle that are not orthologous to the known MS and ICL or the animal MS acquired a new function that remains to be characterized. Regardless of the ultimate solution to this conundrum, the genes for the glyoxylate cycle enzymes present a remarkable variety of evolutionary events including unusual horizontal gene transfer from bacteria to animals.},
  author       = {Fyodor Kondrashov and Koonin, Eugene V and Morgunov, Igor G and Finogenova, Tatiana V and Kondrashova, Marie N},
  journal      = {Biology Direct},
  publisher    = {BioMed Central},
  title        = {{Evolution of glyoxylate cycle enzymes in Metazoa Evidence of multiple horizontal transfer events and pseudogene formation}},
  doi          = {10.1186/1745-6150-1-31},
  volume       = {1},
  year         = {2006},
}

@article{869,
  abstract     = {The impact of synonymous nucleotide substitutions on fitness in mammals remains controversial. Despite some indications of selective constraint, synonymous sites are often assumed to be neutral, and the rate of their evolution is used as a proxy for mutation rate. We subdivide all sites into four classes in terms of the mutable CpG context, nonCpG, postC, preG, and postCpreG, and compare four-fold synonymous sites and intron sites residing outside transposable elements. The distribution of the rate of evolution across all synonymous sites is trimodal. Rate of evolution at nonCpG synonymous sites, not preceded by C and not followed by G, is ∼10% below that at such intron sites. In contrast, rate of evolution at postCpreG synonymous sites is ∼30% above that at such intron sites. Finally, synonymous and intron postC and preG sites evolve at similar rates. The relationship between the levels of polymorphism at the corresponding synonymous and intron sites is very similar to that between their rates of evolution. Within every class, synonymous sites are occupied by G or C much more often than intron sites, whose nucleotide composition is consistent with neutral mutation-drift equilibrium. These patterns suggest that synonymous sites are under weak selection in favor of G and C, with the average coefficient s∼0.25/Ne∼10-5, where Ne is the effective population size. Such selection decelerates evolution and reduces variability at sites with symmetric mutation, but has the opposite effects at sites where the favored nucleotides are more mutable. The amino-acid composition of proteins dictates that many synonymous sites are CpGprone, which causes them, on average, to evolve faster and to be more polymorphic than intron sites. An average genotype carries ∼107 suboptimal nucleotides at synonymous sites, implying synergistic epistasis in selection against them.},
  author       = {Fyodor Kondrashov and Ogurtsov, Aleksey Yu and Kondrashov, Alexey S},
  journal      = {Journal of Theoretical Biology},
  number       = {4},
  pages        = {616 -- 626},
  publisher    = {Elsevier},
  title        = {{Selection in favor of nucleotides G and C diversifies evolution rates and levels of polymorphism at mammalian synonymous sites}},
  doi          = {10.1016/j.jtbi.2005.10.020},
  volume       = {240},
  year         = {2006},
}

@article{873,
  abstract     = {New genes commonly appear through complete or partial duplications of pre-existing genes. Duplications of long DNA segments are constantly produced by rare mutations, may become fixed in a population by selection or random drift, and are subject to divergent evolution of the paralogous sequences after fixation, although gene conversion can impede this process. New data shed some light on each of these processes. Mutations which involve duplications can occur through at least two different mechanisms, backward strand slippage during DNA replication and unequal crossing-over. The background rate of duplication of a complete gene in humans is 10-9-10-10 per generation, although many genes located within hot-spots of large-scale mutation are duplicated much more often. Many gene duplications affect fitness strongly, and are responsible, through gene dosage effects, for a number of genetic diseases. However, high levels of intrapopulation polymorphism caused by presence or absence of long, gene-containing DNA segments imply that some duplications are not under strong selection. The polymorphism to fixation ratios appear to be approximately the same for gene duplications and for presumably selectively neutral nucleotide substitutions, which, according to the McDonald-Kreitman test, is consistent with selective neutrality of duplications. However, this pattern can also be due to negative selection against most of segregating duplications and positive selection for at least some duplications which become fixed. Patterns in post-fixation evolution of duplicated genes do not easily reveal the causes of fixations. Many gene duplications which became fixed recently in a variety of organisms were positively selected because the increased expression of the corresponding genes was beneficial. The effects of gene dosage provide a unified framework for studying all phases of the life history of a gene duplication. Application of well-known methods of evolutionary genetics to accumulating data on new, polymorphic, and fixed duplication will enhance our understanding of the role of natural selection in the evolution by gene duplication.},
  author       = {Fyodor Kondrashov and Kondrashov, Alexey S},
  journal      = {Journal of Theoretical Biology},
  number       = {2},
  pages        = {141 -- 151},
  publisher    = {Elsevier},
  title        = {{Role of selection in fixation of gene duplications}},
  doi          = {10.1016/j.jtbi.2005.08.033},
  volume       = {239},
  year         = {2006},
}