@inproceedings{20542216bb01450fbd78cf3da8bb6676,
title = "The solution space of genome sequence alignment and LIS graph decomposition",
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.",
keywords = "Genome alignment, Graph decomposition, Longest increasing subsequence, Multiple alignment",
author = "Fangrui Ma and Deogun, {Jitender S.}",
year = "2010",
doi = "10.1145/1854776.1854818",
language = "English (US)",
isbn = "9781450304382",
series = "2010 ACM International Conference on Bioinformatics and Computational Biology, ACM-BCB 2010",
pages = "302--311",
booktitle = "2010 ACM International Conference on Bioinformatics and Computational Biology, ACM-BCB 2010",
note = "2010 ACM International Conference on Bioinformatics and Computational Biology, ACM-BCB 2010 ; Conference date: 02-08-2010 Through 04-08-2010",
}