Multiple genome alignment based on longest path in directed acyclic graphs

Authors: Ma, Fangrui¹; Deogun, Jitender S.²

Source: International Journal of Bioinformatics Research and Applications, Volume 6, Number 4, 11 October 2010 , pp. 366-383(18)

Publisher: Inderscience Publishers

Buy & download fulltext article:

Price: $44.11 plus tax (Refund Policy)

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: HEALTHCARE AND BIOSCIENCES; Biosciences and Bioinformatics; COMPUTING AND MATHEMATICS; Computing Science, Applications and Software; HEALTHCARE AND BIOSCIENCES; Healthcare and Medical Engineering

Document Type: Research article

DOI: http://dx.doi.org/10.1504/IJBRA.2010.036000

Affiliations: 1: The Department of Computer Science and Engineering, University of Nebraska-Lincoln, Lincoln, NE 68588, USA. 2: The Department of Computer Science and Engineering, University of Nebraska-Lincoln, Lincoln, NE 68588, USA

Publication date: 2010-10-11

More about this publication?

The International Journal of Bioinformatics Research and Applications addresses the most innovative developments, research issues and solutions in bioinformatics and computational biology and their applications.
Information for Authors
Submit a Paper
Subscribe to this Title
Terms & Conditions
Newsletter
Blog
ingentaconnect is not responsible for the content or availability of external websites