BCD Beam Search: considering suboptimal partial solutions in Bad Clade Deletion supertrees.

Abstract:

:Supertree methods enable the reconstruction of large phylogenies. The supertree problem can be formalized in different ways in order to cope with contradictory information in the input. Some supertree methods are based on encoding the input trees in a matrix; other methods try to find minimum cuts in some graph. Recently, we introduced Bad Clade Deletion (BCD) supertrees which combines the graph-based computation of minimum cuts with optimizing a global objective function on the matrix representation of the input trees. The BCD supertree method has guaranteed polynomial running time and is very swift in practice. The quality of reconstructed supertrees was superior to matrix representation with parsimony (MRP) and usually on par with SuperFine for simulated data; but particularly for biological data, quality of BCD supertrees could not keep up with SuperFine supertrees. Here, we present a beam search extension for the BCD algorithm that keeps alive a constant number of partial solutions in each top-down iteration phase. The guaranteed worst-case running time of the new algorithm is still polynomial in the size of the input. We present an exact and a randomized subroutine to generate suboptimal partial solutions. Both beam search approaches consistently improve supertree quality on all evaluated datasets when keeping 25 suboptimal solutions alive. Supertree quality of the BCD Beam Search algorithm is on par with MRP and SuperFine even for biological data. This is the best performance of a polynomial-time supertree algorithm reported so far.

journal_name

PeerJ

journal_title

PeerJ

authors

Fleischauer M,Böcker S

doi

10.7717/peerj.4987

subject

Has Abstract

pub_date

2018-06-08 00:00:00

pages

e4987

issn

2167-8359

pii

4987

journal_volume

6

pub_type

杂志文章

相关文献

PeerJ文献大全
  • Monitoring body condition score of reintroduced banteng (Bos javanicus D'Alton, 1923) into Salakphra Wildlife Sanctuary, Thailand.

    abstract:Background:Banteng (Bos javanicus d'Alton 1823) are an endangered species, highly sensitive to habitat structure and quality. In many areas, banteng were extinct and needed to be reintroduced to restore their population. Thus, understanding the responses of body condition of reintroduced banteng to their habitat was im...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.9041

    authors: Kongsurakan P,Chaiyarat R,Nakbun S,Thongthip N,Anuracpreeda P

    更新日期:2020-04-23 00:00:00

  • Quantifying uncertainty in annual runoff due to missing data.

    abstract::Long-term streamflow datasets inevitably include gaps, which must be filled to allow estimates of runoff and ultimately catchment water budgets. Uncertainty introduced by filling gaps in discharge records is rarely, if ever, reported. We characterized the uncertainty due to streamflow gaps in a reference watershed at ...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.9531

    authors: See CR,Green MB,Yanai RD,Bailey AS,Campbell JL,Hayward J

    更新日期:2020-07-21 00:00:00

  • Bats from different foraging guilds prey upon the pine processionary moth.

    abstract::Outbreaks of the processionary moth Thaumetopoea pityocampa (Denis & Schiffermüller, 1775), a forest pest from the Palearctic, are thought to induce a behavioral response of bats, but up to now the moth has been seldom identified as bats' prey. Studies on bat diets suggest moths with cyclical outbreaks attract a wide ...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.7169

    authors: Garin I,Aihartza J,Goiti U,Arrizabalaga-Escudero A,Nogueras J,Ibáñez C

    更新日期:2019-07-05 00:00:00

  • Plant community recovery from intense deer grazing depends on reduction of graminoids and the time after exclosure installation in a semi-natural grassland.

    abstract::Exclosures that exclude large herbivores are effective tools for the protection and restoration of grazed plant communities. However, previous studies have shown that the installation of an exclosure does not ensure plant community recovery. Our study aimed to determine the effects of the domination of unpalatable pla...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.7833

    authors: Otsu C,Iijima H,Nagaike T

    更新日期:2019-10-01 00:00:00

  • Shark and ray diversity in the Tropical America (Neotropics)-an examination of environmental and historical factors affecting diversity.

    abstract::We present the first comprehensive review of the present and past shark and ray diversity in marine waters of Tropical America, examining the patterns of distribution in the Eastern Central Pacific (EP) and Western Central Atlantic (WA) realms. We identified the major regions of diversity and of endemism, and explored...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.5313

    authors: Carrillo-Briceño JD,Carrillo JD,Aguilera OA,Sanchez-Villagra MR

    更新日期:2018-07-20 00:00:00

  • The tetrapod fauna of the upper Permian Naobaogou Formation of China: 3. Jiufengia jiai gen. et sp. nov., a large akidnognathid therocephalian.

    abstract::Recent field trips to Member III of the Naobaogou Formation, Nei Mongol, China yielded new fossil discoveries, increasing our knowledge of the late Permian continental fauna from China. We present here a new large therocephalian, Jiufengia jiai gen. et sp. nov., represented by a partial skull with mandibles and part o...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.6463

    authors: Liu J,Abdala F

    更新日期:2019-02-22 00:00:00

  • The mitochondrial genome of Paragonimus westermani (Kerbert, 1878), the Indian isolate of the lung fluke representative of the family Paragonimidae (Trematoda).

    abstract::Among helminth parasites, Paragonimus (zoonotic lung fluke) gains considerable importance from veterinary and medical points of view because of its diversified effect on its host. Nearly fifty species of Paragonimus have been described across the globe. It is estimated that more than 20 million people are infected wor...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.484

    authors: Biswal DK,Chatterjee A,Bhattacharya A,Tandon V

    更新日期:2014-08-12 00:00:00

  • Morphological analysis of dendrites and spines by hybridization of ridge detection with twin support vector machine.

    abstract::Dendritic spines are described as neuronal protrusions. The morphology of dendritic spines and dendrites has a strong relationship to its function, as well as playing an important role in understanding brain function. Quantitative analysis of dendrites and dendritic spines is essential to an understanding of the forma...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.2207

    authors: Wang S,Chen M,Li Y,Shao Y,Zhang Y,Du S,Wu J

    更新日期:2016-07-20 00:00:00

  • VaRank: a simple and powerful tool for ranking genetic variants.

    abstract::Background. Most genetic disorders are caused by single nucleotide variations (SNVs) or small insertion/deletions (indels). High throughput sequencing has broadened the catalogue of human variation, including common polymorphisms, rare variations or disease causing mutations. However, identifying one variation among h...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.796

    authors: Geoffroy V,Pizot C,Redin C,Piton A,Vasli N,Stoetzel C,Blavier A,Laporte J,Muller J

    更新日期:2015-03-03 00:00:00

  • Enzymatically crosslinked gelatin hydrogel promotes the proliferation of adipose tissue-derived stromal cells.

    abstract::Gelatin hydrogel crosslinked by microbial transglutaminase (mTG) exhibits excellent performance in cell adhesion, proliferation, and differentiation. We examined the gelation time and gel strength of gelatin/mTG hydrogels in various proportions to investigate their physical properties and tested their degradation perf...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.2497

    authors: Yang G,Xiao Z,Ren X,Long H,Qian H,Ma K,Guo Y

    更新日期:2016-09-27 00:00:00

  • Towards a barnacle tree of life: integrating diverse phylogenetic efforts into a comprehensive hypothesis of thecostracan evolution.

    abstract::Barnacles and their allies (Thecostraca) are a biologically diverse, monophyletic crustacean group, which includes both intensely studied taxa, such as the acorn and stalked barnacles, as well as cryptic taxa, for example, Facetotecta. Recent efforts have clarified phylogenetic relationships in many different parts of...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.7387

    authors: Ewers-Saucedo C,Owen CL,Pérez-Losada M,Høeg JT,Glenner H,Chan BKK,Crandall KA

    更新日期:2019-08-16 00:00:00

  • Plasma proteomic analysis of systemic lupus erythematosus patients using liquid chromatography/tandem mass spectrometry with label-free quantification.

    abstract:Context:Systemic lupus erythematosus (SLE) is a chronic inflammatory autoimmune disease with unknown etiology. Objective:Human plasma is comprised of over 10 orders of magnitude concentration of proteins and tissue leakages. The changes in the abundance of these proteins have played an important role in various human ...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.4730

    authors: Madda R,Lin SC,Sun WH,Huang SL

    更新日期:2018-05-08 00:00:00

  • PKC in motorneurons underlies self-learning, a form of motor learning in Drosophila.

    abstract::Tethering a fly for stationary flight allows for exquisite control of its sensory input, such as visual or olfactory stimuli or a punishing infrared laser beam. A torque meter measures the turning attempts of the tethered fly around its vertical body axis. By punishing, say, left turning attempts (in a homogeneous env...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.1971

    authors: Colomb J,Brembs B

    更新日期:2016-04-25 00:00:00

  • Molecular characterization of clonal lineage and staphylococcal toxin genes from S. aureus in Southern Nigeria.

    abstract:Background:Staphylococcus aureus is a human colonizer with high potential for virulence, and the spread of the virulent strains from the colonized hosts to non-carriers in the community is on the increase. However, there are few reports on comprehensive analysis of staphylococcal enterotoxin (SE) genes with clonal line...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.5204

    authors: Ayeni FA,Ruppitsch W,Allerberger F

    更新日期:2018-07-09 00:00:00

  • Evidence for the Cretaceous shark Cretoxyrhina mantelli feeding on the pterosaur Pteranodon from the Niobrara Formation.

    abstract::A cervical vertebra of the large, pelagic pterodactyloid pterosaur Pteranodon sp. from the Late Cretaceous Niobrara Formation of Kansas, USA is significant for its association with a tooth from the large lamniform shark, Cretoxyrhina mantelli. Though the tooth does not pierce the vertebral periosteum, the intimate ass...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.6031

    authors: Hone DWE,Witton MP,Habib MB

    更新日期:2018-12-14 00:00:00

  • Bunyaviruses are common in male and female Ixodes scapularis ticks in central Pennsylvania.

    abstract::The blacklegged tick Ixodes scapularis is widely distributed in the United States and transmits multiple pathogens to humans, wildlife and domestic animals. Recently, several novel viruses in the family Bunyaviridae (South Bay virus (SBV) and Blacklegged tick phlebovirus (BTPV)) were identified infecting female I. sca...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.2324

    authors: Sakamoto JM,Ng TFF,Suzuki Y,Tsujimoto H,Deng X,Delwart E,Rasgon JL

    更新日期:2016-08-11 00:00:00

  • Test re-test reliability and construct validity of the star-track test of manual dexterity.

    abstract::Objectives. We wished to determine test re-test reliability and construct validity of the star-track test of manual dexterity. Design. Test re-test reliability was examined in a controlled study. Construct validity was tested in a blinded randomized crossover study. Setting. The study was performed at a university hos...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.917

    authors: Kildebro N,Amirian I,Gögenur I,Rosenberg J

    更新日期:2015-04-23 00:00:00

  • Clinical significance of pretreatment prognostic nutritional index and lymphocyte-to-monocyte ratio in patients with advanced p16-negative oropharyngeal cancer-a retrospective study.

    abstract:Background:Systemic inflammation and nutritional status both play roles in the survival of cancer patients. Therefore, it is important to understand the effects of prognostic nutritional index (PNI) and lymphocyte-to-monocyte ratio (LMR) on the survival of patients with advanced p16-negative oropharyngeal cancer. Meth...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.10465

    authors: Tsai MH,Huang TL,Chuang HC,Lin YT,Fang FM,Lu H,Chien CY

    更新日期:2020-12-01 00:00:00

  • Exercise mode and attentional networks in older adults: a cross-sectional study.

    abstract:Background:Previous studies have indicated that physical exercise enhances attentional function; however, the relationship between exercise mode and attentional networks has not been clarified for older adults (>60 years old). This study aimed to investigate the relationship between attentional networks and different e...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.8364

    authors: Wang B,Guo W

    更新日期:2020-01-07 00:00:00

  • Testing the short-and long-term effects of elevated prenatal exposure to different forms of thyroid hormones.

    abstract::Maternal thyroid hormones (THs) are known to be crucial in embryonic development in humans, but their influence on other, especially wild, animals remains poorly understood. So far, the studies that experimentally investigated the consequences of maternal THs focused on short-term effects, while early organisational e...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.10175

    authors: Sarraude T,Hsu BY,Groothuis T,Ruuskanen S

    更新日期:2020-10-16 00:00:00

  • Repeated hands-and-knees positioning during labour: a randomized pilot study.

    abstract::Background. Caesarean birth rates in North America continue to rise, in the absence of benefit for mothers and babies. One reason may be that hospitalized labouring women spend most of their labours in recumbent or semi-recumbent positions. Although hands-and-knees position has theoretical advantages, efforts to encou...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.25

    authors: Hodnett ED,Stremler R,Halpern SH,Weston J,Windrim R

    更新日期:2013-02-12 00:00:00

  • Survival of side grafts with scions from pure species Pinus engelmannii Carr. and the P. engelmannii × P. arizonica Engelm. var. arizonica hybrid.

    abstract::Grafting is one of the most widely used methods for vegetative propagation, particularly for multiplying trees considered important, but there has been little research done on the effect of hybridization on grafts from the genus Pinus. Sometimes hybrids show the ability to reproduce and adapt efficiently to the enviro...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.8468

    authors: Pérez-Luna A,Wehenkel C,Prieto-Ruíz JÁ,López-Upton J,Hernández-Díaz JC

    更新日期:2020-02-07 00:00:00

  • Deep-sea water displacement from a turbidity current induced by the Super Typhoon Hagibis.

    abstract::Turbidity currents are the main drivers behind the transportation of terrestrial sediments to the deep sea, and turbidite deposits from such currents have been widely used in geological studies. Nevertheless, the contribution of turbidity currents to vertical displacement of seawater has rarely been discussed. This is...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.10429

    authors: Kawagucci S,Miwa T,Lindsay DJ,Ogura E,Yamamoto H,Nishibayashi K,Yokooka H,Nishi S,Takahashi A,Lee S

    更新日期:2020-12-09 00:00:00

  • Potential wound healing activity of Quercus infectoria formulation in diabetic rats.

    abstract:BACKGROUND:Quercus infectoria G. Olivier (Fagaceae) nutgalls have been widely employed in traditional Asian medicine for several treatments, especially wounds and skin disorders. However, the effects of this plant on wound healing have not yet been clearly elucidated. This present work was focused on utilization of Que...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.3608

    authors: Chokpaisarn J,Chusri S,Amnuaikit T,Udomuksorn W,Voravuthikunchai SP

    更新日期:2017-07-24 00:00:00

  • Global mapping of potential natural vegetation: an assessment of machine learning algorithms for estimating land potential.

    abstract::Potential natural vegetation (PNV) is the vegetation cover in equilibrium with climate, that would exist at a given location if not impacted by human activities. PNV is useful for raising public awareness about land degradation and for estimating land potential. This paper presents results of assessing machine learnin...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.5457

    authors: Hengl T,Walsh MG,Sanderman J,Wheeler I,Harrison SP,Prentice IC

    更新日期:2018-08-22 00:00:00

  • Can non-destructive DNA extraction of bulk invertebrate samples be used for metabarcoding?

    abstract:Background:High throughput DNA sequencing of bulk invertebrate samples or metabarcoding is becoming increasingly used to provide profiles of biological communities for environmental monitoring. As metabarcoding becomes more widely applied, new reference DNA barcodes linked to individual specimens identified by taxonomi...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.4980

    authors: Carew ME,Coleman RA,Hoffmann AA

    更新日期:2018-06-13 00:00:00

  • Antioxidant activity and mechanism of commercial Rama Forte persimmon fruits (Diospyros kaki).

    abstract::This study aimed to characterize the antioxidant properties of Rama Forte persimmon, a tannin-rich fruit variety produced in Brazil. Extracts prepared with lyophilized pulps from fruits obtained in local markets were analyzed individually to evaluate the extent of antioxidant protection and investigate the antioxidant...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.5223

    authors: Dalvi LT,Moreira DC,Alonso A,de Avellar IGJ,Hermes-Lima M

    更新日期:2018-07-25 00:00:00

  • Mitochondrial genome of the nonphotosynthetic mycoheterotrophic plant Hypopitys monotropa, its structure, gene expression and RNA editing.

    abstract::Heterotrophic plants-plants that have lost the ability to photosynthesize-are characterized by a number of changes at all levels of organization. Heterotrophic plants are divided into two large categories-parasitic and mycoheterotrophic (MHT). The question of to what extent such changes are similar in these two catego...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.9309

    authors: Shtratnikova VY,Schelkunov MI,Penin AA,Logacheva MD

    更新日期:2020-06-19 00:00:00

  • Physical activity and pre-diabetes-an unacknowledged mid-life crisis: findings from NHANES 2003-2006.

    abstract::The prevalence of pre-diabetes (PD) among US adults has increased substantially over the past two decades. By current estimates, over 34% of US adults fall in the PD category, 84% of whom meet the American Diabetes Association's criteria for impaired fasting glucose (IFG). Low physical activity (PA) and/or sedentary b...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.499

    authors: Farni K,Shoham DA,Cao G,Luke AH,Layden J,Cooper RS,Dugas LR

    更新日期:2014-08-19 00:00:00

  • Warm temperatures, cool sponges: the effect of increased temperatures on the Antarctic sponge Isodictya sp.

    abstract::Although the cellular and molecular responses to exposure to relatively high temperatures (acute thermal stress or heat shock) have been studied previously, only sparse empirical evidence of how it affects cold-water species is available. As climate change becomes more pronounced in areas such as the Western Antarctic...

    journal_title:PeerJ

    pub_type: 杂志文章

    doi:10.7717/peerj.8088

    authors: González-Aravena M,Kenny NJ,Osorio M,Font A,Riesgo A,Cárdenas CA

    更新日期:2019-12-03 00:00:00