phyBWT2: phylogeny reconstruction via eBWT positional clustering

Algorithms for Molecular Biology

Research

Gianni Liti¹  Lorenzo Tattini¹  Veronica Guerrini²  Alessio Conte²  Roberto Grossi²  Giovanna Rosone² 

[1] CNRS UMR 7284, INSERM U1081 Université Côte d’Azu, Nice, France;Dipartimento di Informatica, University of Pisa, Pisa, Italy;

关键词: Phylogeny;    Partition tree;    BWT;    Positional cluster;    Alignment-free;    Reference-free;    Assembly-free;   

DOI  :  10.1186/s13015-023-00232-4

 received in 2023-03-31, accepted in 2023-06-10,  发布年份 2023

来源: Springer

【 摘 要 】

BackgroundMolecular phylogenetics studies the evolutionary relationships among the individuals of a population through their biological sequences. It may provide insights about the origin and the evolution of viral diseases, or highlight complex evolutionary trajectories. A key task is inferring phylogenetic trees from any type of sequencing data, including raw short reads. Yet, several tools require pre-processed input data e.g. from complex computational pipelines based on de novo assembly or from mappings against a reference genome. As sequencing technologies keep becoming cheaper, this puts increasing pressure on designing methods that perform analysis directly on their outputs. From this viewpoint, there is a growing interest in alignment-, assembly-, and reference-free methods that could work on several data including raw reads data.ResultsWe present phyBWT2, a newly improved version of phyBWT (Guerrini et al. in 22nd International Workshop on Algorithms in Bioinformatics (WABI) 242:23–12319, 2022). Both of them directly reconstruct phylogenetic trees bypassing both the alignment against a reference genome and de novo assembly. They exploit the combinatorial properties of the extended Burrows-Wheeler Transform (eBWT) and the corresponding eBWT positional clustering framework to detect relevant blocks of the longest shared substrings of varying length (unlike the k-mer-based approaches that need to fix the length k a priori). As a result, they provide novel alignment-, assembly-, and reference-free methods that build partition trees without relying on the pairwise comparison of sequences, thus avoiding to use a distance matrix to infer phylogeny. In addition, phyBWT2 outperforms phyBWT in terms of running time, as the former reconstructs phylogenetic trees step-by-step by considering multiple partitions, instead of just one partition at a time, as previously done by the latter.ConclusionsBased on the results of the experiments on sequencing data, we conclude that our method can produce trees of quality comparable to the benchmark phylogeny by handling datasets of different types (short reads, contigs, or entire genomes). Overall, the experiments confirm the effectiveness of phyBWT2 that improves the performance of its previous version phyBWT, while preserving the accuracy of the results.

【 授权许可】

CC BY   
© BioMed Central Ltd., part of Springer Nature 2023

【 图 表 】

Fig. 3

Fig. 2

Fig. 4

Fig. 1

Fig. 2

Fig. 3

12888_2023_5113_Article_IEq8.gif

Fig. 2

Fig. 3

Fig. 2

Fig. 2

Fig. 2

Fig. 8

Fig. 2

Fig. 6

12888_2023_5012_Article_IEq5.gif

Fig. 7

12888_2023_5012_Article_IEq4.gif

12888_2023_5012_Article_IEq3.gif

Fig. 1

12888_2023_5012_Article_IEq2.gif

12888_2023_5113_Article_IEq7.gif

12888_2023_5113_Article_IEq6.gif

12888_2023_5113_Article_IEq5.gif

12888_2023_5113_Article_IEq4.gif

12888_2023_5113_Article_IEq3.gif

12888_2023_5113_Article_IEq2.gif

12888_2023_5113_Article_IEq1.gif

Fig. 4

Fig. 1

Fig. 3

40517_2023_261_Article_IEq28.gif

Fig. 1

Fig. 2

40517_2023_261_Article_IEq24.gif

40517_2023_261_Article_IEq45.gif

Fig. 3

40517_2023_261_Article_IEq43.gif

Fig. 2

Fig. 2

40517_2023_261_Article_IEq40.gif

Fig. 1

Fig. 1

40517_2023_261_Article_IEq37.gif

40517_2023_261_Article_IEq36.gif

40517_2023_261_Article_IEq35.gif

40517_2023_261_Article_IEq34.gif

40517_2023_261_Article_IEq31.gif

40517_2023_261_Article_IEq30.gif

Fig. 1

Fig. 1

13690_2023_1154_Article_IEq16.gif

Fig. 1

13690_2023_1154_Article_IEq14.gif

13690_2023_1154_Article_IEq13.gif

40517_2023_261_Article_IEq17.gif

13690_2023_1154_Article_IEq12.gif

13690_2023_1154_Article_IEq18.gif

13690_2023_1154_Article_IEq11.gif

13690_2023_1154_Article_IEq10.gif

13690_2023_1154_Article_IEq17.gif

13690_2023_1154_Article_IEq8.gif

13690_2023_1154_Article_IEq7.gif

Fig. 4

Fig. 1

Fig. 8

Fig. 2

12974_2023_2864_Article_IEq1.gif

Fig. 7

Fig. 2

42004_2023_982_Article_IEq18.gif

Fig. 6

42004_2023_982_Article_IEq16.gif

42004_2023_982_Article_IEq15.gif

Fig. 1

Fig. 1

13068_2023_2361_Article_IEq16.gif

Fig. 5

13068_2023_2361_Article_IEq14.gif

13690_2023_1154_Article_IEq1.gif

Fig. 1

Fig. 1

Fig. 4

Fig. 1

Fig. 4

Fig. 3

42490_2023_74_Article_IEq62.gif

Fig. 1

Fig. 3

13068_2023_2361_Article_IEq1.gif

Fig. 2

42490_2023_74_Article_IEq59.gif

13690_2023_1172_Article_IEq8.gif

13690_2023_1172_Article_IEq7.gif

13690_2023_1172_Article_IEq6.gif

13690_2023_1172_Article_IEq5.gif

Fig. 1

13690_2023_1172_Article_IEq2.gif

13690_2023_1172_Article_IEq1.gif

Fig. 1

Fig. 1

Fig. 1

Fig. 5

Fig. 1

42490_2023_74_Article_IEq50.gif

Fig. 6

Fig. 4

Fig. 4

Fig. 1

Fig. 2

Fig. 3

Fig. 1

Fig. 1

Fig. 2

42490_2023_74_Article_IEq42.gif

Fig. 4

42490_2023_74_Article_IEq40.gif

42490_2023_74_Article_IEq39.gif

42490_2023_74_Article_IEq38.gif

Fig. 3

42490_2023_74_Article_IEq37.gif

42490_2023_74_Article_IEq36.gif

42490_2023_74_Article_IEq35.gif

Fig. 3

Fig. 9

Fig. 1

Fig. 1

42490_2023_74_Article_IEq30.gif

42490_2023_74_Article_IEq29.gif

Fig. 3

42490_2023_74_Article_IEq27.gif

42490_2023_74_Article_IEq25.gif

42490_2023_74_Article_IEq24.gif

42490_2023_74_Article_IEq23.gif

Fig. 1

Fig. 8

42490_2023_74_Article_IEq20.gif

42490_2023_74_Article_IEq19.gif

42490_2023_74_Article_IEq18.gif

42490_2023_74_Article_IEq17.gif

42490_2023_74_Article_IEq13.gif

42490_2023_74_Article_IEq12.gif

Fig. 2

Fig. 7

42490_2023_74_Article_IEq8.gif

Fig. 1

Fig. 1

Fig. 6

Fig. 1

Fig. 6

42490_2023_74_Article_IEq3.gif

42490_2023_74_Article_IEq1.gif

Fig. 2

Fig. 3

Fig. 2

Fig. 2

Fig. 6

Fig. 5

Fig. 10

Fig. 5

Fig. 1

Fig. 6

Fig. 2

Fig. 4

Fig. 1

Fig. 1

Fig. 4

Fig. 1

Fig. 3

Fig. 7

Fig. 3

Fig. 3

Fig. 6

Fig. 6

Fig. 2

Fig. 1

Fig. 5

Fig. 2

40517_2023_263_Article_IEq2.gif

Fig. 5

Fig. 1

Fig. 11

Fig. 4

Fig. 1

Fig. 3

Fig. 2

Fig. 1

Fig. 4

Fig. 2

40798_2023_622_Article_IEq21.gif

40798_2023_622_Article_IEq20.gif

40798_2023_622_Article_IEq19.gif

Fig. 6

Fig. 9

Fig. 1

Fig. 5

40798_2023_622_Article_IEq15.gif

40517_2023_263_Article_IEq1.gif

Fig. 10

Fig. 5

Scheme 1

Fig. 3

40798_2023_622_Article_IEq9.gif

Fig. 2

Fig. 4

Fig. 4

12888_2023_4959_Article_IEq1.gif

Fig. 8

Fig. 6

Fig. 4

Fig. 8

Fig. 3

Fig. 11

Fig. 4

Fig. 12

Fig. 1

Fig. 3

Fig. 2

Fig. 11

Fig. 3

Fig. 1

Fig. 1

12938_2023_1137_Article_IEq68.gif

Fig. 2

40517_2023_267_Article_IEq8.gif

Fig. 10

Fig. 1

Fig. 1

Fig. 1

Fig. 7

Fig. 4

Fig. 3

Fig. 7

Fig. 3

Fig. 5

40798_2023_622_Article_IEq7.gif

40798_2023_622_Article_IEq6.gif

40798_2023_622_Article_IEq4.gif

Fig. 5

Fig. 9

41512_2023_153_Article_IEq116.gif

Fig. 2

Fig. 1

Fig. 3

Fig. 3

Fig. 4

Fig. 1

12938_2023_1137_Article_IEq32.gif

40517_2023_267_Article_IEq6.gif

40517_2023_267_Article_IEq5.gif

40517_2023_267_Article_IEq4.gif

40517_2023_267_Article_IEq3.gif

Fig. 2

Fig. 3

Fig. 5

Fig. 8

Fig. 1

Fig. 1

Fig. 7

Fig. 1

Fig. 3

41512_2023_153_Article_IEq102.gif

41512_2023_153_Article_IEq101.gif

Fig. 2

Fig. 1

Fig. 1

Fig. 2

Fig. 4

41512_2023_153_Article_IEq93.gif

Fig. 6

Fig. 5

Fig. 2

Fig. 4

Fig. 6

Fig. 3

41512_2023_153_Article_IEq73.gif

Fig. 1

Fig. 2

Fig. 1

Fig. 4

Fig. 14

Fig. 4

Fig. 2

41512_2023_153_Article_IEq65.gif

Fig. 3

Fig. 3

Fig. 1

13731_2023_311_Article_IEq7.gif

Fig. 6

Fig. 4

Fig. 1

Fig. 5

Fig. 7.

Fig. 1

Fig. 1

13750_2023_309_Article_IEq64.gif

Fig. 2

Fig. 3

Fig. 6

Fig. 1

Fig. 7

Fig. 2

Fig. 4

Fig. 1

13570_2023_282_Article_IEq21.gif

13570_2023_282_Article_IEq13.gif

Fig. 3

13570_2023_282_Article_IEq6.gif

13570_2023_282_Article_IEq3.gif

13570_2023_282_Article_IEq1.gif

Fig. 6

Fig. 2

13690_2023_1151_Article_IEq15.gif

13690_2023_1151_Article_IEq4.gif

Fig. 1

Fig. 1

Fig. 3

Fig. 1

Fig. 1