@proceedings {38343,
	title = {Inexact Local Alignment Search over Suffix Arrays},
	year = {2009},
	month = {2009},
	publisher = {IEEE},
	type = {10.1109/BIBM.2009.25},
	abstract = {We describe an algorithm for finding approximate seeds for DNA homology searches. In contrast to previous algorithms that use exact or spaced seeds, our approximate seeds may contain insertions and deletions. We present a generalized heuristic for finding such seeds efficiently and prove that the heuristic does not affect sensitivity. We show how to adapt this algorithm to work over the memory efficient suffix array with provably minimal overhead in running time. We demonstrate the effectiveness of our algorithm on two tasks: whole genome alignment of bacteria and alignment of the DNA sequences of 177 genes that are orthologous in human and mouse. We show our algorithm achieves better sensitivity and uses less memory than other commonly used local alignment tools.},
	keywords = {bacteria, Bioinformatics, biology computing, Computational Biology, Costs, DNA, DNA homology searches, DNA sequences, Educational institutions, generalized heuristic, genes, Genetics, genome alignment, Genomics, human, inexact local alignment search, inexact seeds, local alignment, local alignment tools, memory efficient suffix array, microorganisms, molecular biophysics, mouse, Organisms, Sensitivity and Specificity, sequences, suffix array, USA Councils},
	isbn = {978-0-7695-3885-3},
	author = {Ghodsi, M. and M. Pop}
}
@proceedings {38218,
	title = {Dynamic querying for pattern identification in microarray and genomic data},
	volume = {3},
	year = {2003},
	month = {2003},
	publisher = {IEEE},
	type = {10.1109/ICME.2003.1221346},
	abstract = {Data sets involving linear ordered sequences are a recurring theme in bioinformatics. Dynamic query tools that support exploration of these data sets can be useful for identifying patterns of interest. This paper describes the use of one such tool - timesearcher - to interactively explore linear sequence data sets taken from two bioinformatics problems. Microarray time course data sets involve expression levels for large numbers of genes over multiple time points. Timesearcher can be used to interactively search these data sets for genes with expression profiles of interest. The occurrence frequencies of short sequences of DNA in aligned exons can be used to identify sequences that play a role in the pre-mRNA splicing. Timesearcher can be used to search these data sets for candidate splicing signals.},
	keywords = {Bioinformatics, data sets, Displays, dynamic querying, expression profiles, Frequency, Gene expression, genes, Genetics, genomic data, Genomics, linear ordered sequences, macromolecules, medical signal processing, Mice, Microarray, pattern identification, pattern recognition, premRNA splicing, Query processing, sequences, Signal processing, splicing, TimeSearcher},
	isbn = {0-7803-7965-9},
	author = {Hochheiser, H. and Baehrecke, E. H. and Stephen M. Mount and Shneiderman, Ben}
}
@proceedings {38502,
	title = {A SIMD solution to the sequence comparison problem on the MGAP},
	year = {1994},
	month = {1994},
	publisher = {IEEE},
	type = {10.1109/ASAP.1994.331791},
	abstract = {Molecular biologists frequently compare an unknown biosequence with a set of other known biosequences to find the sequence which is maximally similar, with the hope that what is true of one sequence, either physically or functionally, could be true of its analogue. Even though efficient dynamic programming algorithms exist for the problem, when the size of the database is large, the time required is quite long, even for moderate length sequences. In this paper, we present an efficient pipelined SIMD solution to the sequence alignment problem on the Micro-Grain Array Processor (MGAP), a fine-grained massively parallel array of processors with nearest-neighbor connections. The algorithm compares K sequences of length O(M) with the actual sequence of length N, in O(M+N+K) time with O(MN) processors, which is AT-optimal. The implementation on the MGAP computes at the rate of about 0.1 million comparisons per second for sequences of length 128},
	keywords = {AT-optimal algorithm, Biological information theory, biology computing, biosequence comparison problem, computational complexity, Computer science, Costs, database size, Databases, DNA computing, dynamic programming, dynamic programming algorithms, fine-grained massively parallel processor array, Genetics, Heuristic algorithms, maximally similar sequence, MGAP parallel computer, Micro-Grain Array Processor, Military computing, molecular biology, molecular biophysics, Nearest neighbor searches, nearest-neighbor connections, Parallel algorithms, pipeline processing, pipelined SIMD solution, sequence alignment problem, sequences},
	isbn = {0-8186-6517-3},
	author = {Borah, M. and Bajwa, R. S. and Sridhar Hannenhalli and Irwin, M. J.}
}
