Bioinformatics algorithm based on a parallel implementation of a machine learning approach using transducers | JoVE Visualize

Area of Science:

Bioinformatics
Computational Biology
Machine Learning

Background:

Finite-state transducers (FSTs) are crucial for bioinformatics, used in sequence alignment and developing computational biology kernels.
Machine learning algorithms for conditional FSTs are vital for DNA sequence analysis but computationally intensive due to large datasets.
Existing transducer learning algorithms rely on costly probability computations like pair-database creation, normalization, and Expectation-Maximization (EM).

Purpose of the Study:

To develop and evaluate a parallel implementation of an algorithm for learning conditional transducers.
To optimize computational efficiency for bioinformatics applications, including sequence alignment and phylogenetic tree construction.
To assess the scalability and performance of the parallel algorithm on a high-performance computing cluster.

Main Methods:

A parallel algorithm was implemented for learning conditional transducers, incorporating techniques like Maximum-Likelihood normalization and EM parameter optimization.
The algorithm was tested on bioinformatics applications, including sequence alignment and genome evolution studies.
Performance was evaluated on the Westgrid Breeze cluster, comparing parallel and sequential execution times, scalability with data size, precision, and thread count.

Main Results:

The parallel algorithm demonstrated significant scalability, with execution times decreasing as data size increased.
Using the parallel algorithm resulted in shorter execution times when the precision parameter was adjusted.
Speedup increased with more threads, showing convergence beyond 16 threads for the parallel execution.

Conclusions:

The developed parallel algorithm offers a scalable and efficient solution for learning conditional transducers in bioinformatics.
The parallel implementation significantly reduces computational costs associated with large-scale bioinformatics data analysis.
This approach facilitates advanced genome evolution studies and other complex biological sequence analyses.