Title :
A New Approach for Phylogenetic Tree Construction Based on Minimal Absent Words
Author :
Chairungsee, Supaporn
Author_Institution :
Dept. of Inf. Technol., Walailak Univ., Nakhonsithammarat, Thailand
Abstract :
An absent word (or a forbidden word) is a word that does not appear in a given sequence. It is a minimal absent word if all its proper factors occur in the given sequence. In this paper, we propose a linear-time algorithm to compute the minimal absent words for DNA sequence using a suffix automaton. This method outputs the whole set of minimal absent words. We apply a Neighbor-Joining method to construct phylogenetic tree based on the minimal absent words.
Keywords :
automata theory; bioinformatics; pattern clustering; trees (mathematics); DNA sequence; hierarchical clustering; linear-time algorithm; minimal absent word; neighbor-joining method; phylogenetic tree construction; suffix automaton; Automata; Bioinformatics; Bovine; Genomics; Mice; Phylogeny; Rabbits; forbidden words; minimal absent words; phylogenetic tree construction; suffix automaton;
Conference_Titel :
Database and Expert Systems Applications (DEXA), 2014 25th International Workshop on
Conference_Location :
Munich
Print_ISBN :
978-1-4799-5721-7
DOI :
10.1109/DEXA.2014.21
