ALFRED-G

BACKGROUND: Alignment-free sequence comparison approaches have been garnering
increasing interest in various data- and compute-intensive applications such as
phylogenetic inference for large-scale sequences. While k-mer based methods are
predominantly used in real applications, the average common substring (ACS)
approach is emerging as one of the prominent alignment-free approaches. This ACS
approach has been further generalized by some recent work, either greedily or
exactly, by allowing a bounded number of mismatches in the common substrings.
RESULTS: We present ALFRED-G, a greedy alignment-free distance estimator for
phylogenetic tree reconstruction based on the concept of the generalized ACS
approach. In this algorithm, we have investigated a new heuristic to efficiently
compute the lengths of common strings with mismatches allowed, and have further
applied this heuristic to phylogeny reconstruction. Performance evaluation using
real sequence datasets shows that our heuristic is able to reconstruct
comparable, or even more accurate, phylogenetic tree topologies than the kmacs
heuristic algorithm at highly competitive speed. CONCLUSIONS: ALFRED-G is an
alignment-free heuristic for evolutionary distance estimation between two
biological sequences. This algorithm is implemented in C++ and has been
incorporated into our open-source ALFRED software package (
http://alurulab.cc.gatech.edu/phylo ).

A greedy alignment-free distance estimator for phylogenetic inference.

ALFRED-G is a bioinformatics software tool to estimate evolutionary distances between two sequences. The ALFRED-G algorithm uses a greedy alignment-free method.

ALFRED-G

Topic

Detail

Publications

Download and documentation