Quantitative method for identifying networks of minimum priority sites for protection of rare and endangered plant species in Guangdong, China

The approaches to enlarge the protected areas are deeply embedded in the conservation planning. In practice, however, even in some sites of top conservation priority, there exist problems of inefficient conservation for lack of funding, to say nothing of assisting all species under threat from the viewpoint of conservationists. Identifying priority sites for conservation and establishing networks of minimum priority sites (NOMPS) are helpful for promoting the transition from number and size oriented, to quality and effectiveness oriented practices of biological conservation, and for realizing the target of biodiversity conservation with the most benefits for the least costs. Based on heuristic algorithm and integer linear programming (ILP), we propose a refined method of heuristic integer linear programming (HILP) for quantitative identification of the NOMPS to protect rare and endangered plant species (REPS) in Guangdong Province, China. The results indicate that there are 19 priority sites which are essential for protecting all of the 107 REPS distributed in 83 sites in Guangdong. These should be the paramount targets of financing and management. Compared with the ILP, which uses minimum number of sites as the only constraint, HILP takes into consideration of the effect of species richness, and is thus more suitable for conservation practices though with a little more number of priority sites selected. It is suggested that ILP and HILP are both effective quantitative methods for identifying NOMPS and can yield important information for decision making, especially when economic factors are constraints for biological conservation.     

Rarity-Weighted Richness: A Simple and Reliable Alternative to Integer Programming and Heuristic Algorithms for Minimum Set and Maximum Coverage Problems in Conservation Planning

Here we report that prioritizing sites in order of rarity-weighted richness (RWR) is a simple, reliable way to identify sites that represent all species in the fewest number of sites (minimum set problem) or to identify sites that represent the largest number of species within a given number of sites (maximum coverage problem). We compared the number of species represented in sites prioritized by RWR to numbers of species represented in sites prioritized by the Zonation software package for 11 datasets in which the size of individual planning units (sites) ranged from <1 ha to 2,500 km². On average, RWR solutions were more efficient than Zonation solutions. Integer programming remains the only guaranteed way find an optimal solution, and heuristic algorithms remain superior for conservation prioritizations that consider compactness and multiple near-optimal solutions in addition to species representation. But because RWR can be implemented easily and quickly in R or a spreadsheet, it is an attractive alternative to integer programming or heuristic algorithms in some conservation prioritization contexts.     

自然保护区空间特征和地块最优化选择方法

自然保护区是保护物种和生态系统的有效方式,用于建立自然保护区的资源却是稀缺的,这就提出这样的问题：1)自然保护区在空间上应具有什么特征才是有效的;2)如何从许多备选地块中选择一部分组成自然保护区对稀缺资源进行最优化分配。为促进物种生存繁衍,在地块选择时应考虑保护区空间特征。这篇文章综述了该领域最近的研究进展,重点介绍了结合各种空间特征的保护区地块最优化选择模型。介绍了4个主要的空间特征：1)连续,2)间隔和距离,3)边界和集约,4)面积以及核心区和缓冲区。以前用启发式算法求解这些问题,但研究已显示该法不能保证资源的最优化分配。空间特征也可用线性整数规划模拟,用最优化软件求得最优解。目前的线性整数规划模型和软件还不能有效解决大型的保护区地块选择问题,计算效率易成为实际应用的瓶颈。文章概括了我国目前自然保护区设计领域的研究状况和面临的问题,最后讨论了该领域新的研究方向。     

Mixed integer linear programming for maximum-parsimony phylogeny inference

Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny inference will be required if we are to be able to continue to make effective use of the rapidly growing stores of variation data now being gathered. In this paper, we present two integer linear programming (ILP) formulations to find the most parsimonious phylogenetic tree from a set of binary variation data. One method uses a flow-based formulation that can produce exponential numbers of variables and constraints in the worst case. The method has, however, proven extremely efficient in practice on datasets that are well beyond the reach of the available provably efficient methods, solving several large mtDNA and Y-chromosome instances within a few seconds and giving provably optimal results in times competitive with fast heuristics than cannot guarantee optimality. An alternative formulation establishes that the problem can be solved with a polynomial-sized ILP. We further present a web server developed based on the exponential-sized ILP that performs fast maximum parsimony inferences and serves as a front end to a database of precomputed phylogenies spanning the human genome.     

Uncovering signal transduction networks from high-throughput data by integer linear programming

Signal transduction is an important process that transmits signals from the outside of a cell to the inside to mediate sophisticated biological responses. Effective computational models to unravel such a process by taking advantage of high-throughput genomic and proteomic data are needed to understand the essential mechanisms underlying the signaling pathways. In this article, we propose a novel method for uncovering signal transduction networks (STNs) by integrating protein interaction with gene expression data. Specifically, we formulate STN identification problem as an integer linear programming (ILP) model, which can be actually solved by a relaxed linear programming algorithm and is flexible for handling various prior information without any restriction on the network structures. The numerical results on yeast MAPK signaling pathways demonstrate that the proposed ILP model is able to uncover STNs or pathways in an efficient and accurate manner. In particular, the prediction results are found to be in high agreement with current biological knowledge and available information in literature. In addition, the proposed model is simple to be interpreted and easy to be implemented even for a large-scale system.     

Solving and analyzing side-chain positioning problems using linear and integer programming

MOTIVATION: Side-chain positioning is a central component of homology modeling and protein design. In a common formulation of the problem, the backbone is fixed, side-chain conformations come from a rotamer library, and a pairwise energy function is optimized. It is NP-complete to find even a reasonable approximate solution to this problem. We seek to put this hardness result into practical context. RESULTS: We present an integer linear programming (ILP) formulation of side-chain positioning that allows us to tackle large problem sizes. We relax the integrality constraint to give a polynomial-time linear programming (LP) heuristic. We apply LP to position side chains on native and homologous backbones and to choose side chains for protein design. Surprisingly, when positioning side chains on native and homologous backbones, optimal solutions using a simple, biologically relevant energy function can usually be found using LP. On the other hand, the design problem often cannot be solved using LP directly; however, optimal solutions for large instances can still be found using the computationally more expensive ILP procedure. While different energy functions also affect the difficulty of the problem, the LP/ILP approach is able to find optimal solutions. Our analysis is the first large-scale demonstration that LP-based approaches are highly effective in finding optimal (and successive near-optimal) solutions for the side-chain positioning problem.     

生物多样性保护的一个理论框架

稳定而复杂多样的自然生境有利于多样性的形成和保存,剧变并趋于简单化的干扰生境常使多样性丧失。现实中的森林破碎化使区域物种丧失。多样性保护要求具备促使物种能长久生存的生境。生物最小面积概念集中讨论物种长久生存与群落（景观）面积的关系,是多样性保护的最基本的理论基础。根据自然保护实践,提出最小景观,扩充了生物最小面积概念。讨论了生物最小面积概念在建立自然保护区的理论框架、了解被保护生物及其生境的自然特点以及建立更全面的自然保护网络等方面的应用     

生物多样性保护的一个理论框架——生物最小面积概念

稳定而复杂多样的自然生境有利于多样性的形成和保存,剧变并趋于简单化的干扰生境常使多样性丧失。现实中的森林破碎化使区域物种丧失。多样性保护要求具备促使物种能长久生存的生境。生物最小面积概念集中讨论物种长久生存与群落(景观)面积的关系,是多样性保护的最基本的理论基础。根据自然保护实践,提出最小景观,扩充了生物最小面积概念。讨论了生物最小面积概念在建立自然保护区的理论框架、了解被保护生物及其生境的自然特点以及建立更全面的自然保护网络等方面的应用。     

The risk of invasion by angiosperms peaks at intermediate levels of human influence

Biological invasions are a growing threat to biodiversity. The control and eradication of exotic species established in earnest are of limited success despite high financial investments. Anticipating biological invasions based on species’ suitabilities is a cost-effective strategy given it helps identifying areas where exotic species can prosper, which can then translate in improving management and conservation efforts. Based on information from 191 invasive angiosperm species worldwide, we used ecological niche models to identify areas at high risk of invasion (cumulative predicted distribution of invasive species) in Mexico. Further, we explored the importance of bioclimatic and human influence variables as drivers of the distribution of invasive species and analyzed the status of the currently recognized priority conservation sites in Mexico. We found that areas with intermediate human activity scores had a high risk of invasion. Additionally, we found that many of the current priority conservation sites in Mexico had a high risk of invasion. Our findings contribute to disentangling the factors that drive environment susceptibility to invasions and urge management strategies to minimize the impacts of biological invasions in priority conservation sites.     

Computing the reversal distance between genomes in the presence of multi-gene families via binary integer programming

Hannenhalli and Pevzner developed the first polynomial-time algorithm for the combinatorial problem of sorting signed genomic data. Their algorithm determines the minimum number of reversals required for rearranging a genome to another -but only in the absence of gene duplicates. However, duplicates often account for 40% of a genome. In this paper, we show how to extend Hannenhalli and Pevzner's approach to deal with genomes with multi-gene families. We propose a new heuristic algorithm to compute the nearest reversal distance between two genomes with multi-gene families via binary integer programming. The experimental results on both synthetic and real biological data demonstrate that the proposed algorithm is able to find the reversal distance with high accuracy.     

Selecting priority areas for systematic conservation of Chinese <Emphasis Type="Italic">Rhododendron</Emphasis>: hotspot versus complementarity approaches

The use of quantitative measures to select priority areas for conservation has been in practice since the early 1980s. However, the relative efficiency of different methods for identifying priority areas is still the subject of debate. Here, using the distribution data of 556 Rhododendron species in China with high spatial resolution, we evaluated the performance of the two commonly used methods, i.e. hotspot and complementarity and selected the efficient method to select priority areas for the conservation of Rhododendron in China. By overlaying the priority areas map with the locations of protected areas, we also identified the regions not covered by current protected areas (i.e. conservation gaps). We found that the complementarity method selected less number of grid cells to capture an equivalent number of species and hence had higher efficiency and representativeness than the commonly used hotspot method. Moreover, the complementarity method was better at capturing the range-restricted species than the hotspot method. Based on the complementarity method, we identified 61 grid cells of 50?×?50 km as priority areas for Rhododendron conservation in China. Among these priority areas, only about 50% grid cells were located in the hotspot areas (e.g. Hengduan Mountains), and 14% grid cells were outside the current protected area network. Our findings suggest that, despite its popularity and ease of implementation, the sites selected by hotspot algorithm may not necessarily be the best sites to allocate conservation efforts. Since the identification of priority areas in China has largely been based on the hotspot method, the current study has revived the need to reassess the priority areas for other taxonomic groups too. More importantly, our findings have emphasized the need to expand the conservation priorities from Hengduan Mountains to south and southeast China as well.     

Loading problems with tool management in flexible manufacturing systems: A few integer programming models

In automated production systems like flexible manufacturing systems (FMSs), an important issue is to find an adequate workload for each machine for each time period. Many integer linear programming (ILP) models have been proposed to solve the FMS loading problems, but not all of them take tools into account. Those that do not consider tooling are quite unrealistic, especially when setup times are important with respect to processing times. When tool loading has to be handled by the model, the load assignment may have to be changed completely. In this article we consider FMSs with a tool management of the following type: the system works in time periods whose durations are fixed or not; and tools are loaded on the machines at the beginning of each time period and stay there for the whole time period. Tool changes may occur only at the end of each time period when the system is stopped. We present some integer programming models for handling these situations with several types of objectives. Emphasis is laid on the ILP formulations. Computational complexities are discussed.     

Complementarity and other key criteria in the conservation of herb-rich forests in Finland

Complementarity of the nature reserve network in southernmost Finlandwas examined using a simple heuristic algorithm and occurrence data of 75characteristic herb-rich forest vascular plant species in 126 protected and 120non-protected sites. Three different minimum sets were selected to represent 1,5, or 10 occurrences of each species. In each minimum set there weresignificantly more protected than non-protected sites. Thus, although efficiencyis not maximal in the existing reserve network, the network does provide arepresentative basis for the conservation of herb-rich forest plants. However,some deficiencies were also noticed, particularly new reserves in floristicallydiverse herb-rich forests along watercourses would supplement the existingreserve network. On the other hand, the growing concern over the shortcomings ofreserve selection studies using presence/absence data is echoed here, becausemany of the protected forests not included in the minimum sets harbour importantnature conservation values. With regard to the five biological reserve selectioncriteria (e.g. occurrences of threatened species) considered here, theperformance of the existing reserve network is rather good. However, examinationof five reserve design criteria revealed some deficiencies, particularlyvulnerability of many reserves to potential edge effects.     

最优化设计连续的自然保护区

生境破碎是导致生物多样性损失的重要原因之一,避免生境破碎的一个有效方式是建立连续的自然保护区使物种可在保护区内自由移动。不加选择地把大片土地都转为保护区是实现连续的一个途径,但资源是有限的,应当以最优的方式分配。如何最优化设计生态上和经济上都有效的保护区成为生物保护领域一个重要议题。从一组备选地块中选择一部分组成自然保护区,这样的问题主要有两种解法:启发式方法和最优化方法。启发式方法虽然灵活且运算速度快但不能保证最优解因而可能导致稀缺资源的浪费,最优化方法保证得到的解是最优的但建模和运算存在困难。建立一个线性整数规划模型用于设计一个最小的连续保护区,用Dantzig剪切法消除循环确保形成一个连续的树,对应一个连续的保护区,检验了模型的计算效率。结果显示,模型可在合理时间内解决一个包含100个备选地块和30个物种的连续保护区设计问题,计算效率显著优于同类目的的其它方法。以美国伊利诺伊州Cache河流域11种濒危鸟类的保护区设计为例说明了该方法的应用,设计了两种情况下连续的保护区。讨论了模型的局限和数据问题。     

Design of Nature Reserve System for Red-Crowned Crane in China

A system of nature reserves is a necessary component of an integrated conservation strategy. The basic problem in the design of a nature reserve system is to select the smallest number of sites from a region for some conservation objectives. There are 33 nature reserves intended for the conservation of Red-Crowned Crane (Grus japonensis), totalling 3.1 million ha. Other habitats of Red-Crowned Crane are facing severe problems due to economic development and other human activities. GIS, iterative methods and the integer programming approach were employed to design the nature reserve system for Red-Crowned Crane, with conservation goals to protect 70 and 60% areas of highly and moderately suitable wetlands, respectively. The results indicated the need to designate six new nature reserves in Wulagai marsh, Duluhe River, Tumen River, Rizhao, Gaoyou Lake and Hongze Lake, and showed a protection zone in Songnen Plain (between Heilongjiang Province and Jilin Province) and three clusters of nature reserves in Sanjing Plain, which, will be used as reference for the designation of new nature reserves, or enlargement and adjustment of existing nature reserves. The iterative method and integer programming approaches were feasible for design of nature reserve system.     

Landscape heterogeneity in relation to variations in epigaeic beetle diversity of a Mediterranean ecosystem. Implications for conservation

Habitat heterogeneity is a determinant cause of biological diversity in natural ecosystems, and therefore its preservation should be a priority when planning conservation strategies. Sierra de Baza, in southern Spain, is a protected natural area in which biotopes of particular interest still remain, but extensive afforestation with pine species has been widespread in recent decades and, in some cases, continues. The aim of this paper is to test the role of habitat heterogeneity at the landscape scale in generating epigaeic beetle diversity in Sierra de Baza. After two-year-long cycles of sampling epigaeic beetles, differences in local diversity at nine sites, and differences in the pattern of species turnover between sites, have been measured. Local communities differed among sites, 74% of the species being scarce (less than 0.41% of total beetle abundance), and thus species replacement differed markedly between sites. Comparisons between habitat types showed that the planted pine forests support less diverse fauna. Our results identify habitat heterogeneity at the landscape scale as the main source of epigaeic beetle diversity at the landscape scale, practices such as extensive afforestation diminishing landscape heterogeneity and consequently local beetle diversity. Preservation of landscape heterogeneity should be encouraged for an adequate beetle biodiversity conservation.     

Downscaling patterns of complementarity to a finer resolution and its implications for conservation prioritization

Given species inventories of all sites in a planning area, integer programming or heuristic algorithms can prioritize sites in terms of the site's complementary value, that is, the ability of the site to complement (add unrepresented species to) other sites prioritized for conservation. The utility of these procedures is limited because distributions of species are typically available only as coarse atlases or range maps, whereas conservation planners need to prioritize relatively small sites. If such coarse‐resolution information can be used to identify small sites that efficiently represent species (i.e., downscaled), then such data can be useful for conservation planning. We develop and test a new type of surrogate for biodiversity, which we call downscaled complementarity. In this approach, complementarity values from large cells are downscaled to small cells, using statistical methods or simple map overlays. We illustrate our approach for birds in Spain by building models at coarse scale (50 × 50 km atlas of European birds, and global range maps of birds interpreted at the same 50 × 50 km grid size), using this model to predict complementary value for 10 × 10 km cells in Spain, and testing how well‐prioritized cells represented bird distributions in an independent bird atlas of those 10 × 10 km cells. Downscaled complementarity was about 63–77% as effective as having full knowledge of the 10‐km atlas data in its ability to improve on random selection of sites. Downscaled complementarity has relatively low data acquisition cost and meets representation goals well compared with other surrogates currently in use. Our study justifies additional tests to determine whether downscaled complementarity is an effective surrogate for other regions and taxa, and at spatial resolution finer than 10 × 10 km cells. Until such tests have been completed, we caution against assuming that any surrogate can reliably prioritize sites for species representation.     

Influence of scale on conservation priority setting – a test on African mammals

Broad-scale priority regions for conservation can be identified usingdatabases on species distribution through the application of site-selectionalgorithms. However, the influence of scale on large-scale priority setting isstill unclear. Using a data set of all 939 sub-Saharan mammal species,we wanted to know if continental conservation priorities derived at the scales of 1°, 2°,4° and 8° latitude–longitude grid cells are consistent. We testedwhether (1) geographical location of minimum sets were nested across scale, (2)the selection sequence (priority) of areas within a minimum set were scaledependent, and (3) these coarse-scale priorities can act as a cost-effectiveshortcut for the identification of fine-scale priorities. We found that minimumsets at smaller scales were largely represented within minimum sets at largerscales, especially when flexibility was considered. However, the geographicallocation of the grid cells with highest priority in the minimum sets was onlyscale independent if ranked by number of endangered species, total speciesrichness or rare quartile species richness, but surprisingly not bycomplementary species richness. Minimum sets at a 1° scale were generallyidentified within the areas of the 2°, 4° and 8° minimum sets.Therefore, coarse-scale priorities may provide a pragmatic basis for immediateassessment of priorities for conservation.     

An ILP solution for the gene duplication problem

Background

The gene duplication (GD) problem seeks a species tree that implies the fewest gene duplication events across a given collection of gene trees. Solving this problem makes it possible to use large gene families with complex histories of duplication and loss to infer phylogenetic trees. However, the GD problem is NP-hard, and therefore, most analyses use heuristics that lack any performance guarantee.

Results

We describe the first integer linear programming (ILP) formulation to solve instances of the gene duplication problem exactly. With simulations, we demonstrate that the ILP solution can solve problem instances with up to 14 taxa. Furthermore, we apply the new ILP solution to solve the gene duplication problem for the seed plant phylogeny using a 12-taxon, 6, 084-gene data set. The unique, optimal solution, which places Gnetales sister to the conifers, represents a new, large-scale genomic perspective on one of the most puzzling questions in plant systematics.

Conclusions

Although the GD problem is NP-hard, our novel ILP solution for it can solve instances with data sets consisting of as many as 14 taxa and 1, 000 genes in a few hours. These are the largest instances that have been solved to optimally to date. Thus, this work can provide large-scale genomic perspectives on phylogenetic questions that previously could only be addressed by heuristic estimates.

     

Inferring haplotypes from genotypes on a pedigree with mutations, genotyping errors and missing alleles

Inferring the haplotypes of the members of a pedigree from their genotypes has been extensively studied. However, most studies do not consider genotyping errors and de novo mutations. In this paper, we study how to infer haplotypes from genotype data that may contain genotyping errors, de novo mutations, and missing alleles. We assume that there are no recombinants in the genotype data, which is usually true for tightly linked markers. We introduce a combinatorial optimization problem, called haplotype configuration with mutations and errors (HCME), which calls for haplotype configurations consistent with the given genotypes that incur no recombinants and require the minimum number of mutations and errors. HCME is NP-hard. To solve the problem, we propose a heuristic algorithm, the core of which is an integer linear program (ILP) using the system of linear equations over Galois field GF(2). Our algorithm can detect and locate genotyping errors that cannot be detected by simply checking the Mendelian law of inheritance. The algorithm also offers error correction in genotypes/haplotypes rather than just detecting inconsistencies and deleting the involved loci. Our experimental results show that the algorithm can infer haplotypes with a very high accuracy and recover 65%-94% of genotyping errors depending on the pedigree topology.