Accelerated evolution of the pituitary adenylate cyclase-activating polypeptide precursor gene during human origin

Pituitary adenylate cyclase-activating polypeptide (PACAP) is a neuropeptide abundantly expressed in the central nervous system and involved in regulating neurogenesis and neuronal signal transduction. The amino acid sequence of PACAP is extremely conserved across vertebrate species, indicating a strong functional constraint during the course of evolution. However, through comparative sequence analysis, we demonstrated that the PACAP precursor gene underwent an accelerated evolution in the human lineage since the divergence from chimpanzees, and the amino acid substitution rate in humans is at least seven times faster than that in other mammal species resulting from strong Darwinian positive selection. Eleven human-specific amino acid changes were identified in the PACAP precursors, which are conserved from murine to African apes. Protein structural analysis suggested that a putative novel Deuropeptide might have originated during human evolution and functioned in the human brain. Our data suggested that the PACAP precursor gene underwent adaptive changes during human origin and may have contributed to the formation of human cognition.

Characterization and Comparison of the Tissue-Related Modules in Human and Mouse

Background: Due to the advances of high throughput technology and data-collection approaches, we are now in an unprecedented position to understand the evolution of organisms. Great efforts have characterized many individual genes responsible for the interspecies divergence, yet little is known about the genome-wide divergence at a higher level. Modules, serving as the building blocks and operational units of biological systems, provide more information than individual genes. Hence, the comparative analysis between species at the module level would shed more light on the mechanisms underlying the evolution of organisms than the traditional comparative genomics approaches. Results: We systematically identified the tissue-related modules using the iterative signature algorithm (ISA), and we detected 52 and 65 modules in the human and mouse genomes, respectively. The gene expression patterns indicate that all of these predicted modules have a high possibility of serving as real biological modules. In addition, we defined a novel quantity, "total constraint intensity,'' a proxy of multiple constraints (of co-regulated genes and tissues where the co-regulation occurs) on the evolution of genes in module context. We demonstrate that the evolutionary rate of a gene is negatively correlated with its total constraint intensity. Furthermore, there are modules coding the same essential biological processes, while their gene contents have diverged extensively between human and mouse. Conclusions: Our results suggest that unlike the composition of module, which exhibits a great difference between human and mouse, the functional organization of the corresponding modules may evolve in a more conservative manner. Most importantly, our findings imply that similar biological processes can be carried out by different sets of genes from human and mouse, therefore, the functional data of individual genes from mouse may not apply to human in certain occasions.

The complete mitochondrial genomes of two species from Sinocyclocheilus (Cypriniformes: Cyprinidae) and a phylogenetic analysis within Cyprininae

We determined the complete mitochondrial DNA sequences for two species of surface- and cave-dwelling-cyprinid fishes, Sinocyclocheilus grahami and S. altishoulderus. Sequence comparison of 13 protein-coding genes shows that the mutation pattern of each single gene is quite similar to those of other vertebrate animal species. Analysis of the ratios of Ka/Ks at these loci between Sinocyclocheilus and two other cyprinid species (Cyprinus carpio and Procypris rabaudi) show that Ka/Ks ratios are differed, consistent with purifying selection and variation in functional constraint among genes. Bayesian analysis and maximum likelihood analysis of the concatenated mitochondrial protein sequences for 14 cyprinid taxa support the monophyly of the family Cyprininae, and further confirm the monophyly of the genus Sinocyclocheilus. The two Sinocyclocheilus species fall within the Cyprinion-Onychostoma lineage, including Cyprinus, Carassius, and Procypris, rather than among the Barbinae, as previously suggested on morphological grounds.

Adaptive Evolution of Digestive RNASE1 Genes in Leaf-Eating Monkeys Revisited: New Insights from Ten Additional Colobines

Pancreatic RNase genes implicated in the adaptation of the colobine monkeys to leaf eating have long intrigued evolutionary biologists since the identification of a duplicated RNASE1 gene with enhanced digestive efficiencies in Pygathrix nemaeus. The recent emergence of two contrasting hypotheses, that is, independent duplication and one-duplication event hypotheses, make it into focus again. Current understanding of Colobine RNASE1 gene evolution of colobine monkeys largely depends on the analyses of few colobine species. The present study with more intensive taxonomic and character sampling not only provides a clearer picture of Colobine RNASE1 gene evolution but also allows to have a more thorough understanding about the molecular basis underlying the adaptation of Colobinae to the unique leaf-feeding lifestyle. The present broader and detailed phylogenetic analyses yielded two important findings: 1) All trees based on the analyses of coding, noncoding, and both regions provided consistent evidence, indicating RNASE1 duplication occurred after Asian and African colobines speciation, that is, independent duplication hypothesis; 2) No obvious evidence of gene conversion in RNASE1 gene was found, favoring independent evolution of Colobine RNASE1 gene duplicates. The conclusion drawn from previous studies that gene conversion has played a significant role in the evolution of Colobine RNASE1 was not supported. Our selective constraint analyses also provided interesting insights, with significant evidence of positive selection detected on ancestor lineages leading to duplicated gene copies. The identification of a handful of new adaptive sites and amino acid changes that have not been characterized previously also provide a necessary foundation for further experimental investigations of RNASE1 functional evolution in Colobinae.

Origin and evolution of new exons in the rodent zinc finger protein 39 gene

The origin of new structures and functions is an important process in evolution. In the past decades, we have obtained some preliminary knowledge of the origin and evolution of new genes. However, as the basic unit of genes, the origin and evolution of exons remain unclear. Because young exons retain the footprints of origination, they can be good materials for studying origin and evolution of new exons. In this paper, we report two young exons in a zinc finger protein gene of rodents. Since they are unique sequences in mouse and rat genome and no homologous sequences were found in the orthologous genes of human and pig, the young exons might originate after the divergence of primates and rodents through exonization of intronic sequences. Strong positive selection was detected in the new exons between mouse and rat, suggesting that these exons have undergone significant functional divergence after the separation of the two species. On the other hand, population genetics data of mouse demonstrate that the new exons have been subject to functional constraint, indicating an important function of the new exons in mouse. Functional analyses suggest that these new exons encode a nuclear localization signal peptide, which may mediate new ways of nuclear protein transport. To our knowledge, this is the first example of the origin and evolution of young exons.

Recombination Yet Inefficient Selection along the Drosophila melanogaster Subgroup's Fourth Chromosome

A central goal of evolutionary genetics is an understanding of the forces responsible for the observed variation, both within and between species. Theoretical and empirical work have demonstrated that genetic recombination contributes to this variation by breaking down linkage between nucleotide sites, thus allowing them to behave independently and for selective forces to act efficiently on them. The Drosophila fourth chromosome, which is believed to experience no-or very low-rates of recombination has been an important model for investigating these effects. Despite previous efforts, central questions regarding the extent of recombination and the predominant modes of selection acting on it remain open. In order to more comprehensively test hypotheses regarding recombination and its potential influence on selection along the fourth chromosome, we have resequenced regions from most of its genes from Drosophila melanogaster, D. simulans, and D. yakuba. These data, along with available outgroup sequence, demonstrate that recombination is low but significantly greater than zero for the three species. Despite there being recombination, there is strong evidence that its frequency is low enough to have rendered selection relatively inefficient. The signatures of relaxed constraint can be detected at both the level of polymorphism and divergence.

Small SiGe quantum dots obtained by excimer laser annealing

In this paper, we obtain SiGe quantum dots with the diameters and density of 15-20 nm and 1.8 x 10(11) cm(-2), respectively, by 193 nm excimer laser annealing of Si0.77Ge0.23 strained films. Under the excimer laser annealing, only surface atoms diffusion happens. From the detailed statistical information about the size and shape of the quantum dots with different annealing time, it is shown that the as-grown self-assembled quantum dots, especially the {105}-faceted dots, are not stable and disappear before the appearance of the laser-induced quantum dots. Based on the calculation of surface energy and surface chemical potential, we show that the {103}-faceted as-grown self-assembled quantum dots are more heavily strained than the {105}-faceted ones, and the heavy strain in the dot can decrease the surface energy of the dot facets. The formation of the laser-induced quantum dots, which is also with heavy strain, is attributed to kinetic constraint. (c) 2008 Elsevier B.V. All rights reserved.

Formal specification and refinement of a safe train control function

Motivated by the design and development challenges of the BART case study, an approach for developing and analyzing a formal model for reactive systems is presented. The approach makes use of a domain specific language for specifying control algorithms able to satisfy competing properties such as safety and optimality. The domain language, called SPC, offers several key abstractions such as the state, the profile, and the constraint to facilitate problem specification. Using a high-level program transformation system such as HATS being developed at the University of Nebraska at Omaha, specifications in this modelling language can be transformed to ML code. The resulting executable specification can be further refined by applying generic transformations to the abstractions provided by the domain language. Problem dependent transformations utilizing the domain specific knowledge and properties may also be applied. The result is a significantly more efficient implementation which can be used for simulation and gaining deeper insight into design decisions and various control policies. The correctness of transformations can be established using a rewrite-rule based induction theorem prover Rewrite Rule Laboratory developed at the University of New Mexico.

基于约束的主动规则终止性分析

终止性是主动规则所需的最重要的一个性质,但规则的终止性检查通常是不可判定的.已有的静态分析方法非常保守,SQL3标准也没有提供保证终止的机制,所以商业数据库限制规则级联触发的最大次数确保终止.由于规则可看成数据库状态转换器,而约束能够表示所有可能的数据库状态,基于约束表示的数据库状态及约束求解,模拟规则处理,可得到更精确的终止性结论.

约束求解与优化技术的结合

提出了将混合约束问题转化为混合整数规划问题的方法.用约束求解方法及混合整数规划方法共同求解混合约束问题可以令二者相互借鉴,从而促进二者求解技术的进一步发展.同时,由混合约束问题转化而来的混合整数规划问题也可作为求解混合整数规划问题的测试问题（benchmarks）.

约束问题求解

约束问题的求解涉及到人工智能、运筹学、计算机科学等领域．它的应用范围也极为广泛,包括计算机科学、控制科学、生物学等方面．本文对其发展历史、所要求解的问题以及它的基本方法等问题进行了综述．

一阶逻辑中约束求解的局部搜索法

以一阶谓词逻辑为基础，讨论约束满足问题．着重研究一阶逻辑公式可满足性的局部搜索法，并与命题逻辑中的可满足性过程加以比较．以皇后问题和哈密顿回路问题为例，说明基于一阶逻辑的方法能处理较大的问题实例．

automated test case generation for the stress testing of multimedia systems

With the advancement in network bandwidth and computing power, multimedia systems have become a popular means for information delivery. However, general principles of system testing cannot be directly applied to testing of multimedia systems on account of their stringent temporal and synchronization requirements. In particular, few studies have been made on the stress testing of multimedia systems with respect to their temporal requirements under resource saturation. Stress testing is important because erroneous behavior is most likely to occur under resource saturation. This paper presents an automatable method of test case generation for the stress testing of multimedia systems. It adapts constraint solving techniques to generate test cases that lead to potential resource saturation in a multimedia system. Coverage of the test cases is defined upon the reachability graph of a multimedia system. The proposed stress testing technique is supported by tools and has been successfully applied to a real-life commercial multimedia system. Although our technique focuses on the stress testing of multimedia systems, the underlying issues and concepts are applicable to other types of real-time systems.

constructing finite algebras with falcon

The generation of models and counterexamples is an important form of reasoning. In this paper, we give a formal account of a system, called FALCON, for constructing finite algebras from given equational axioms. The abstract algorithms, as well as some implementation details and sample applications, are presented. The generation of finite models is viewed as a constraint satisfaction problem, with ground instances of the axioms as constraints. One feature of the system is that it employs a very simple technique, called the least number heuristic, to eliminate isomorphic (partial) models, thus reducing the size of the search space. The correctness of the heuristic is proved. Some experimental data are given to show the performance and applications of the system.

SAT和DSOLS问题的研究

约束可满足性问题（Constraint Satisfaction Problem,CSP）是在人工智能领域被广泛研究的一类问题。对CSP问题的研究有两种重要的思路：一种思路是用统一的模型来表示CSP，然后用针对这个统一模型的通用工具进行求解；另外一种思路是针对不同的CSP问题开发专门工具，设计不同的算法和数据结构来求解。 本文研究了两个CSP问题：SAT(SATisfiability problem)和DSOLS(DoublySelf-Orthogonal Latin Squares)。CSP可以方便的转换为SAT来求解，因此对SAT的研究对很多问题具有重大意义。本文介绍了当前流行的SAT solver的一些技术，也提出一种新的搜索空间裁剪策略Local Lemma。DSOLS是一种具有特定性质的拉丁方，本文对它的研究不仅仅因为它的应用意义。更重要的是它作为一个特定的CSP问题，可以用来比较通用工具和专门工具的优劣。本文尝试了把DSOLS转化为SAT求解，也试过用一般CSP的思路来求解，最后提出了一种针对性的高效算法并开发了一个专门工具DSOLver，用这个工具证明了一个开放问题：DSOLS(10)不存在。