Biology subjects

Pardi, F.

Publications and source records attributed to Pardi, F..

5 recordsLinked to original sources

bioRxiv2024

Algorithms to reconstruct past indels: the deletion-only parsimony problem

Ancestral sequence reconstruction is an important task in bioinformatics, with applications ranging from protein engineering to the study of genome evolution. When sequences can only undergo substitutions, optimal reconstructions can be efficiently computed using well-known algorithms. However, accounting for indels in ancestral reconstructions is much harder. First, for biologically-relevant problem formulations, no polynomial-time exact algorithms are available. Second, multiple reconstructions are often equally parsimonious or likely, making it crucial to correctly display uncertainty in the results. Here, we consider a parsimony approach where any indel event has the same cost, irrespective of its size or the branch where it occurs. We thoroughly examine the case where only deletions are allowed, while addressing the aforementioned limitations. First, we describe an exact algorithm to obtain all the optimal solutions. The algorithm runs in polynomial time if only one solution is sought. Second, we show that all possible optimal reconstructions for a fixed node can be represented using a graph computable in polynomial time. While previous studies have proposed graph-based representations of ancestral reconstructions, this result is the first to offer a solid mathematical justification for this approach. Finally we discuss the relevance of the deletion-only case for the general case. Author summaryAn exciting frontier in evolutionary biology is the ability to reconstruct DNA or protein sequences from species that lived in the distant past. By analyzing sequences from present-day species, we aim to infer the sequences of their common ancestors --a process known as ancestral sequence reconstruction. This task has far-reaching applications, such as resurrecting ancient proteins and studying the biology of extinct organisms. However, a significant challenge remains: the lack of well-established methods for inferring past deletions and insertions ---mutations that remove or add segments of genetic code. In this paper, we present algorithms that lay the groundwork for addressing this gap. We show that finding the reconstructions involving only deletion events, while minimizing their number, can be done efficiently. Additionally, we show that all optimal solutions can be represented using specialized graphs. While previous studies have proposed graph-based representations of ancestral reconstructions, we are the first to provide a rigorous mathematical foundation for the use of these graphs.

bioinformatics↗

bioRxiv2020

Phylogenetic Novelty Scores: a New Approach for Weighting Genetic Sequences

BackgroundMany important applications in bioinformatics, including sequence alignment and protein family profiling, employ sequence weighting schemes to mitigate the effects of non-independence of homologous sequences and under- or over-representation of certain taxa in a dataset. These schemes aim to assign high weights to sequences that are novel compared to the others in the same dataset, and low weights to sequences that are over-represented. ResultsWe formalise this principle by rigorously defining the evolutionary novelty of a sequence within an alignment. This results in new sequence weights that we call phylogenetic novelty scores. These scores have various desirable properties, and we showcase their use by considering, as an example application, the inference of character frequencies at an alignment column -- important, for example, in protein family profiling. We give computationally efficient algorithms for calculating our scores and, using simulations, show that they improve the accuracy of character frequency estimation compared to existing sequence weighting schemes. ConclusionsOur phylogenetic novelty scores can be useful when an evolutionarily meaningful system for adjusting for uneven taxon sampling is desired. They have numerous possible applications, including estimation of evolutionary conservation scores and sequence logos, identification of targets in conservation biology, and improving and measuring sequence alignment accuracy.

bioinformatics↗

bioRxiv2020

On the inference of complex phylogenetic networks by Markov Chain Monte-Carlo

For various species, high quality sequences and complete genomes are nowadays available for many individuals. This makes data analysis challenging, as methods need not only to be accurate, but also time efficient given the tremendous amount of data to process. In this article, we introduce an efficient method to infer the evolutionary history of individuals under the multispecies coalescent model in networks (MSNC). Phylogenetic networks are an extension of phylogenetic trees that can contain reticulate nodes, which allow to model complex biological events such as horizontal gene transfer, hybridization, introgression and recombination. We present a novel way to compute the likelihood of biallelic markers sampled along genomes whose evolution involved such events. This likelihood computation is at the heart of a Bayesian network inference method called SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW, as it extends the SO_SCPLOWNAPPC_SCPLOW method [1] inferring evolutionary trees under the multispecies coalescent model, to networks. SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW is available as a package of the well-known beast 2 software. Recently, the MCMCBiMarkers method [2] also extended SO_SCPLOWNAPPC_SCPLOW to networks. Both methods take biallelic markers as input, rely on the same model of evolution and sample networks in a Bayesian framework, though using different methods for computing priors. However, SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW relies on algorithms that are exponentially more time-efficient on non-trivial networks. Using extensive simulations, we compare performances of SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW and MCMCBiMarkers. We show that both methods enjoy similar abilities to recover simple networks, but SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW is more accurate than MCMCBiMarkers on more complex network scenarios. Also, on complex networks, SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW is found to be extremely faster than MCMCBiMarkers in terms of time required for the likelihood computation. We finally illustrate SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW performances on a rice data set. SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW infers a scenario that is compatible with simpler schemes proposed so far and provides additional understanding of rice evolution. Author summaryNowadays, to make the best use of the vast amount of genomic data at our disposal, there is a real need for methods able to model complex biological mechanisms such as hybridization and introgression. Understanding such mechanisms can help geneticists to elaborate strategies in crop improvement that may help reducing poverty and dealing with climate change. However, reconstructing such evolution scenarios is challenging. Indeed, the inference of phylogenetic networks, which explicitly model reticulation events such as hybridization and introgression, requires high computational resources. Then, on large data sets, biologists generally deduce reticulation events indirectly using species tree inference tools. In this context, we present a new Bayesian method, called SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW, dedicated to phylogenetic network inference. Our method is competitive in terms of execution speed with respect to its competitors. This speed gain enables us to consider more complex evolution scenarios during Bayesian analyses. When applied to rice genomic data, SO_SCPLOWNAPPC_SCPLOWNO_SCPLOWETC_SCPLOW suggested a new evolution scenario, compatible with the existing ones: it posits cAus as the result of an early combination between the Indica and Japonica lineages, followed by a later combination between the cAus and Japonica lineages to derive cBasmati. This accounts for the well-documented wide hybrid compatibility of cAus.

evolutionary biology↗

bioRxiv2020

Rapid screening and detection of inter-type viral recombinants using phylo-k-mers

MotivationNovel recombinant viruses may have important medical and evolutionary significance, as they sometimes display new traits not present in the parental strains. This is particularly concerning when the new viruses combine fragments coming from phylogenetically-distinct viral types. Here, we consider the task of screening large collections of sequences for such novel recombinants. A number of methods already exist for this task. However, these methods rely on complex models and heavy computations that are not always practical for a quick scan of a large number of sequences. ResultsWe have developed SHERPAS, a new program to detect novel recombinants and provide a first estimate of their parental composition. Our approach is based on the precomputation of a large database of "phylogenetically-informed k-mers", an idea recently introduced in the context of phylogenetic placement in metagenomics. Our experiments show that SHERPAS is hundreds to thousands of times faster than existing software, and enables the analysis of thousands of whole genomes, or long sequencing reads, within minutes or seconds, and with limited loss of accuracy. Availability and ImplementationThe source code is freely available for download at https://github.com/phylo42/sherpas Contactpardi@lirmm.fr, gllm.scholz@gmail.com Supplementary informationSupplementary Materials are available online.

bioinformatics↗

bioRxiv2018

Rapid alignment-free phylogenetic identification of metagenomic sequences

MotivationTaxonomic classification is at the core of environmental DNA analysis. When a phylogenetic tree can be built as a prior hypothesis to such classification, phylogenetic placement (PP) provides the most informative type of classification because each query sequence is assigned to its putative origin in the tree. This is useful whenever precision is sought (e.g. in diagnostics). However,likelihood-based PP algorithms struggle to scale with the ever-increasing throughput of DNA sequencing.\n\nResultsWe have developed RAPPAS (Rapid Alignment-free Phylogenetic Placement via Ancestral Sequences) which uses an alignment-free approach, removing the hurdle of query sequence alignment as a preliminary step to PP. Our approach relies on the precomputation of a database of k-mers that may be present with non-negligible probability in relatives of the reference sequences. The placement is performed by inspecting the stored phylogenetic origins of the k-mers in the query, and their probabilities. The database can be reused for the analysis of several different metagenomes. Experiments show that the first implementation of RAPPAS is already faster than competing likelihood-based PP algorithms, while keeping similar accuracy for short reads. RAPPAS scales PP for the era of routine metagenomic diagnostics.\n\nAvailabilityProgram and sources freely available for download at gite.lirmm.fr/linard/RAPPAS.\n\nContactbenjamin.linard@lirmm.fr

bioinformatics↗