Statistical potential-based amino acid similarity matrices for aligning distantly related protein sequences

Aligning distantly related protein sequences is a long-standing problem in bioinformatics, and a key for successful protein structure prediction. Its importance is increasing recently in the context of structural genomics projects because more and more experimentally solved structures are available as templates for protein structure modeling. Toward this end, recent structure prediction methods employ profile-profile alignments, and various ways of aligning two profiles have been developed. More fundamentally, a better amino acid similarity matrix can improve a profile itself; thereby resulting in more accurate profile-profile alignments. Here we have developed novel amino acid similarity matrices from knowledge-based amino acid contact potentials. Contact potentials are used because the contact propensity to the other amino acids would be one of the most conserved features of each position of a protein structure. The derived amino acid similarity matrices are tested on benchmark alignments at three different levels, namely, the family, the superfamily, and the fold level. Compared to BLOSUM45 and the other existing matrices, the contact potential-based matrices perform comparably in the family level alignments, but clearly outperform in the fold level alignments. The contact potential-based matrices perform even better when suboptimal alignments are considered. Comparing the matrices themselves with each other revealed that the contact potential-based matrices are very different from BLOSUM45 and the other matrices, indicating that they are located in a different basin in the amino acid similarity matrix space.     

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.     

Describing the organization of dominance relationships by dominance-directed tree method

Methods to describe dominance hierarchies are a key tool in primatology studies. Most current methods are appropriate for analyzing linear and near-linear hierarchies; however, more complex structures are common in primate groups. We propose a method termed "dominance-directed tree." This method is based on graph theory and set theory to analyze dominance relationships in social groups. The method constructs a transitive matrix by imposing transitivity to the dominance matrix and produces a graphical representation of the dominance relationships, which allows an easy visualization of the hierarchical position of the individuals, or subsets of individuals. The method is also able to detect partial and complete hierarchies, and to describe situations in which hierarchical and nonhierarchical principles operate. To illustrate the method, we apply a dominance tree analysis to artificial data and empirical data from a group of Cebus apella.     

Isolation by resistance

Despite growing interest in the effects of landscape heterogeneity on genetic structuring, few tools are available to incorporate data on landscape composition into population genetic studies. Analyses of isolation by distance have typically either assumed spatial homogeneity for convenience or applied theoretically unjustified distance metrics to compensate for heterogeneity. Here I propose the isolation-by-resistance (IBR) model as an alternative for predicting equilibrium genetic structuring in complex landscapes. The model predicts a positive relationship between genetic differentiation and the resistance distance, a distance metric that exploits precise relationships between random walk times and effective resistances in electronic networks. As a predictor of genetic differentiation, the resistance distance is both more theoretically justified and more robust to spatial heterogeneity than Euclidean or least cost path-based distance measures. Moreover, the metric can be applied with a wide range of data inputs, including coarse-scale range maps, simple maps of habitat and nonhabitat within a species' range, or complex spatial datasets with habitats and barriers of differing qualities. The IBR model thus provides a flexible and efficient tool to account for habitat heterogeneity in studies of isolation by distance, improve understanding of how landscape characteristics affect genetic structuring, and predict genetic and evolutionary consequences of landscape change.     

From components to regulatory motifs in signalling networks.

The developments in biochemistry and molecular biology over the past 30 years have produced an impressive parts list of cellular components. It has become increasingly clear that we need to understand how components come together to form systems. One area where this approach has been growing is cell signalling research. Here, instead of focusing on individual or small groups of signalling proteins, researchers are now using a more holistic perspective. This approach attempts to view how many components are working together in concert to process information and to orchestrate cellular phenotypic changes. Additionally, the advancements in experimental techniques to measure and visualize many cellular components at once gradually grow in diversity and accuracy. The multivariate data, produced by experiments, introduce new and exciting challenges for computational biologists, who develop models of cellular systems made up of interacting cellular components. The integration of high-throughput experimental results and information from legacy literature is expected to produce computational models that would rapidly enhance our understanding of the detail workings of mammalian cells.     

Co-localisation of host plant resistance QTLs affecting the performance and feeding behaviour of the aphid Myzus persicae in the peach tree

The architecture and action of quantitative trait loci (QTL) contributing to plant resistance mechanisms against aphids, the largest group of phloem-feeding insects, are not well understood. Comparative mapping of several components of resistance to the green peach aphid (Myzus persicae) was undertaken in Prunus davidiana, a wild species related to peach. An interspecific F(1) population of Prunus persica var. Summergrand × P. davidiana clone P1908 was scored for resistance (aphid colony development and foliar damage) and 17 aphid feeding behaviour traits monitored by means of the electrical penetration graph technique. Seven resistance QTLs were detected, individually explaining 6.1-43.1% of the phenotypic variation. Consistency was shown over several trials. Nine QTLs affecting aphid feeding behaviour were identified. All resistance QTLs except one co-located with QTLs underlying aphid feeding behaviour. A P. davidiana resistance allele at the major QTL was associated with drastic reductions in phloem sap ingestion by aphids, suggesting a phloem-based resistance mechanism. Resistance was also positively correlated with aphid salivation into sieve elements, suggesting an insect response to restore the appropriate conditions for ingestion after phloem occlusion. No significant QTL was found for traits characterising aphid mouthpart activity in plant tissues other than phloem vessels. Two QTLs with effects on aphid feeding behaviour but without effect on resistance were identified. SSR markers linked to the main QTLs involved in resistance are of potential use in marker-assisted selection for aphid resistance. Linking our results with the recent sequencing of the peach genome may help clarify the physiological resistance mechanisms.     

Identification of significant pathways in gastric cancer based on protein-protein interaction networks and cluster analysis

Gastric cancer is one of the most common and lethal cancers worldwide. However, despite its clinical importance, the regulatory mechanisms involved in the aggressiveness of this cancer are still poorly understood. A better understanding of the biology, genetics and molecular mechanisms of gastric cancer would be useful in developing novel targeted approaches for treating this disease. In this study we used protein-protein interaction networks and cluster analysis to comprehensively investigate the cellular pathways involved in gastric cancer. A primary immunodeficiency pathway, focal adhesion, ECM-receptor interactions and the metabolism of xenobiotics by cytochrome P450 were identified as four important pathways associated with the progression of gastric cancer. The genes in these pathways, e.g., ZAP70, IGLL1, CD79A, COL6A3, COL3A1, COL1A1, CYP2C18 and CYP2C9, may be considered as potential therapeutic targets for gastric cancer.     

Linux与人类代谢的自相似性实证研究

对现实世界复杂网络的自相似性进行实证分析是当前该领域的一个热点问题。文章首先介绍了复杂网络自相似性的基本概念,随后阐述了自相似指数及其计算方法盒覆盖算法的基本原理和方法,最后对Linux与人类代谢这两种不同类型的复杂系统进行自相似性实证研究。研究结果表明,它们都是自相似的。     

The influence of social structure on the propagation of social information in artificial primate groups: a graph-based simulation approach

Observations of primate groups have shown that social learning can lead to the development of temporal stable traditions or even proto-culture. The social structure of primate groups is highly diverse and it has been proposed that differences in the group structure shall influence the patterns of social information transmission. While empirical studies have mainly focused on the psychological mechanisms of social learning in individuals, the phenomenon of information propagation within the group has received relatively little attention. This might be due to the fact that formal theories that allow actual testing have not been formulated, or were kept too simple, ignoring the social dynamics of multi-agent societies. We want to propose a network approach to social information transmission that (1) preserves the complexity of the social structure of primate groups and (2) allows direct application to empirical data. Results from simulation experiments with artificial group structures confirm that association patterns of group-members influence the expected speed of information transmission during the propagation process. Introducing a forgetting rate shows that under certain conditions the proportion of informed individuals will reach a stable rate in some systems while it will drop to zero in others. This suggests that the likelihood to observe temporal stable traditions shall differ between social systems with different structure.