Species coexistence, intransitivity, and topological variation in competitive tournaments

Competitive intransitivity occurs when species’ competitive abilities cannot be listed in a strict hierarchy, but rather form competitive loops, as in the game ‘Rock-Paper-Scissors’. Indices are useful for summarizing intransitivity in communities; however, as with most indices, a great deal of information is compressed into single number. So while recent ecological theory, experiments, and natural history observations demonstrate that competitive intransitivity can promote species coexistence, the consequence of variation in the ‘topology’ of competitive interactions that is not accounted for by intransitivity indices is much less well understood. We use a continuous analytical model and two complementary discrete lattice models (one spatially explicit, the other aspatial) to demonstrate that such variation does indeed greatly affect species coexistence. Specifically, we show that although intransitivity indices are good at capturing broad patterns of coexistence, communities with different levels of intransitivity can have equal coexistence, and communities with equal intransitivity can have different coexistence, due to underlying variation in competitive network topology.     

Finding paths in a labyrinth based on reaction-diffusion media.

During the past few decades, many proposals were made on how to take an effective solution for finding a path in a labyrinth, one of the most well known problems of high computational complexity inherent in information processing by biomolecular and biological entities. In particular, attempts were made to use a technique attractive enough for solving this problem based on wave processes in reaction-diffusion media. Trigger waves in reaction diffusion systems spread simultaneously through all paths of the labyrinth in a highly parallel mode. Regretfully, the velocity of these waves is extremely low which gave no way for the practical implementation of this technique until now. An effective 'hardware' system was designed which was capable of finding a path in a labyrinth using fast phase waves. Three principal points were assumed as a basis for this design, i.e. (1) hybrid architecture that combined an information processing reaction-diffusion medium which performs operations of high computational complexity with a digital computer carrying out supplementary image processing operations; (2) light-sensitive information processing media of Belousov-Zhabotinsky type that enables the simulation of the labyrinth and spreading wave evolution by their images stored in the medium and reduces the problem to the image processing operations; (3) fast light-induced phase wave processes that spreads through the labyrinth in several seconds instead of hours which is typical for trigger waves inherent in reaction-diffusion media. These fundamentals along with the additional procedure of testing for labyrinth fragment connectness provided us with the opportunity to solve labyrinth problems.     

DNA polymerase programmed with a hairpin DNA incorporates a multiple-instruction architecture into molecular computing

Parallelism is one of the major advantages of molecular computation. A large number of data encoded in DNA molecules can be processed simultaneously by molecular biology techniques, although only a single set of instructions has been implemented in a solution. We have developed a computing machine, called the "whiplash" machine, which is made of DNA polymerase and a hairpin DNA. This machine simulates a finite state machine, executing its own instructions encoded in the DNA moiety, and would thus be applicable to multiple-instruction operation in a solution. In the present study, we explored the feasibility of this novel type of parallelism by applying the whiplash machine in a computation of the directed Hamiltonian path problem. The possible paths in a given graph were represented with different instruction sets, which were then implemented separately by whiplash machines in a test tube. After an autonomous operation of the machines, only the machine that implemented the instruction set corresponding to the Hamiltonian path was recovered from the tube. On the basis of the efficiency of machine operation, which was experimentally determined, 10(10) different instruction sets could be implemented simultaneously in a 1-ml solution.     

Curved paths in raptor flight: Deterministic models

Two deterministic models for flight of Peregrine Falcons and possibly other raptors as they approach their prey are examined mathematically. Both models make two assumptions. The first, applicable to both models, is that the angle of sight between falcon and prey is constant, consistent with observations that the falcon keeps its head straight during flight and keeps on course by use of the deep foveal region in its eye which allows maximum acuity at an angle of sight of about 45 degrees . The second assumption for the first model (conical spiral), is that the initial direction of flight determines the overall path. For the second model (flight constrained to a tilted plane), a parameter that fixes the orientation of the plane is required. A variational calculation also shows that the tilted plane flight path is the shortest total path, and, consequently, the conical spiral is another shortest total path. Numerical calculations indicate that the flight paths for the two models are very similar for the experimental conditions under which observations have been made. However, the angles of flight and bank differ significantly. More observations are needed to investigate the applicability of the two models.     

Theoretical studies on doubly and triply linked polymers of Ge9 clusters

Experimental isolation of singly-bonded polymers of Ge₉, Sn₉ clusters and oligomers of doubly linked Ge₉ clusters encouraged us to explore other possibilities of polymerizing Ge₉ units. The electron counts in the reported oligomers are not consistent with simple ideas of localized intercluster bonding; demanding a detailed theoretical analysis. Band structure calculations suggest delocalized bonding with a charge requirement of 2− per Ge₉ unit for all polymeric doubly linked chains. DFT-based geometry optimization of model doubly linked polymers shows that one of the two possible forms is stable and has a band gap of ≈1.0 eV. A detailed bonding analysis of a theoretical model, Rb₄Ge₁₈, shows that the increased inter-polyhedral bond weakens the intra-polyhedral bonding. Ternary fusions are found to be generally unstable - for triple linkages the intrapolyhedral bonding is still further reduced; the polymers appear to be unstable towards dissociation into individual Ge₉ units.     

An exact parallel algorithm to compare very long biological sequences in clusters of workstations

Biological Sequence Comparison is one of the most important operations in Computational Biology since it is used to determine how similar two sequences are. Smith and Waterman proposed an exact algorithm (SW), based on dynamic programming, that is able to obtain the best local alignment between two sequences in quadratic time and space. In order to compare long biological sequences, SW is rarely used since the computation time and the amount of memory required becomes prohibitive. For this reason, heuristic methods like BLAST are widely used. Although faster, these heuristic methods do not guarantee that the best result will be produced. In this paper, we propose an exact parallel variant of the SW algorithm that obtains the best local alignments in quadratic time and reduced space. The results obtained in two clusters (8-machine and 16-machine) for DNA sequences longer than 32 KBP (kilo base-pairs) were very close to linear and, in some cases, superlinear. For very long DNA sequences (1.6 MBP), we were able to reduce execution time from 12.25 hours to 1.54 hours, in our 8-machine cluster. As far as we know, this is the first time 1.6 MBP sequences are compared with an exact SW variant. In this case, 30240 best local alignments were obtained.

Automatic classification in the case of unknown number of clusters using global density estimates

A clustering algorithm using a nonparametric density gradient estimate based on a trigonometric series expansion approach is investigated. The Mean-Integrated-Square-Error will be evaluated, conditions for consistency and a stopping rule for the number of terms needed in the series expansion are given. An example demonstrates the utility of the method.     

DNA approach to solve clustering problem based on a mutual order

Clustering is regarded as a consortium of concepts and algorithms that are aimed at revealing a structure in highly dimensional data and arriving at a collection of meaningful relationships in data and information granules. The objective of this paper is to propose a DNA computing to support the development of clustering techniques. This approach is of particular interest when dealing with huge data sets, unknown number of clusters and encountering a heterogeneous character of available data. We present a detailed algorithm and show how the essential components of the clustering technique are realized through the corresponding mechanisms of DNA computing. Numerical examples offer a detailed insight into the performance of the DNA-based clustering.     

Finding spatial regularity in mosaic landscapes: two methods integrated

Two methods were employed to find spatial regularity in a complicated mountain landscape of Beijing, China on the basis of functional and structural affinities. The first approach applied Affinity Analysis based on species composition to landscape. The mosaic diversity of the landscape was 3.5298>3, which means the study landscape is complex and controlled by multiple environmental gradients. These landscape types were divided into 3 parts according to the mean affinity values of 0.2143 and 0.7857 (0.5±1 SD). Modal sites are the central types of the landscape, which include a zonal broad-leaved forest of the region and a conifer plantation replacing the former. Outliers are found in the highest altitude and the lowest, both have few species in common with the above two modal types. The remaining landscape types are intermediate sites, which are transitional between modals and outliers, broadly distributed throughout mountain environments. Neighbor types have more species in common than those more widely separated, which probably distributed adjacently in space or in similar quality habitat. The other method employed is the new TWINSPAN analysis by substituting spatial neighboring data of landscape types for species composition data. It clearly divided the landscape types into three groups, i.e., subalpine, middle and low mountain groups, which were correlated with altitude, as well as influenced by human disturbance. The new TWINSPAN classification method is more reliable in finding spatial gradient of patchy landscapes than affinity analysis; however, affinity analysis is useful in finding species diversity pattern and the importance of landscape types in a region. Integrating advantages of the two methods could supply complete and reliable information on how landscape types are distributed in space, which environmental gradient dominates the spatial distribution of the landscape types, as well as where important and unusual types are located.     

Structures of clusters in sweetpotato amylopectin

Sweetpotato amylopectin was subjected to partial hydrolysis by α-amylase from Bacillus amyloliquefaciens to release the clusters. Clusters were then fractionated and precipitated by methanol and structurally characterized by gel-permeation chromatography and high-performance anion-exchange chromatography. An initial stage of α-amylolysis on the amylopectin isolated mostly domains but also clusters. A second stage of α-amylolysis on the domains and clusters further isolated their respective clusters and sub-clusters. All the domains, clusters and sub-clusters were sequentially subjected to phosphorolysis and β-amylolysis to obtain their internal part. The degree of polymerization of the clusters in the form of φ,β-limit dextrins were from 58 to 86. Each domain contained 2–8 clusters. Two types of clusters were structurally identified. Type A clusters were larger and contained about 12 chains per cluster with higher degree of branching (DB), whereas those of type B were smaller and contained about eight chains per cluster with lower DB.     

Comparative study of the server-initiated lowest algorithm using a load balancing index based on the process behavior for heterogeneous environment

The availability of low cost microcomputers and the evolution of computer networks have increased the development of distributed systems. In order to get a better process allocation on distributed environments, several load balancing algorithms have been proposed. Generally, these algorithms consider as the information policy’s load index the length of the CPU’s process waiting queue. This paper modifies the Server-Initiated Lowest algorithm by using a load index based on the resource occupation. Using this load index the Server-Initiated Lowest algorithm is compared to the Stable symmetrically initiated, which nowadays is defined as the best choice. The comparisons are made by using simulations. The simulations showed that the modified Server-Initiated Lowest algorithm had better results than the Symmetrically Initiated one.     

AutoMate: Enabling Autonomic Applications on the Grid

The increasing complexity, heterogeneity, and dynamism of emerging pervasive Grid environments and applications has necessitated the development of autonomic self-managing solutions, that are inspired by biological systems and deal with similar challenges of complexity, heterogeneity, and uncertainty. This paper introduces Project AutoMate and describes its key components. The overall goal of Project Automate is to investigate conceptual models and implementation architectures that can enable the development and execution of such self-managing Grid applications. Illustrative autonomic scientific and engineering Grid applications enabled by AutoMate are presented. The research presented in this paper is supported in part by the National Science Foundation via grants numbers ACI 9984357, EIA 0103674, EIA 0120934, ANI 0335244, CNS 0305495, CNS 0426354 and IIS 0430826. The authors would like to acknowledge the contributions of M. Agarwal, V. Bhat and N. Jiang to this research.     

A framework for characterizing overlap of communication and computation in parallel applications

Effective overlap of computation and communication is a well understood technique for latency hiding and can yield significant performance gains for applications on high-end computers. In this paper, we propose an instrumentation framework for message-passing systems to characterize the degree of overlap of communication with computation in the execution of parallel applications. The inability to obtain precise time-stamps for pertinent communication events is a significant problem, and is addressed by generation of minimum and maximum bounds on achieved overlap. The overlap measures can aid application developers and system designers in investigating scalability issues. The approach has been used to instrument two MPI implementations as well as the ARMCI system. The implementation resides entirely within the communication library and thus integrates well with existing approaches that operate outside the library. The utility of the framework is demonstrated by analyzing communication-computation overlap for micro-benchmarks and the NAS benchmarks, and the insights obtained are used to modify the NAS SP benchmark, resulting in improved overlap.

Exploiting redundancy to boost performance in a RAID-10 style cluster-based file system

While aggregating the throughput of existing disks on cluster nodes is a cost-effective approach to alleviate the I/O bottleneck in cluster computing, this approach suffers from potential performance degradations due to contentions for shared resources on the same node between storage data processing and user task computation. This paper proposes to judiciously utilize the storage redundancy in the form of mirroring existed in a RAID-10 style file system to alleviate this performance degradation. More specifically, a heuristic scheduling algorithm is developed, motivated from the observations of a simple cluster configuration, to spatially schedule write operations on the nodes with less load among each mirroring pair. The duplication of modified data to the mirroring nodes is performed asynchronously in the background. The read performance is improved by two techniques: doubling the degree of parallelism and hot-spot skipping. A synthetic benchmark is used to evaluate these algorithms in a real cluster environment and the proposed algorithms are shown to be very effective in performance enhancement. Yifeng Zhu received his B.Sc. degree in Electrical Engineering in 1998 from Huazhong University of Science and Technology, Wuhan, China; the M.S. and Ph.D. degree in Computer Science from University of Nebraska – Lincoln in 2002 and 2005 respectively. He is an assistant professor in the Electrical and Computer Engineering department at University of Maine. His main research interests are cluster computing, grid computing, computer architecture and systems, and parallel I/O storage systems. Dr. Zhu is a Member of ACM, IEEE, the IEEE Computer Society, and the Francis Crowe Society. Hong Jiang received the B.Sc. degree in Computer Engineering in 1982 from Huazhong University of Science and Technology, Wuhan, China; the M.A.Sc. degree in Computer Engineering in 1987 from the University of Toronto, Toronto, Canada; and the PhD degree in Computer Science in 1991 from the Texas A&M University, College Station, Texas, USA. Since August 1991 he has been at the University of Nebraska-Lincoln, Lincoln, Nebraska, USA, where he is Professor and Vice Chair in the Department of Computer Science and Engineering. His present research interests are computer architecture, parallel/distributed computing, cluster and Grid computing, computer storage systems and parallel I/O, performance evaluation, real-time systems, middleware, and distributed systems for distance education. He has over 100 publications in major journals and international Conferences in these areas and his research has been supported by NSF, DOD and the State of Nebraska. Dr. Jiang is a Member of ACM, the IEEE Computer Society, and the ACM SIGARCH. Xiao Qin received the BS and MS degrees in computer science from Huazhong University of Science and Technology in 1992 and 1999, respectively. He received the PhD degree in computer science from the University of Nebraska-Lincoln in 2004. Currently, he is an assistant professor in the department of computer science at the New Mexico Institute of Mining and Technology. He had served as a subject area editor of IEEE Distributed System Online (2000–2001). His research interests are in parallel and distributed systems, storage systems, real-time computing, performance evaluation, and fault-tolerance. He is a member of the IEEE. Dan Feng received the Ph.D degree from Huazhong University of Science and Technology, Wuhan, China, in 1997. She is currently a professor of School of Computer, Huazhong University of Science and Technology, Wuhan, China. She is the principal scientist of the the National Grand Fundamental Research 973 Program of China “Research on the organization and key technologies of the Storage System on the next generation Internet.” Her research interests include computer architecture, storage system, parallel I/O, massive storage and performance evaluation. David Swanson received a Ph.D. in physical (computational) chemistry at the University of Nebraska-Lincoln (UNL) in 1995, after which he worked as an NSF-NATO postdoctoral fellow at the Technical University of Wroclaw, Poland, in 1996, and subsequently as a National Research Council Research Associate at the Naval Research Laboratory in Washington, DC, from 1997–1998. In 1999 he returned to UNL where he directs the Research Computing Facility and currently serves as an Assistant Research Professor in the Department of Computer Science and Engineering. The Office of Naval Research, the National Science Foundation, and the State of Nebraska have supported his research in areas such as large-scale scientific simulation and distributed systems.     

DFT modelling of hydrogen on Cu(110)- and (111)-type clusters

Density Functional Theory (DFT) calculations using gaussian 98 have been performed on hydrogen adsorbed on clusters representing the (110) and (111) surfaces of Cu. Clusters were constructed to model different adsorption sites, and at least two different size clusters were used for each site. On the (111) surface, hydrogen prefers to adsorb in a hollow site, though with the hcp variant being favoured by the adsorption energy, and the fcc alternative by the vibrational frequencies. On the (110) surface, the "fcc" site on a (1 2 2) reconstructed surface is preferred.     

微生物连续发酵酶催化动力系统的鲁棒性与并行计算

依据甘油连续发酵生产1,3-丙二醇的非线性酶催化动力系统.针对1,3-丙二醇可能存在的跨膜运输方式建立相应的动力学模型,提出了酶催化动力系统的定量鲁棒性定义,并建立了以鲁棒性为性能指标、非线性动力系统为主要约束的参数辨识模型.由于求解该辨识问题的数值计算量大,在普通的PC机上难以完成,因此本文构建了相应的并行算法.根据数值结果推断出1,3-丙二醇最有可能的跨膜运输方式,这对于进一步研究甘油连续发酵的机理具有重要的参考价值.     

Structures of building blocks in clusters of sweetpotato amylopectin

φ,β-Limit dextrins of domains and clusters of sweetpotato amylopectin were subjected to extensive hydrolysis by Bacillus amyloliquefaciens α-amylase to release building blocks and reveal the internal structures of clusters. The composition of building blocks was analyzed by size-fractionation, gel permeation chromatography, and high performance anion exchange chromatography. Different domains and clusters had structurally similar building blocks with around three chains per building block and internal chain length around 2.9. Singly branched and doubly branched building blocks were the largest and second largest groups in the clusters. Type A clusters had more large building blocks and contained 5–6 blocks per cluster with an inter-block chain length (IB-CL) of 7.0, whereas type B clusters had less large building blocks and contained 3–4 blocks per cluster with IB-CL 7.9. Models on how the building blocks could be organized into type A and type B clusters are discussed.     

A DNA-based in vitroGenetic Program

In PNA-mediated Whiplash PCR (PWPCR), autonomous molecular computation is implemented by the recursive polymerase extension of a mixture of DNA hairpins. Like other methods based on exhaustive search, however, application to problem instances of realistic size is prevented by the exponential scaling of thesolution space. The tendency of evolving populations to minimize the sampling of large, low fitness basins suggests that a DNA-based evolutionary approach might be an effective alternative to exhaustive search. In this work, PWPCR is modified to support the evolution of a population of finite state machines. A practical, in vitroalgorithm for applying this architecture to evolve approximate solutions to instances of the NP-complete problem, Hamiltonian Pathis described in detail.     

Vegetation on avalanche paths in the alps

Vegetation pattern on avalanche paths in the Nordkette Mountains near Innsbruck (Tyrol, Austria) was studied using transect sampling. The plant communities represent a gradient from alpine grassland (Seslerio-Caricetum sempervirentis, via grassland with Trisetum distichophyllum) and nutrient-poor grassland (Carlino-Caricetum sempervirentis) to an avalanche grassland proper. Along this gradient disturbance decreases from higher to lower elevations. The topography of the avalanche path suggests a gradient from the central zone to the edge of the path, although a floristic zonation or grouping of species across the path cannot be detected. Disturbance and local topography are the dominant factors for the vegetation pattern on the avalanche paths investigated.Abbreviations DCA= detrended correspondence analysis