图论在RNA二级结构中的应用

图论是以图为研究对象的数学分支,是一门研究事物对象在图表示法中的特征与性质的学科。鉴于RNA二级结构在功能基因组研究中的重要地位,已发展了用二维图解表示法描述RNA二级结构。文章介绍了用于RNA二级结构图解表示法的两种图,即树图和对偶图的构造规则。并在树图表示基础上产生Laplacian矩阵和相应本征值谱。以有害突变预测和类RNA模体设计的例子,说明图论在RNA二级结构中的应用,同时对可能存在的一些问题做了讨论。     

Prediction of Protein Allosteric Signalling Pathways and Functional Residues Through Paths of Optimised Propensity

Allostery commonly refers to the mechanism that regulates protein activity through the binding of a molecule at a different, usually distal, site from the orthosteric site. The omnipresence of allosteric regulation in nature and its potential for drug design and screening render the study of allostery invaluable. Nevertheless, challenges remain as few computational methods are available to effectively predict allosteric sites, identify signalling pathways involved in allostery, or to aid with the design of suitable molecules targeting such sites. Recently, bond-to-bond propensity analysis has been shown successful at identifying allosteric sites for a large and diverse group of proteins from knowledge of the orthosteric sites and its ligands alone by using network analysis applied to energy-weighted atomistic protein graphs. To address the identification of signalling pathways, we propose here a method to compute and score paths of optimised propensity that link the orthosteric site with the identified allosteric sites, and identifies crucial residues that contribute to those paths. We showcase the approach with three well-studied allosteric proteins: h-Ras, caspase-1, and 3-phosphoinositide-dependent kinase-1 (PDK1). Key residues in both orthosteric and allosteric sites were identified and showed agreement with experimental results, and pivotal signalling residues along the pathway were also revealed, thus providing alternative targets for drug design. By using the computed path scores, we were also able to differentiate the activity of different allosteric modulators.     

基于图论的景观图表达、分析及应用

景观结构和空间格局一直是景观生态学的核心问题,图论的应用为景观格局的分析提供了一种研究框架,基于图论的景观图逐渐被应用于生物多样性保护的连通性建模和景观规划的决策支持研究,景观图的表达、分析和应用已成为保护生物学和景观生态学研究的热点。本文首先介绍了景观图的图论基础,在Scopus数据库的基础上,检索了1993—2019年在标题、摘要和关键词中出现 “landscape graph”、“connectivity”和“network”词汇的257篇已发表的期刊论文。从年发文量、来源期刊、研究区域、研究机构、景观类型等方面分析了该领域的研究进展和发展趋势。分析发现,2017年之前,发表的期刊论文数量整体呈上升趋势,2017年之后年发文量逐年下降;主要研究力量集中在美国、西班牙、法国、加拿大和中国,发文量占到86.8%。大部分研究成果发表在“Landscape Ecology”、“Landscape and Urban Planning”和“Biological Conservation”期刊上。在研究内容上,景观图表达主要包括点的定义、边的度量和景观的模拟3方面,景观图分析研究包括分析指数、景观图划分两方面。我们重点关注了景观图在生物多样性保护、景观(生态网络)规划和管理、景观影响评价等科学与实践中的应用。基于图论的景观图通过帮助理解景观连通性变化、动物行为和栖息地保护,影响着保护科学和规划实践者。图论对保护科学和规划的影响来自于丰富的理论基础和成熟的研究方法,基于图论的景观图为景观结构和格局的生态学理解提供了跳板,并将继续成为全球研究人员和实践者的重要工具。     

用Ansys软件对矩形腔流体的分析

利用有限元分析软件Ansys对离体心血管循环系统中的层流装置(矩形腔)内的流体进行分析，显示流体的速度向量图、压力分布图，用于研究血动力学因素对人工培养的内皮细胞生物学特征性影响。     

模糊图论在山西植被区划中的应用

本文用模糊图论的最大树方法对山西植被区划进行了数量分类研究,将山西植被分为2个植被地带,6个植被地区,17个植被小区。与在植物群落学中应用的模糊聚类分析和其它方法相比,模糊图论的最大树方法直接依模糊相似系数矩阵得到树状图,从而避免了相似系数矩阵复杂的合成运算,而分类结果不仅更具直观性,而且也是令人满意的。我们认为模糊图论应用于植被区划是合适的。     

Effect of epistasis and linkage on fixation probability in three-locus models: an ancestral recombination-selection graph approach

We study the probability of ultimate fixation of a single new mutant arising in an individual chosen at random at a locus linked to two other loci carrying previously arisen mutations. This is done using the Ancestral Recombination-Selection Graph (ARSG) in a finite population in the limit of a large population size, which is also known as the Ancestral Influence Graph (AIG). An analytical expansion of the fixation probability with respect to population-scaled recombination rates and selection intensities is obtained. The coefficients of the expansion are expressed in terms of the initial state of the population and the epistatic interactions among the selected loci. Under the assumption of weak selection at tightly linked loci, the sign of the leading term, which depends on the signs of epistasis and initial linkage disequilibrium, determines whether an increase in recombination rates increases the chance of ultimate fixation of the new mutant. If mutants are advantageous, this is the case when epistasis is positive or null and the initial linkage disequilibrium is negative, which is an expected state in a finite population under directional selection. Moreover, this is also the case for a neutral mutant modifier coding for higher recombination rates if the same conditions hold at the selected loci. Under the same conditions, deleterious mutants are disfavored for ultimate fixation and neutral modifiers for higher recombination rates still favored. The recombination rates between the modifier locus and the selected loci do not come into play in the leading terms of the approximation for the fixation probability, but they do in higher-order terms.     

Allosteric Hotspots in the Main Protease of SARS-CoV-2

Inhibiting the main protease of SARS-CoV-2 is of great interest in tackling the COVID-19 pandemic caused by the virus. Most efforts have been centred on inhibiting the binding site of the enzyme. However, considering allosteric sites, distant from the active or orthosteric site, broadens the search space for drug candidates and confers the advantages of allosteric drug targeting. Here, we report the allosteric communication pathways in the main protease dimer by using two novel fully atomistic graph-theoretical methods: Bond-to-bond propensity, which has been previously successful in identifying allosteric sites in extensive benchmark data sets without a priori knowledge, and Markov transient analysis, which has previously aided in finding novel drug targets in catalytic protein families. Using statistical bootstrapping, we score the highest ranking sites against random sites at similar distances, and we identify four statistically significant putative allosteric sites as good candidates for alternative drug targeting.     

A taxonomy of application scheduling tools for high performance cluster computing

Application scheduling plays an important role in high-performance cluster computing. Application scheduling can be classified as job scheduling and task scheduling. This paper presents a survey on the software tools for the graph-based scheduling on cluster systems with the focus on task scheduling. The tasks of a parallel or distributed application can be properly scheduled onto multi-processors in order to optimize the performance of the program (e.g., execution time or resource utilization). In general, scheduling algorithms are designed based on the notion of task graph that represents the relationship of parallel tasks. The scheduling algorithms map the nodes of a graph to the processors in order to minimize overall execution time. Although many scheduling algorithms have been proposed in the literature, surprisingly not many practical tools can be found in practical use. After discussing the fundamental scheduling techniques, we propose a framework and taxonomy for the scheduling tools on clusters. Using this framework, the features of existing scheduling tools are analyzed and compared. We also discuss the important issues in improving the usability of the scheduling tools. This work is supported by the Hong Kong Polytechnic University under grant H-ZJ80 and by NASA Ames Research Center by a cooperative grant agreement with the University of Texas at Arlington. Jiannong Cao received the BSc degree in computer science from Nanjing University, Nanjing, China in 1982, and the MSc and the Ph.D degrees in computer science from Washington State University, Pullman, WA, USA, in 1986 and 1990 respectively. He is currently an associate professor in Department of Computing at the Hong Kong Polytechnic University, Hong Kong. He is also the director of the Internet and Mobile Computing Lab in the department. He was on the faculty of computer science at James Cook University and University of Adelaide in Australia, and City University of Hong Kong. His research interests include parallel and distributed computing, networking, mobile computing, fault tolerance, and distributed software architecture and tools. He has published over 120 technical papers in the above areas. He has served as a member of editorial boards of several international journals, a reviewer for international journals/conference proceedings, and also as an organizing/programme committee member for many international conferences. Dr. Cao is a member of the IEEE Computer Society, the IEEE Communication Society, IEEE, and ACM. He is also a member of the IEEE Technical Committee on Distributed Processing, IEEE Technical Committee on Parallel Processing, IEEE Technical Committee on Fault Tolerant Computing, and Computer Architecture Professional Committee of the China Computer Federation. Alvin Chan is currently an assistant professor at the Hong Kong Polytechnic University. He graduated from the University of New South Wales with a Ph.D. degree in 1995 and was subsequently employed as a Research Scientist by the CSIRO, Australia. From 1997 to 1998, he was employed by the Centre for Wireless Communications, National University of Singapore as a Program Manager. Dr. Chan is one of the founding members and director of a university spin-off company, Information Access Technology Limited. He is an active consultant and has been providing consultancy services to both local and overseas companies. His research interests include mobile computing, context-aware computing and smart card applications. Yudong Sun received the B.S. and M.S. degrees from Shanghai Jiao Tong University, China. He received Ph.D. degree from the University of Hong Kong in 2002, all in computer science. From 1988 to 1996, he was among the teaching staff in Department of Computer Science and Engineering at Shanghai Jiao Tong University. From 2002 to 2003, he held a research position at the Hong Kong Polytechnic University. At present, he is a Research Associate in School of Computing Science at University of Newcastle upon Tyne, UK. His research interests include parallel and distributed computing, Web services, Grid computing, and bioinformatics. Sajal K. Das is currently a Professor of Computer Science and Engineering and the Founding Director of the Center for Research in Wireless Mobility and Networking (CReWMaN) at the University of Texas at Arlington. His current research interests include resource and mobility management in wireless networks, mobile and pervasive computing, sensor networks, mobile internet, parallel processing, and grid computing. He has published over 250 research papers, and holds four US patents in wireless mobile networks. He received the Best Paper Awards in ACM MobiCom’99, ICOIN-16, ACM, MSWiM’00 and ACM/IEEE PADS’97. Dr. Das serves on the Editorial Boards of IEEE Transactions on Mobile Computing, ACM/Kluwer Wireless Networks, Parallel Processing Letters, Journal of Parallel Algorithms and Applications. He served as General Chair of IEEE PerCom’04, IWDC’04, MASCOTS’02 ACM WoWMoM’00-02; General Vice Chair of IEEE PerCom’03, ACM MobiCom’00 and IEEE HiPC’00-01; Program Chair of IWDC’02, WoWMoM’98-99; TPC Vice Chair of ICPADS’02; and as TPC member of numerous IEEE and ACM conferences. Minyi Guo received his Ph.D. degree in information science from University of Tsukuba, Japan in 1998. From 1998 to 2000, Dr. Guo had been a research scientist of NEC Soft, Ltd. Japan. He is currently a professor at the Department of Computer Software, The University of Aizu, Japan. From 2001 to 2003, he was a visiting professor of Georgia State University, USA, Hong Kong Polytechnic University, Hong Kong. Dr. Guo has served as general chair, program committee or organizing committee chair for many international conferences, and delivered more than 20 invited talks in USA, Australia, China, and Japan. He is the editor-in-chief of the Journal of Embedded Systems. He is also in editorial board of International Journal of High Performance Computing and Networking, Journal of Embedded Computing, Journal of Parallel and Distributed Scientific and Engineering Computing, and International Journal of Computer and Applications. Dr. Guo’s research interests include parallel and distributed processing, parallelizing compilers, data parallel languages, data mining, molecular computing and software engineering. He is a member of the ACM, IEEE, IEEE Computer Society, and IEICE. He is listed in Marquis Who’s Who in Science and Engineering.     

Edge-count probabilities for the identification of local protein communities and their organization

We present a computational approach based on a local search strategy that discovers sets of proteins that preferentially interact with each other. Such sets are referred to as protein communities and are likely to represent functional modules. Preferential interaction between module members is quantified via an analytical framework based on a network null model known as the random graph with given expected degrees. Based on this framework, the concept of local protein community is generalized to that of community of communities. Protein communities and higher-level structures are extracted from two yeast protein interaction data sets and a network of published interactions between human proteins. The high level structures obtained with the human network correspond to broad biological concepts such as signal transduction, regulation of gene expression, and intercellular communication. Many of the obtained human communities are enriched, in a statistically significant way, for proteins having no clear orthologs in lower organisms. This indicates that the extracted modules are quite coherent in terms of function.     

A Theoretical Graph Method for Search and Analysis of Critical Phenomena in Biochemical Systems. I. Graphical Rules for Detecting Oscillators

Sufficient conditions for existence of concentration oscillations of components of complex reactions are considered on the basis of graph theory. Graphical rules were developed for detecting oscillators in kinetic schemes of complex biochemical systems. The main types of topology and principles of construction of kinetic schemes of oscillators containing two, three, and four substances are considered. The resulting oscillators might be a part of the biochemical systems of the n-th order. Under certain conditions they were found to be capable of generating oscillations of the system components.     

On adaptation: A reduction of the Kauffman-Levin model to a problem in graph theory and its consequences

It is shown that complex adaptations are best modelled as discrete processes represented on directed weighted graphs. Such a representation captures the idea that problems of adaptation in evolutionary biology are problems in a discrete space, something that the conventional representations using continuous adaptive landscapes does not. Further, this representation allows the utilization of well-known algorithms for the computation of several biologically interesting results such as the accessibility of one allele from another by a specified number of point mutations, the accessibility of alleles at a local maximum of fitness, the accessibility of the allele with the globally maximum fitness, etc. A reduction of a model due to Kauffman and Levin to such a representation is explicitly carried out and it is shown how this reduction clarifies the biological questions that are of interest.Thanks are due to William Wimsatt, James F. Crow, and the referees for Biology and Philosophy for comments on an earlier version of this paper. Remarks by members of the audience, especially Abner Shimony, of a seminar at Boston University, February 19, 1988, were also very helpful. The diagrams were prepared with the assistance of Tracy Lubas.     

A Theoretical Graph Method for Search and Analysis of Critical Phenomena in Biochemical Systems. II. Kinetic Models of Biochemical Oscillators Including Two and Three Substances

Four kinetic models of hypothetical complex reactions containing minimal two-substance or three-substance oscillators were constructed on the basis of the graphical rules suggested in the preceding work. The kinetic models are thought to be a part of one of four general biochemical systems: 1) system of mutual protein phosphorylation/dephosphorylation; 2) autophosphorylation of multisubunit protein; 3) association/dissociation of proteins or protein-containing structures during protein–protein or protein–ligand interaction; and 4) two-substrate enzymatic reaction with substrate inhibition by one substrate. Graphical rules of oscillator association with surrounding medium were considered. The graphical criteria of the oscillation generator elimination and criteria of oscillation damping were obtained. Both damped and undamped oscillations of reaction components were obtained by numerical integration of the mathematical models of these reactions. The areas of changes of model parameters and variables, within which the oscillations exist, were found.     

Ancestral processes for non-neutral models of complex diseases

We consider non-neutral models for unlinked loci, where the fitness of a chromosome or individual is not multiplicative across loci. Such models are suitable for many complex diseases, where there are gene-interactions. We derive a genealogical process for such models, called the complex selection graph (CSG). This coalescent-type process is related to the ancestral selection graph, and is derived from the ancestral influence graph by considering the limit as the recombination rate between loci gets large. We analyse the CSG both theoretically and via simulation. The main results are that the gene-interactions do not produce linkage disequilibrium, but do produce dependencies in allele frequencies between loci. For small selection rates, the distributions of the genealogy and the allele frequencies at a single locus are well-approximated by their distributions under a single locus model, where the fitness of each allele is the average of the true fitnesses of that allele with respect to the distribution of alleles at other loci.     

A probabilistic approach to compact steady-state kinetic equations for enzymic reactions

We describe a method for deriving kinetic equations based on the simplification of a complex graphical scheme of steady-state enzymic reactions to one that is comprised of an unbranched pathway. It entails compressing unbranched multi-step sequences into one step, and fusing some graph nodes into a single node. The final form of the equations is compact and well structured, and it simplifies the choice of independent kinetic parameters. The approach is illustrated by an analysis of representative two- and three-substrate reactions.     

Simplest Kinetic Schemes for Biochemical Oscillators

The topological structure of the simplest critical fragments in biochemical systems has been characterized. The conditions are considered where the critical fragments induce oscillations of the concentrations of the system participants. To illustrate, three biochemical systems (transport of ions through a membrane, protein phosphorylation, and two-substrate reaction) are discussed. The kinetic schemes of these systems contain one of the discovered critical fragments. Relaxation oscillations of the concentrations of the system participants were demonstrated using the numerical integration method.     

Visualizing fitness landscapes

Fitness landscapes are a classical concept for thinking about the relationship between genotype and fitness. However, because the space of genotypes is typically high-dimensional, the structure of fitness landscapes can be difficult to understand and the heuristic approach of thinking about fitness landscapes as low-dimensional, continuous surfaces may be misleading. Here, I present a rigorous method for creating low-dimensional representations of fitness landscapes. The basic idea is to plot the genotypes in a manner that reflects the ease or difficulty of evolving from one genotype to another. Such a layout can be constructed using the eigenvectors of the transition matrix describing the evolution of a population on the fitness landscape when mutation is weak. In addition, the eigendecomposition of this transition matrix provides a new, high-level view of evolution on a fitness landscape. I demonstrate these techniques by visualizing the fitness landscape for selection for the amino acid serine and by visualizing a neutral network derived from the RNA secondary structure genotype-phenotype map.     

Simple critical schemes in non-autocatalytic systems of biochemical reactions

Kinetic behavior of various reaction systems consisting of three compounds was analyzed in order to find and study the origin of multiple-steady-state and auto-oscillatory behavior in biochemical systems. More than 3000 such reactions were considered. Using the bigraph method, six simple critical reaction schemes were found. It is shown that the presence of these fragments in the composition of more complex biochemical systems may be the origin of the multiple steady-states and autooscillations.