Multiple genome alignment based on longest path in Directed Acyclic Graphs

Fangrui Ma, Jitender S. Deogun

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)366-383
Number of pages18
JournalInternational Journal of Bioinformatics Research and Applications
Volume6
Issue number4
DOIs
StatePublished - Oct 2010

Keywords

  • Bioinformatics
  • Biological sequence analysis
  • DAG
  • Directed Acyclic Graph
  • Genome sequence alignment
  • Longest path algorithm

ASJC Scopus subject areas

  • Biomedical Engineering
  • Health Informatics
  • Clinical Biochemistry
  • Health Information Management

Fingerprint Dive into the research topics of 'Multiple genome alignment based on longest path in Directed Acyclic Graphs'. Together they form a unique fingerprint.

Cite this