The solution space of genome sequence alignment and LIS graph decomposition

Fangrui Ma, Jitender S. Deogun

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we present an algorithm to discover the optimal solution space of genome sequence alignment. The solution space is an LIS (longest increasing subsequence) graph, which can be constructed in O(n2) time, where n is the number of MUMs in given genome sequences. The LIS graph has many unique properties that lead to the development of efficient decomposition algorithms. With the availability of the solution space, users can examine all possible solutions and pick the one that best meet their needs. We provide the decomposition tree traversal algorithm, which outputs the solution in an elegant and compact clustered form. Moreover, the solution space can also be used to study the homology of genome sequences.

Original languageEnglish (US)
Title of host publication2010 ACM International Conference on Bioinformatics and Computational Biology, ACM-BCB 2010
Pages302-311
Number of pages10
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 ACM International Conference on Bioinformatics and Computational Biology, ACM-BCB 2010 - Niagara Falls, NY, United States
Duration: Aug 2 2010Aug 4 2010

Publication series

Name2010 ACM International Conference on Bioinformatics and Computational Biology, ACM-BCB 2010

Conference

Conference2010 ACM International Conference on Bioinformatics and Computational Biology, ACM-BCB 2010
Country/TerritoryUnited States
CityNiagara Falls, NY
Period8/2/108/4/10

Keywords

  • Genome alignment
  • Graph decomposition
  • Longest increasing subsequence
  • Multiple alignment

ASJC Scopus subject areas

  • Biomedical Engineering
  • Health Information Management

Fingerprint

Dive into the research topics of 'The solution space of genome sequence alignment and LIS graph decomposition'. Together they form a unique fingerprint.

Cite this