FAME: fast and memory efficient multiple sequences alignment tool through compatible chain of roots

Genetic surveillance reveals low but sustained malaria transmission with clonal replacement in Sao Tome and Principe

BACKGROUND

Despite efforts to eliminate malaria in Sao Tome and Principe (STP), cases have recently increased. Understanding residual transmission structure is crucial for developing effective elimination strategies.

METHODS

This study collected surveillance data and generated amplicon sequencing data from 980 samples between 2010 and 2016 to examine the genetic structure of the parasite population.

RESULTS

Here we show that the mean multiplicity of infection (MOI) is 1.3, with 11% polyclonal infections, indicating low transmission intensity. Temporal trends of these genetic metrics do not align with incidence rates, suggesting that changes in genetic metrics may not straightforwardly reflect changes in transmission intensity, particularly in low transmission settings where genetic drift and importation have a substantial impact. While 88% of samples are genetically linked, continuous turnover in genetic clusters and changes in drug-resistance haplotypes are observed. Principal component analysis reveals some STP samples are genetically similar to those from Central and West Africa, indicating possible importation.

CONCLUSIONS

These findings highlight the need to prioritize several interventions, such as targeted interventions against transmission hotspots, reactive case detection, and strategies to reduce the introduction of new parasites into this island nation as it approaches elimination. This study also serves as a case study for implementing genetic surveillance in a low transmission setting.

Genetic surveillance reveals low, sustained malaria transmission with clonal replacement in Sao Tome and Principe

Despite efforts to eliminate malaria in Sao Tome and Principe (STP), cases have recently increased. Understanding residual transmission structure is crucial for developing effective elimination strategies. This study collected surveillance data and generated amplicon sequencing data from 980 samples between 2010 and 2016 to examine the genetic structure of the parasite population. The mean multiplicity of infection (MOI) was 1.3, with 11% polyclonal infections, indicating low transmission intensity. Temporal trends of these genetic metrics did not align with incidence rates, suggesting that changes in genetic metrics may not straightforwardly reflect changes in transmission intensity, particularly in low transmission settings where genetic drift and importation have a substantial impact. While 88% of samples were genetically linked, continuous turnover in genetic clusters and changes in drug-resistance haplotypes were observed. Principal component analysis revealed some STP samples were genetically similar to those from Central and West Africa, indicating possible importation. These findings highlight the need to prioritize several interventions such as targeted interventions against transmission hotspots, reactive case detection, and strategies to reduce the introduction of new parasites into this island nation as it approaches elimination. This study also serves as a case study for implementing genetic surveillance in a low transmission setting.

FMAlign2: a novel fast multiple nucleotide sequence alignment method for ultralong datasets

MOTIVATION

In bioinformatics, multiple sequence alignment (MSA) is a crucial task. However, conventional methods often struggle with aligning ultralong sequences. To address this issue, researchers have designed MSA methods rooted in a vertical division strategy, which segments sequence data for parallel alignment. A prime example of this approach is FMAlign, which utilizes the FM-index to extract common seeds and segment the sequences accordingly.

RESULTS

FMAlign2 leverages the suffix array to identify maximal exact matches, redefining the approach of FMAlign from searching for global chains to partial chains. By using a vertical division strategy, large-scale problem is deconstructed into manageable tasks, enabling parallel execution of subMSA. Furthermore, sequence-profile alignment and refinement are incorporated to concatenate subsets, yielding the final result seamlessly. Compared to FMAlign, FMAlign2 markedly augments the segmentation of sequences and significantly reduces the time while maintaining accuracy, especially on ultralong datasets. Importantly, FMAlign2 enhances existing MSA methods by conferring the capability to handle sequences reaching billions in length within an acceptable time frame.

AVAILABILITY AND IMPLEMENTATION

Source code and datasets are available at https://github.com/malabz/FMAlign2 and https://zenodo.org/records/10435770.

Creating and Using Minimizer Sketches in Computational Genomics

Processing large data sets has become an essential part of computational genomics. Greatly increased availability of sequence data from multiple sources has fueled breakthroughs in genomics and related fields but has led to computational challenges processing large sequencing experiments. The minimizer sketch is a popular method for sequence sketching that underlies core steps in computational genomics such as read mapping, sequence assembling, k-mer counting, and more. In most applications, minimizer sketches are constructed using one of few classical approaches. More recently, efforts have been put into building minimizer sketches with desirable properties compared with the classical constructions. In this survey, we review the history of the minimizer sketch, the theories developed around the concept, and the plethora of applications taking advantage of such sketches. We aim to provide the readers a comprehensive picture of the research landscape involving minimizer sketches, in anticipation of better fusion of theory and application in the future.

WMSA: a novel method for multiple sequence alignment of DNA sequences

MOTIVATION

Multiple sequence alignment (MSA) is a fundamental problem in bioinformatics. The quality of alignment will affect downstream analysis. MAFFT has adopted the Fast Fourier Transform method for searching the homologous segments and using them as anchors to divide the sequences, then making alignment only on segments, which can save time and memory without overly reducing the sequence alignment quality. MAFFT becomes slow when the dataset is large.

RESULTS

We made a software, WMSA, which uses the divide-and-conquer method to split the sequences into clusters, aligns those clusters into profiles with the center star strategy and then makes a progressive profile-profile alignment. The alignment is conducted by the compiled algorithms of MAFFT, K-Band with multithread parallelism. Our method can balance time, space and quality and performs better than MAFFT in test experiments on highly conserved datasets.

AVAILABILITY AND IMPLEMENTATION

Source code is freely available at https://github.com/malabz/WMSA/, which is implemented in C/C++ and supported on Linux, and datasets are available at https://github.com/malabz/WMSA-dataset.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Developments in Algorithms for Sequence Alignment: A Review

The continuous development of sequencing technologies has enabled researchers to obtain large amounts of biological sequence data, and this has resulted in increasing demands for software that can perform sequence alignment fast and accurately. A number of algorithms and tools for sequence alignment have been designed to meet the various needs of biologists. Here, the ideas that prevail in the research of sequence alignment and some quality estimation methods for multiple sequence alignment tools are summarized.

A survey on the algorithm and development of multiple sequence alignment

Multiple sequence alignment (MSA) is an essential cornerstone in bioinformatics, which can reveal the potential information in biological sequences, such as function, evolution and structure. MSA is widely used in many bioinformatics scenarios, such as phylogenetic analysis, protein analysis and genomic analysis. However, MSA faces new challenges with the gradual increase in sequence scale and the increasing demand for alignment accuracy. Therefore, developing an efficient and accurate strategy for MSA has become one of the research hotspots in bioinformatics. In this work, we mainly summarize the algorithms for MSA and its applications in bioinformatics. To provide a structured and clear perspective, we systematically introduce MSA's knowledge, including background, database, metric and benchmark. Besides, we list the most common applications of MSA in the field of bioinformatics, including database searching, phylogenetic analysis, genomic analysis, metagenomic analysis and protein analysis. Furthermore, we categorize and analyze classical and state-of-the-art algorithms, divided into progressive alignment, iterative algorithm, heuristics, machine learning and divide-and-conquer. Moreover, we also discuss the challenges and opportunities of MSA in bioinformatics. Our work provides a comprehensive survey of MSA applications and their relevant algorithms. It could bring valuable insights for researchers to contribute their knowledge to MSA and relevant studies.

A novel fast multiple nucleotide sequence alignment method based on FM-index

Multiple sequence alignment (MSA) is fundamental to many biological applications. But most classical MSA algorithms are difficult to handle large-scale multiple sequences, especially long sequences. Therefore, some recent aligners adopt an efficient divide-and-conquer strategy to divide long sequences into several short sub-sequences. Selecting the common segments (i.e. anchors) for division of sequences is very critical as it directly affects the accuracy and time cost. So, we proposed a novel algorithm, FMAlign, to improve the performance of multiple nucleotide sequence alignment. We use FM-index to extract long common segments at a low cost rather than using a space-consuming hash table. Moreover, after finding the longer optimal common segments, the sequences are divided by the longer common segments. FMAlign has been tested on virus and bacteria genome and human mitochondrial genome datasets, and compared with existing MSA methods such as MAFFT, HAlign and FAME. The experiments show that our method outperforms the existing methods in terms of running time, and has a high accuracy on long sequence sets. All the results demonstrate that our method is applicable to the large-scale nucleotide sequences in terms of sequence length and sequence number. The source code and related data are accessible in https://github.com/iliuh/FMAlign.