Evaluating intraspecific "network" construction methods using simulated sequence data: do existing algorithms outperform the global maximum parsimony approach?

In intraspecific studies, reticulated graphs are valuable tools for visualization, within a single figure, of alternative genealogical pathways among haplotypes. As available software packages implementing the global maximum parsimony (MP) approach only give the possibility to merge resulting topologies into less-resolved consensus trees, MP has often been neglected as an alternative approach to purely algorithmic (i.e., methods defined solely on the basis of an algorithm) "network" construction methods. Here, we propose to search tree space using the MP criterion and present a new algorithm for uniting all equally most parsimonious trees into a single (possibly reticulated) graph. Using simulated sequence data, we compare our method with three purely algorithmic and widely used graph construction approaches (minimum-spanning network, statistical parsimony, and median-joining network). We demonstrate that the combination of MP trees into a single graph provides a good estimate of the true genealogy. Moreover, our analyses indicate that, when internal node haplotypes are not sampled, the median-joining and MP methods provide the best estimate of the true genealogy whereas the minimum-spanning algorithm shows very poor performances.     

中国蛛缘蝽科物种DNA条形码研究(英文)

【目的】本研究旨在探讨DNA条形码对中国蛛缘蝽科(半翅目：缘蝽总科)物种界定的适用性。【方法】对中国蛛缘蝽科13属23种207个样本的线粒体COI基因DNA条形码序列进行扩增,并扩增稻缘蝽属Leptocorisa 3个物种的31条内转录间隔区1(ITS-1)序列作为辅助标记。使用MEGA 11软件计算种间和种内遗传距离(Kimura 2-parameter, K2P);采用邻接法(neighbor-joining, NJ)进行物种聚类分析;利用中介邻接网络算法构建单倍型网络图。【结果】基于线粒体COI DNA条形码序列得出测试的中国蛛缘蝽科所有23个种的种内平均K2P距离在2%以下,种间K2P距离在0.98%~23.98%之间(平均17.50%)。多数物种彼此能够被较好地分开,且支持率较高。其中,中稻缘蝽Leptocorisa chinensis和大稻缘蝽L. oratoria共享部分COI单倍型,造成COI条形码无法区分二者,可通过ITS-1序列在单倍型网络分析中将二者区分。【结论】本研究得出的中国蛛缘蝽科中绝大部分物种的DNA条形码数据分析结果与基于形态特征的分类单元一致。然而,对于其中亲缘关系极近的物种,单靠线粒体数据尤其是COI条形码序列无法进行准确界定,需引入其他DNA序列或其他类型数据进行区分。     

Mitochondrial Portraits of Human Populations Using Median Networks

Analysis of variation in the hypervariable region of mitochondrial DNA (mtDNA) has emerged as an important tool for studying human evolution and migration. However, attempts to reconstruct optimal intraspecific mtDNA phylogenies frequently fail because parallel mutation events partly obscure the true evolutionary pathways. This makes it inadvisable to present a single phylogenetic tree at the expense of neglecting equally acceptable ones. As an alternative, we propose a novel network approach for portraying mtDNA relationships. For small sample sizes (< ~50), an unmodified median network contains all most parsimonious trees, displays graphically the full information content of the sequence data, and can easily be generated by hand. For larger sample sizes, we reduce the complexity of the network by identifying parallelisms. This reduction procedure is guided by a compatibility argument and an additional source of phylogenetic information: the frequencies of the mitochondrial haplotypes. As a spin-off, our approach can also assist in identifying sequencing errors, which manifest themselves in implausible network substructures. We illustrate the advantages of our approach with several examples from existing data sets.     

Phylogenetic relationships of North American garter snakes (Thamnophis) based on four mitochondrial genes: how much DNA sequence is enough?

The clade of garter snakes (Thamnophis) includes some of the most abundant and well-studied snakes in North America. However, phylogenetic relationships within this group have been little studied. We used DNA sequences of four mitochondrial genes (cytochrome b and NADH dehydrogenase subunits 1, 2, and 4) to estimate relationships among 29 of the 31 recognized species of Thamnophis plus the related species Adelophis foxi. Both maximum parsimony (MP) and maximum-likelihood (ML) analyses of all these genes combined produced well-resolved trees with moderate (70-89%) to strong (90-100%) bootstrap support for most clades. MP and ML trees were very similar, with no strongly supported conflict between the two analyses. These analyses identify a clade of 12 species largely restricted to México (the "Mexican clade"), and a clade containing 15 species that collectively range from Central America to southern Canada (the "widespread clade"). These two groups are identified as sister taxa in both MP and ML analyses. A clade consisting of the ribbon snakes (T. sauritus and T. proximus) and the common garter snake (T. sirtalis) is placed as the sister group to all other Thamnophis (i.e., the Mexican + widespread clades) in our analyses. High bootstrap proportions at several levels in the tree support the inclusion of both Thamnophis validus, which has traditionally been placed in the genus Nerodia, and the poorly known species Adelophis foxi within Thamnophis. We used randomly sampled characters (i.e., standard bootstrapping) and randomly sampled contiguous blocks of characters to examine the effect of number of characters on resolution of and support for relationships within Thamnophis using MP. In general, these analyses indicate that we have reached a point of strongly diminishing returns with respect to the effect of adding mtDNA sequence characters for the current set of taxa; our sample of 3809 mtDNA characters is apparently "enough." The next steps to improve the phylogenetic estimate may be to add nuclear DNA sequences, morphology, or behavior, or to sequence additional mtDNA lineages within species.     

Trees and/or networks to display intraspecific DNA sequence variation?

Phylogenetic trees and networks are both used in the scientific literature to display DNA sequence variation at the intraspecific level. Should we rather use trees or networks? I argue that the process of inferring the most parsimonious genealogical relationships among a set of DNA sequences should be dissociated from the problem of displaying this information in a graph. A network graph is probably more appropriate than a strict consensus tree if many alternative, equally most parsimonious, genealogies are to be included. Within the maximum parsimony framework, current phylogenetic inference and network‐building algorithms are both unable to guarantee the finding of all most parsimonious (MP) connections. In fact, each approach can find MP connections that the other does not. Although it should be possible to improve at least the maximum parsimony approach, current implementations of these algorithms are such that it is advisable to use both approaches to increase the probability of finding all possible MP connections among a set of DNA sequences.     

Distilling artificial recombinants from large sets of complete mtDNA genomes

Background

Large-scale genome sequencing poses enormous problems to the logistics of laboratory work and data handling. When numerous fragments of different genomes are PCR amplified and sequenced in a laboratory, there is a high immanent risk of sample confusion. For genetic markers, such as mitochondrial DNA (mtDNA), which are free of natural recombination, single instances of sample mix-up involving different branches of the mtDNA phylogeny would give rise to reticulate patterns and should therefore be detectable.

Methodology/Principal Findings

We have developed a strategy for comparing new complete mtDNA genomes, one by one, to a current skeleton of the worldwide mtDNA phylogeny. The mutations distinguishing the reference sequence from a putative recombinant sequence can then be allocated to two or more different branches of this phylogenetic skeleton. Thus, one would search for two (or three) near-matches in the total mtDNA database that together best explain the variation seen in the recombinants. The evolutionary pathway from the mtDNA tree connecting this pair together with the recombinant then generate a grid-like median network, from which one can read off the exchanged segments.

Conclusions

We have applied this procedure to a large collection of complete human mtDNA sequences, where several recombinants could be distilled by our method. All these recombinant sequences were subsequently corrected by de novo experiments – fully concordant with the predictions from our data-analytical approach.     

从细胞色素b基因序列变异分析中国鲇形目鱼类的系统发育

采用PCR技术获得中国鲇形目鱼类11科24属27个代表种类细胞色素b基因1138bp全序列,比较分析了来自北美洲、非洲的部分鲇形目鱼类同一基因序列,并选取脂鲤目、鲤形目和鲱形目鱼类作外类群,采用Bayesian方法和最大简约法(MP)构建分子系统树。结果表明：(1)鲇形目鱼类细胞色素b基因序列中,与脂鲤目、鲤形目以及鲱形目鱼类相比存在3bp的缺失;(2)鲇形目鱼类各科代表种类形成一单系群;(3)两种建树方法均支持铫科、粒鲇科和钝头鮠科形成一单系群;而胡子鲇科、刀鲇科、海鲇科、鮰科、长臀鮠科、鲢科、鲇科、棘脂鲿科、鲿科形成一大的单系群;但鳗鲇科的系统位置两种建树方法没有取得一致结果;而其中长臀鲍科与北美的鮰科形成姐妹群,胡子鲇、鮰科、鲇科、鲿科和鮡科是较明显的单系群。     

Fast recovery of evolutionary trees with thousands of nodes.

We present a novel distance-based algorithm for evolutionary tree reconstruction. Our algorithm reconstructs the topology of a tree with n leaves in O(n(2)) time using O(n) working space. In the general Markov model of evolution, the algorithm recovers the topology successfully with (1 - o(1)) probability from sequences with polynomial length in n. Moreover, for almost all trees, our algorithm achieves the same success probability on polylogarithmic sample sizes. The theoretical results are supported by simulation experiments involving trees with 500, 1,895, and 3,135 leaves. The topologies of the trees are recovered with high success from 2,000 bp DNA sequences.     

用线粒体tRNA基因探讨现存两栖动物三个目间系统发生关系

现存两栖类3个目的系统发生关系仍然没有统一意见,最广泛被接受的假说是单系起源,并且无尾类和有尾类为姐妹群关系而排斥蚓螈类(蛙类假说)。然而,这一假说一直存在争议。我们在测定了泽蛙线粒体基因组全序列的基础上,与已知其他的6种两栖类进行详细的比较分析,同时选择了11种高等脊椎动物的线粒体全基因序列,以硬骨鱼类作外群,用22个tRNA基因合并数据进行系统发生重建分析,结果表明MP、ML树都强力地支持现生两栖类动物为单系群,并且有尾目和蚓螈目为姐妹群关系。这个结果与蛙类假说是相矛盾的,与Bolt(1991)在形态学基础上提出的有尾类和蚓螈类为姐妹群关系的假说相一致,并得到建立在线粒体和核rRNA基因数据基础上的许多分子研究的支持。另外还探讨了本结果与前人的研究不一致的原因,以及利用线粒体全基因序列进行系统发生分析可能存在的偏差。     

Statistical properties of bootstrap estimation of phylogenetic variability from nucleotide sequences: II. Four taxa without a molecular clock

Summary The statistical properties of sample estimation and bootstrap estimation of phylogenetic variability from a sample of nucleotide sequences were studied by considering model trees of three taxa with an outgroup. The cases of constant and varying rates of nucleotide substitution were compared. From sequences obtained by simulation, phylogenetic trees were constructed by using the maximum parsimony (MP) and neighbor joining (NJ) methods. The effectiveness and consistency of the MP method were studied in terms of proportions of informative sites. The results of simulation showed that bootstrap estimation of the confidence level for an inferred phylogeny can be used even under unequal rates of evolution if the rate differences are not large so that the MP method is not misleading. The condition under which the MP method becomes misleading (inconsistent) is more stringent for slowly evolving sequences than for rapidly evolving ones, and it also depends on the length of the internal branch. If the rate differences are large so that the MP method becomes consistently misleading, then bootstrap estimation will reinforce an erroneous conclusion on topology. Similar conclusions apply to the NJ method with uncorrected distances. The NJ method with corrected distances performs poorly when the sequence length is short but can avoid the inconsistency problem if the sequence length is long and if the distances can be estimated accurately.Offprint requests to: W.-H. Li     

豉甲科及水生肉食亚目的分子系统发育学分析(昆虫纲：鞘翅目)

利用PAUP和MrBayes软件,对线粒体COⅠ基因序列3个密码子位置的数据模块分别进行了豉甲科(Gyrinidae)和水生肉食亚目(Hydradephaga)在亚科或科水平上的系统发育学分析,结果表明第二密码子数据模块获得了理想的分析结果。由PAUP生成的豉甲科最优树来自第二密码子数据模块的分析,而由MrBayes生成的最优树来自全部密码子数据模块的分析。此外,用对应的氨基酸序列生成的ME和MP树与第二密码子数据模块分析的结果也一致。亚科Orectochilinae和Gyrininae以高的支持率形成了单系。然而,来自亚科Enhydrinae的种Porrorhynchus landaisi landaisi呈现了异常的位置。SH-test检验也支持该异常位置,表明这个种可能代表了一个科。在来自第二密码子数据模块的水生肉食亚目最优ML树中,整个Hydradephaga树呈现单系,豉甲科位于树的基部,表明了该科在水生肉食亚目中是一个早期的分支。在树中还产生了一个单系的Dytiscoidea总科,由Dytiscidae、Hygrobiidae、Noteridae和Amphizoidae 4个科组成,单系的Haliplidae与之成为姐妹群。此外线粒体分子钟的结果表明豉甲科的5对相近种间的分化是一个短时期内发生的(0.01～1.81百万年前),这点可能与它们的特殊地理分布有关。     

A molecular phylogenetic study of the freshwater talitrid amphipod Orchestia cavimana (Crustacea).

In this paper we performed a molecular phylogenetic study of Orchestia cavimana, the sole talitrid amphipod inhabiting beaches of European freshwater lakes and rivers. For that purpose, we have PCR amplified and sequenced regions of the mitochondrial cytochrome oxidase subunit I (COI) gene, basing our analysis on both nucleotide and amino acid sequences and considering also structural classes of the COI enzyme. Phylogenetic analyses were conducted by neighbour-joining (NJ) and maximum-parsimony (MP) methods comparing homologous sequences of talitrids and other Crustacea. In both NJ and MP trees, O. cavimana shows a basal placement with respect to other talitrid amphipods.     

Alignment and phylogenetic analysis of beta-fibrinogen intron 7 sequences among avian orders reveal conserved regions within the intron

We sequenced beta-fibrinogen intron 7 (beta-fibint 7) from 28 species of birds, representing 18 families in nine orders. Although the antiquity of the avian orders is estimated to be 55 to 90 Myr, and numerous indels have accrued among diverging lineages, the intron sequences were not difficult to align. However, alignment of avian sequences with mammal or snake sequences was difficult, and the residual phylogenetic signal was weak. beta-fibint 7 is an AT-rich intron, and its base composition varies little over the diversity of birds represented by our sample. Alignment of these anciently diverged sequences reveals at least five clusters of conserved nucleotides; at least two clusters appear to be in excess of the minimal set usually associated with intron excision, but their functions are unknown. Two equally most-parsimonious (MP) trees were found when indels were not included in the phylogenetic analysis, and six such trees were found when indels were included. The Neighbor-Joining and maximum-likelihood trees were identical to each other and to one of the MP trees in each MP analysis. Indels, as well as nucleotide substitutions, are phylogenetically informative, and bootstrap support exceeded 90% for 21 of 24 inferred nodes when indels were included in the MP analysis. All traditional orders represented by two or more species appear monophyletic. Relationships among avian orders are strongly supported with the exception of an inferred sister-group relationship between Caprimulgiformes and Columbiformes. A relatively close relationship between Piciformes and Passeriformes is inferred, at odds with earlier DNA-DNA hybridization studies but consistent with traditional classifications. Among Passeriformes, the traditional perspective of a sister-group relationship of suboscines and oscines is supported, as is the subsequent split of the oscines into a lineage representative of the Corvida before the diversification of the Passerida. The four species of owls divide into two strongly supported clades, corresponding to the widely accepted bifurcation of owls into two families, Tytonidae and Strigidae. A sister-group relationship between gallinaceous birds and waterfowl, the Galloanserae, is also strongly supported.     

Phylogenetic relationships among holarctic populations of Chironomus entis and Chironomus plumosus in view of possible horizontal transfer of mitochondrial genes

In eight Holarctic populations of two typical chironomid sibling species of the plumosus group, Chrionomus entis and Chironomus plumosus, nucleotides sequences of mitochondrial (cytb) and nuclear (gb2b) gene regions were examined. The phylogenetic trees reflecting the evolutionary histories of the nuclear and mitochondrial markers exhibited significant differences. On the tree based on the nuclear gene sequences the populations clustered according to their species affiliation, whereas on the tree based on the mitochondrial gene sequences the populations were grouped according to their geographic position. This discrepancy is probably explained by mitochondrial gene flow between sympatric species with incomplete reproductive isolation (sibling species). Based on our results together with the earlier data on nuclear and mitochondrial gene sequences of some other species from the phylogenetic group plumosus, a scheme of phylogenetic relationships within this group is proposed. This scheme is in many ways different from the traditional view on the evolutionary relationships among species of the plumosus group.     

基于线粒体16S rRNA基因对中国狼蛛科(Lycosidae)系统发育研究

将自测的中国狼蛛科Lycosidae4亚科6属26种和从GenBank中检索到的北美2种豹蛛的mtD-NA-16S rRNA序列进行比较;以漏斗蛛科1种蜘蛛作为外群,对碱基序列的组成和遗传距离进行了分析,采用Bayesian方法和最大简约法(MP)构建分子系统树。研究结果表明:16SrRNA基因的部分序列为340bp到360bp,A T含量平均为75%,存在较强的A T含量偏向性;序列共有157个碱基存在变异,其中79个简约信息位点。狼蛛科各属间的遗传距离介于0.026￣0.200之间。2种建树方法均表明:科内的属及属内的种优先聚在一起;水狼蛛属相对马蛛属是狼蛛科中较为原始的类群,分化较早;獾蛛属作为1个单系群与熊蛛属合为1个并系,属于狼蛛亚科。狼蛛科6属间的分子系统关系为(Pirata(Hippasa(Trochsa Arctosa(Pardosa Wadicosa))))。     

Molecular Phylogeny of the Genus Paramesotriton (Caudata: Salamandridae)

To elucidate the phylogeny of the genus Paramesotriton (Caudata: Salamandridae), we investigated three mitochondrial DNA gene fragments (1207 bp in total) of cytochrome b, ND2, and ND4 for its six recognized species. The phylogenetic relationships within Paramesotriton were reconstructed by maximum parsimony (MP) and maximum likelihood (ML) methods. Phylogenetic trees (MP and ML trees) that were constructed from the combined data set of the three gene fragments indicated that all six species of Paramesotriton formed a monophyletic group, with P. caudopunctatus as basal to the other five species. This result suggests that P. fuzhongensis is a valid species in Paramesotriton.     

Combined nuclear and mitochondrial DNA sequences resolve generic relationships within the Cracidae (Galliformes,Aves)

The Cracidae is one of the most endangered and distinctive bird families in the Neotropics, yet the higher relationships among taxa remain uncertain. The molecular phylogeny of its 11 genera was inferred using 10,678 analyzable sites (5,412 from seven different mitochondrial segments and 5,266 sites from four nuclear genes). We performed combinability tests to check conflicts in phylogenetic signals of separate genes and genomes. Phylogenetic analysis showed that the unrooted tree of ((curassows, horned guan) (guans, chachalacas)) was favored by most data partitions and that different data partitions provided support for different parts of the tree. In particular, the concatenated mitochondrial DNA (mtDNA) genes resolved shallower nodes, whereas the combined nuclear sequences resolved the basal connections among the major clades of curassows, horned guan, chachalacas, and guans. Therefore, we decided that for the Cracidae all data should be combined for phylogenetic analysis. Maximum parsimony (MP), maximum likelihood (ML), and Bayesian analyses of this large data set produced similar trees. The MP tree indicated that guans are the sister group to (horned guan, (curassows, chachalacas)), whereas the ML and Bayesian analysis recovered a tree where the horned guan is a sister clade to curassows, and these two clades had the chachalacas as a sister group. Parametric bootstrapping showed that alternative trees previously proposed for the cracid genera are significantly less likely than our estimate of their relationships. A likelihood ratio test of the hypothesis of a molecular clock for cracid mtDNA sequences using the optimal ML topology did not reject rate constancy of substitutions through time. We estimated cracids to have originated between 64 and 90 million years ago (MYA), with a mean estimate of 76 MYA. Diversification of the genera occurred approximately 41-3 MYA, corresponding with periods of global climate change and other Earth history events that likely promoted divergences of higher level taxa.     

Relative efficiencies of the maximum parsimony and distance-matrix methods in obtaining the correct phylogenetic tree

The relative efficiencies of the maximum parsimony (MP) and distance-matrix methods in obtaining the correct tree (topology) were studied by using computer simulation. The distance-matrix methods examined are the neighbor-joining, distance-Wagner, Tateno et al. modified Farris, Faith, and Li methods. In the computer simulation, six or eight DNA sequences were assumed to evolve following a given model tree, and the evolutionary changes of the sequences were followed. Both constant and varying rates of nucleotide substitution were considered. From the sequences thus obtained, phylogenetic trees were constructed using the six tree-making methods and compared with the model (true) tree. This process was repeated 300 times for each different set of parameters. The results obtained indicate that when the number of nucleotide substitutions per site is small and a relatively small number of nucleotides are used, the probability of obtaining the correct topology (P1) is generally lower in the MP method than in the distance-matrix methods. The P1 value for the MP method increases with increasing number of nucleotides but is still generally lower than the value for the NJ or DW method. Essentially the same conclusion was obtained whether or not the rate of nucleotide substitution was constant or whether or not a transition bias in nucleotide substitution existed. The relatively poor performance of the MP method for these cases is due to the fact that information from singular sites is not used in this method. The MP method also showed a relatively low P1 value when the model of varying rate of nucleotide substitution was used and the number of substitutions per site was large. However, the MP method often produced cases in which the correct tree was one of several equally parsimonious trees. When these cases were included in the class of "success," the MP method performed better than the other methods, provided that the number of nucleotide substitutions per site was small.     

The average common substring approach to phylogenomic reconstruction.

We describe a novel method for efficient reconstruction of phylogenetic trees, based on sequences of whole genomes or proteomes, whose lengths may greatly vary. The core of our method is a new measure of pairwise distances between sequences. This measure is based on computing the average lengths of maximum common substrings, which is intrinsically related to information theoretic tools (Kullback-Leibler relative entropy). We present an algorithm for efficiently computing these distances. In principle, the distance of two l long sequences can be calculated in O(l) time. We implemented the algorithm using suffix arrays our implementation is fast enough to enable the construction of the proteome phylogenomic tree for hundreds of species and the genome phylogenomic forest for almost two thousand viruses. An initial analysis of the results exhibits a remarkable agreement with "acceptable phylogenetic and taxonomic truth." To assess our approach, our results were compared to the traditional (single-gene or protein-based) maximum likelihood method. The obtained trees were compared to implementations of a number of alternative approaches, including two that were previously published in the literature, and to the published results of a third approach. Comparing their outcome and running time to ours, using a "traditional" trees and a standard tree comparison method, our algorithm improved upon the "competition" by a substantial margin. The simplicity and speed of our method allows for a whole genome analysis with the greatest scope attempted so far. We describe here five different applications of the method, which not only show the validity of the method, but also suggest a number of novel phylogenetic insights.     

Inferring phylogenetic networks by the maximum parsimony criterion: a case study

Horizontal gene transfer (HGT) may result in genes whose evolutionary histories disagree with each other, as well as with the species tree. In this case, reconciling the species and gene trees results in a network of relationships, known as the "phylogenetic network" of the set of species. A phylogenetic network that incorporates HGT consists of an underlying species tree that captures vertical inheritance and a set of edges which model the "horizontal" transfer of genetic material. In a series of papers, Nakhleh and colleagues have recently formulated a maximum parsimony (MP) criterion for phylogenetic networks, provided an array of computationally efficient algorithms and heuristics for computing it, and demonstrated its plausibility on simulated data. In this article, we study the performance and robustness of this criterion on biological data. Our findings indicate that MP is very promising when its application is extended to the domain of phylogenetic network reconstruction and HGT detection. In all cases we investigated, the MP criterion detected the correct number of HGT events required to map the evolutionary history of a gene data set onto the species phylogeny. Furthermore, our results indicate that the criterion is robust with respect to both incomplete taxon sampling and the use of different site substitution matrices. Finally, our results show that the MP criterion is very promising in detecting HGT in chimeric genes, whose evolutionary histories are a mix of vertical and horizontal evolution. Besides the performance analysis of MP, our findings offer new insights into the evolution of 4 biological data sets and new possible explanations of HGT scenarios in their evolutionary history.