Title: Multiple genome alignment based on longest path in directed acyclic graphs

Authors: Fangrui Ma, Jitender S. Deogun

Addresses: The Department of Computer Science and Engineering, University of Nebraska-Lincoln, Lincoln, NE 68588, USA. ' The Department of Computer Science and Engineering, University of Nebraska-Lincoln, Lincoln, NE 68588, USA

Abstract: In this paper, we present a simple and efficient algorithm for multiple genome sequence alignment. Sequences of Maximal Unique Matches (MUMs) are first transformed into a multi-bipartite diagram. The diagram is then converted into a Directed Acyclic Graph (DAG). Therefore, finding the alignment is reduced to finding the longest path in the DAG, which is solvable in linear time. The experiments show that the algorithm can correctly find the alignment, and runs faster than MGA and EMAGEN. In addition, our algorithm can handle the alignments with overlapping MUMs and has both weighted and unweighted options. It provides the flexibility for the alignments depending on different needs.

Keywords: biological sequence analysis; genome sequence alignment; longest path algorithm; bioinformatics; DAG; directed acyclic graph; gene sequences.

DOI: 10.1504/IJBRA.2010.036000

International Journal of Bioinformatics Research and Applications, 2010 Vol.6 No.4, pp.366 - 383

Published online: 11 Oct 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article