A graph-based approach to defend agro-ecological systems against water vole outbreaks

The cyclic spread of montane water vole populations in the grasslands of the Jura plateaus causes severe economic, ecological, and public-health problems. Since this phenomenon cannot be managed by massive use of the anticoagulant rodenticide bromadiolone, the challenge is to limit it by reducing regional-level connectivity through landscaping and agro-environmental interventions such as planting hedgerows, ploughing, and cultivating cereals. We used landscape graphs – a spatial modelling approach based on graph theory – to represent the grassland network and identify key areas for intervention. Several strategies were compared in terms of their capacity to fulfil operational requirements by interchanging patches and meta-patches as nodes of the graph, and least-cost distances and resistance distances to weight links. The combination of meta-patches and resistance distances provides a relevant basis on which to design concrete action to decrease regional-level connectivity of grasslands. The results also indicate that the usual removal method applied to the links of the graph would benefit from data on the statistical distribution of cost values along the shortest paths. More broadly, this suggests the modelling approach should be better matched the actual field interventions if the connectivity analysis is to be operational.     

A new approach for designing disease intervention strategies in metapopulation models

We describe a new approach for investigating the control strategies of compartmental disease transmission models. The method rests on the construction of various alternative next-generation matrices, and makes use of the type reproduction number and the target reproduction number. A general metapopulation SIRS (susceptible–infected–recovered–susceptible) model is given to illustrate the application of the method. Such model is useful to study a wide variety of diseases where the population is distributed over geographically separated regions. Considering various control measures such as vaccination, social distancing, and travel restrictions, the procedure allows us to precisely describe in terms of the model parameters, how control methods should be implemented in the SIRS model to ensure disease elimination. In particular, we characterize cases where changing only the travel rates between the regions is sufficient to prevent an outbreak.     

A hybrid graph-based approach for right ventricle segmentation in cardiac MRI by long axis information transition

Right ventricle segmentation is a challenging task in cardiac image analysis due to its complex anatomy and huge shape variations. In this paper, we proposed a semi-automatic approach by incorporating the right ventricle region and shape information into livewire framework and using one slice segmentation result for the segmentation of adjacent slices. The region term is created using our previously proposed region growing algorithm combined with the SUSAN edge detector while the shape prior is obtained by forming a signed distance function (SDF) from a set of binary masks of the right ventricle and applying PCA on them. Short axis slices are divided into two groups: primary and secondary slices. A primary slice is segmented by the proposed modified livewire and the livewire seeds are transited to a pre-processed version of upper and lower slices (secondary) to find new seed positions in these slices. The shortest path algorithm is applied on each pair of seeds for segmentation. This method is applied on 48 MR patients (from MICCAI’12 Right Ventricle Segmentation Challenge) and yielded an average Dice Metric of 0.937 ± 0.58 and the Hausdorff Distance of 5.16 ± 2.88 mm for endocardium segmentation. The correlation with the ground truth contours were measured as 0.99, 0.98, and 0.93 for EDV, ESV and EF respectively. The qualitative and quantitative results declare that the proposed method outperforms the state-of-the-art methods that uses the same dataset and the cardiac global functional parameters are calculated robustly by the proposed method.     

A graph-based reflexive artificial chemistry

The conceptual divide between formal systems of computation and abstract models of chemistry is considered. As an attempt to concretely bridge this divide, a formalism is proposed that describes a constructive artificial chemistry on a space of directed graph structures. The idea for the formalism originates in computer science theory, with the traditional abstraction of a physical machine, the finite-state machine (FSM). In the FSM, the machine (state-transition graph) and input string (series of binary digits) are fundamentally distinct objects, separated by nature of the underlying formalism. This distinction is dissolved in the proposed system, resulting in a construction process that is reflexive: graphs interact with their own topological structure to generate a product. It is argued that this property of reflexivity is a key element missing from earlier model chemistries. Examples demonstrate the continuous emergence complex self-similar topologies, novel reaction pathways, and seemingly open-ended diversity. Implications of these findings are discussed.     

A graph-based approach to investigating the influence of the landscape on population spread processes

Modelling of landscape connectivity is a key point in the study of the movement of populations within a given landscape. For studies focused on the preservation of biodiversity, graph-based methods provide an interesting framework to investigate the landscape influence on population spread processes. Such an approach is described here, based on the mapping of landscape categories in habitat patches, including a diachronic data set describing the population spread within the habitat patches. A minimum planar graph was built by computing spatial distances between all pairs of neighbouring patches. From this structure, two types of analysis are proposed: one focused on the links of the graph and consists in correlating spatial distances and gap indicators computed from the diachronic data. The other was based on the correlations between population data and connectivity metrics at the patch level. As an example, this approach was applied to the spread of the fossorial water vole on the Jura plateau (France), with annual population data covering eleven years from 1989 to 2000. Link analysis allowed to find an optimal set of resistance values used in the least-cost distances computations, and thus to build a relevant graph. From this graph, patch analysis displayed a cyclic correlation between a metric based on potential dispersal flux and the population density, outlining the strong role of landscape connectivity in the population spread. The present study clearly shows that landscape modelling and graph-based approach can produce parameters which are consistent with field observations and thus pave the way to simulating the effect of landscape modification on population dynamics.     

A graph-based filtering method for top-down mass spectral identification

Background

Database search has been the main approach for proteoform identification by top-down tandem mass spectrometry. However, when the target proteoform that produced the spectrum contains post-translational modifications (PTMs) and/or mutations, it is quite time consuming to align a query spectrum against all protein sequences without any PTMs and mutations in a large database. Consequently, it is essential to develop efficient and sensitive filtering algorithms for speeding up database search.

Results

In this paper, we propose a spectrum graph matching (SGM) based protein sequence filtering method for top-down mass spectral identification. It uses the subspectra of a query spectrum to generate spectrum graphs and searches them against a protein database to report the best candidates. As the sequence tag and gaped tag approaches need the preprocessing step to extract and select tags, the SGM filtering method circumvents this preprocessing step, thus simplifying data processing. We evaluated the filtration efficiency of the SGM filtering method with various parameter settings on an Escherichia coli top-down mass spectrometry data set and compared the performances of the SGM filtering method and two tag-based filtering methods on a data set of MCF-7 cells.

Conclusions

Experimental results on the data sets show that the SGM filtering method achieves high sensitivity in protein sequence filtration. When coupled with a spectral alignment algorithm, the SGM filtering method significantly increases the number of identified proteoform spectrum-matches compared with the tag-based methods in top-down mass spectrometry data analysis.

     

A thermodynamic approach to designing structure-free combinatorial DNA word sets

An algorithm is presented for the generation of sets of non-interacting DNA sequences, employing existing thermodynamic models for the prediction of duplex stabilities and secondary structures. A DNA ‘word’ structure is employed in which individual DNA ‘words’ of a given length (e.g. 12mer and 16mer) may be concatenated into longer sequences (e.g. four tandem words and six tandem words). This approach, where multiple word variants are used at each tandem word position, allows very large sets of non-interacting DNA strands to be assembled from combinations of the individual words. Word sets were generated and their figures of merit are compared to sets as described previously in the literature (e.g. 4, 8, 12, 15 and 16mer). The predicted hybridization behavior was experimentally verified on selected members of the sets using standard UV hyperchromism measurements of duplex melting temperatures (T_ms). Additional experimental validation was obtained by using the sequences in formulating and solving a small example of a DNA computing problem.     

Uniform design: A new approach of designing fermentation media

Summary Uniform design was introduced as a new approach of designing fermentation medium. The production of ethanol by Saccharomyces cerevisiae was used as a model system to investigate its applicability. Six factors, each at 10 levels experiments based on uniform design were carried out. As a result, the empirical mathematical models could successfully predict the experimental results with very good accuracy. In contrast with orthogonal design, uniform design has advantages of less experiments and higher working effeciency. Furthermore, factor influences on operation performance can be easily analyzed.     

A graph-based semantic similarity measure for the gene ontology

Existing methods for calculating semantic similarities between pairs of Gene Ontology (GO) terms and gene products often rely on external databases like Gene Ontology Annotation (GOA) that annotate gene products using the GO terms. This dependency leads to some limitations in real applications. Here, we present a semantic similarity algorithm (SSA), that relies exclusively on the GO. When calculating the semantic similarity between a pair of input GO terms, SSA takes into account the shortest path between them, the depth of their nearest common ancestor, and a novel similarity score calculated between the definitions of the involved GO terms. In our work, we use SSA to calculate semantic similarities between pairs of proteins by combining pairwise semantic similarities between the GO terms that annotate the involved proteins. The reliability of SSA was evaluated by comparing the resulting semantic similarities between proteins with the functional similarities between proteins derived from expert annotations or sequence similarity. Comparisons with existing state-of-the-art methods showed that SSA is highly competitive with the other methods. SSA provides a reliable measure for semantics similarity independent of external databases of functional-annotation observations.     

用原图-对偶图法设计内部间隔最小的自然保护区

生境破碎是导致生物多样性损失的重要原因之一,在设计自然保护区时设法减少生境破碎是提高保护区有效性的重要方法.由于经济资源或地理因素制约不可能把连续的大片土地都划为保护区时,设计一个由相互分离的几部分组成的保护区是更为现实的做法.选择地块组成内部间隔最小的保护区是减少破碎化的一个重要途径,但结合空间特征的保护区地块选择模...     

A global sampling approach to designing and reengineering RNA secondary structures

The development of algorithms for designing artificial RNA sequences that fold into specific secondary structures has many potential biomedical and synthetic biology applications. To date, this problem remains computationally difficult, and current strategies to address it resort to heuristics and stochastic search techniques. The most popular methods consist of two steps: First a random seed sequence is generated; next, this seed is progressively modified (i.e. mutated) to adopt the desired folding properties. Although computationally inexpensive, this approach raises several questions such as (i) the influence of the seed; and (ii) the efficiency of single-path directed searches that may be affected by energy barriers in the mutational landscape. In this article, we present RNA-ensign, a novel paradigm for RNA design. Instead of taking a progressive adaptive walk driven by local search criteria, we use an efficient global sampling algorithm to examine large regions of the mutational landscape under structural and thermodynamical constraints until a solution is found. When considering the influence of the seeds and the target secondary structures, our results show that, compared to single-path directed searches, our approach is more robust, succeeds more often and generates more thermodynamically stable sequences. An ensemble approach to RNA design is thus well worth pursuing as a complement to existing approaches. RNA-ensign is available at http://csb.cs.mcgill.ca/RNAensign.     

MHC binding peptides for designing of vaccines against Japanese encephalitis virus: A computational approach

Japanese encephalitis (JE), a viral disease has seen a drastic and fatal enlargement in the northern states of India in the current decade. The better and exact cure for the disease is still in waiting. For the cause an in silico strategy in the development of the peptide vaccine has been taken here for the study. A computational approach to find out the Major Histocompatibility Complex (MHC) binding peptide has been implemented. The prediction analysis identified MHC class I (using propred I) and MHC class II (using propred) binding peptides at an expectable percent predicted IC (50) threshold values. These predicted Human leukocyte antigen [HLA] allele binding peptides were further analyzed for potential conserved region using an Immune Epitope Database and Analysis Resource (IEDB). This analysis shows that HLA-DRB1*0101, HLA-DRB3*0101, HLA-DRB1*0401, HLA-DRB1*0102 and HLA-DRB1*07:01% of class II (in genotype 2) and HLA-A*0101, HLA-A*02, HLA-A*0301, HLA-A*2402, HLA-B*0702 and HLA-B*4402% of HLA I (in genotype 3) bound peptides are conserved. The predicted peptides MHC class I are ILDSNGDIIGLY, FVMDEAHFTDPA, KTRKILPQIIK, RLMSPNRVPNYNLF, APTRVVAAEMAEAL, YENVFHTLW and MHC class II molecule are TTGVYRIMARGILGT, NYNLFVMDEAHFTDP, AAAIFMTATPPGTTD, GDTTTGVYRIMARGI and FGEVGAVSL found to be top ranking with potential super antigenic property by binding to all HLA. Out of these the predicted peptide FVMDEAHFTDPA for allele HLA-A*02:01 in MHC class I and NYNLFVMDEAHFTDP for allele HLA-DRB3*01:01 in MHC class II was observed to be most potent and can be further proposed as a significant vaccine in the process. The reported results revealed that the immune-informatics techniques implemented in the development of small size peptide is useful in the development of vaccines against the Japanese encephalitis virus (JEV).     

SubSeqer: a graph-based approach for the detection and identification of repetitive elements in low-complexity sequences

Summary: Low-complexity, repetitive protein sequences with alimited amino acid palette are abundant in nature, and manyof them play an important role in the structure and functionof certain types of proteins. However, such repetitive sequencesoften do not have rigidly defined motifs. Consequently, theidentification of these low-complexity repetitive elements hasproven challenging for existing pattern-matching algorithms.Here we introduce a new web-tool SubSeqer (http://compsysbio.org/subseqer/)which uses graphical visualization methods borrowed from proteininteraction studies to identify and characterize repetitiveelements in low-complexity sequences. Given their abundance,we suggest that SubSeqer represents a valuable resource forthe study of typically neglected low-complexity sequences. Contact: jparkin{at}sickkids.ca Associate Editor: Limsoon Wong     

A graph-based clustering method applied to protein sequences

The number of amino acid sequences is increasing very rapidly in the protein databases like Swiss-Prot, Uniprot, PIR and others, but the structure of only some amino acid sequences are found in the Protein Data Bank. Thus, an important problem in genomics is automatically clustering homologous protein sequences when only sequence information is available. Here, we use graph theoretic techniques for clustering amino acid sequences. A similarity graph is defined and clusters in that graph correspond to connected subgraphs. Cluster analysis seeks grouping of amino acid sequences into subsets based on distance or similarity score between pairs of sequences. Our goal is to find disjoint subsets, called clusters, such that two criteria are satisfied: homogeneity: sequences in the same cluster are highly similar to each other; and separation: sequences in different clusters have low similarity to each other. We tested our method on several subsets of SCOP (Structural Classification of proteins) database, a gold standard for protein structure classification. The results show that for a given set of proteins the number of clusters we obtained is close to the superfamilies in that set; there are fewer singeltons; and the method correctly groups most remote homologs.     

An evolutionary modeling approach for designing a contractual REDD+ payment scheme

Economic development and sustainable ecological and environmental development generally target different goals, and there are trade-offs and game-like behaviors between implementers and donors in reducing emissions from deforestation and degradation (REDD+) program. This paper analyzed the effects of evolutionary behaviors of REDD+ implementers and donors with respect to environmental service payments. Within a theoretical analysis framework, the evolutionary stable strategies of the implementers and donors under different contractual payments for ecosystem services (PES) scenarios are analyzed to explore contractual REDD+ payments through evolutionary game models. On this basis, anon-parametric local regression approach is used to analyze arrange of market-based contractual PES schemes in five REDD+ countries (Congo, Brazil, Ecuador, Nepal and Uganda). The results show the following: First, when the opportunity costs are less than the environmental benefits, some middle and high income developing countries are sufficiently incentivized to conserve forests, even without formal contractual PES scheme. This conservation occurs regardless of whether the industrialized countries will pay for the ecosystem services. Second, when the opportunity costs are greater than the environmental benefits, developing countries will generally not take the initiative to conserve forests when industrialized countries do not pay for the associated ecosystem services. Third, when there are enough contractual PES fines, developing countries will conserve forests, and the industrialized countries will pay for the ecosystem services. Finally, contractual PES fines are related to the costs of reducing emissions. Nepal has the largest marginal effect, and Uganda has the smallest. These results have implications for REDD+ program design and implementation: market-based contractual PES scheme should be given priority to regulate behavior of industrialized countries and developing countries in the PES scheme. Developing a targeted and differentiated contractual PES scheme requires an accounting of emission reduction costs in different countries.     

宏基因组研究的生物信息学平台现状

由Handelsman et al(1998)提出的宏基因组(metagenome)泛指特定环境样品(例如:人类和动物的肠道、母乳、土壤、湖泊、冰川和海洋等环境)中微生物群落所有物种的基因组。宏基因组技术起源于环境微生物学研究,而新一代高通量测序技术使其广泛应用成为可能。与基因组学研究相类似,目前宏基因组学发展的瓶颈在于如何高效分析高通量测序产生的海量数据,因此,相关的生物信息学分析方法和平台是宏基因组学研究的关键。该文介绍了目前宏基因组研究领域中主要的生物信息学软件及工具;鉴于目前宏基因组研究所采用的"全基因组测序"(whole genome sequencing)和"扩增子测序"(amplicon sequencing)两大测序方法所获得的数据和相应分析方法有较大差异,文中分别对相应软件平台进行了介绍。