@conference {16278,
	title = {MetaPhyler: Taxonomic profiling for metagenomic sequences},
	booktitle = {2010 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)},
	year = {2010},
	month = {2010/12/18/21},
	pages = {95 - 100},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {A major goal of metagenomics is to characterize the microbial diversity of an environment. The most popular approach relies on 16S rRNA sequencing, however this approach can generate biased estimates due to differences in the copy number of the 16S rRNA gene between even closely related organisms, and due to PCR artifacts. The taxonomic composition can also be determined from whole-metagenome sequencing data by matching individual sequences against a database of reference genes. One major limitation of prior methods used for this purpose is the use of a universal classification threshold for all genes at all taxonomic levels. We propose that better classification results can be obtained by tuning the taxonomic classifier to each matching length, reference gene, and taxonomic level. We present a novel taxonomic profiler MetaPhyler, which uses marker genes as a taxonomic reference. Results on simulated datasets demonstrate that MetaPhyler outperforms other tools commonly used in this context (CARMA, Megan and PhymmBL). We also present interesting results obtained by applying MetaPhyler to a real metagenomic dataset.},
	keywords = {Bioinformatics, CARMA comparison, Databases, Genomics, Linear regression, marker genes, matching length, Megan comparison, metagenomic sequences, metagenomics, MetaPhyler, microbial diversity, microorganisms, molecular biophysics, molecular configurations, Pattern classification, pattern matching, phylogenetic classification, Phylogeny, PhymmBL comparison, reference gene database, Sensitivity, sequence matching, taxonomic classifier, taxonomic level, taxonomic profiling, whole metagenome sequencing data},
	isbn = {978-1-4244-8306-8},
	doi = {10.1109/BIBM.2010.5706544},
	author = {Liu,Bo and Gibbons,T. and Ghodsi,M. and Pop, Mihai}
}
@conference {16275,
	title = {Inexact Local Alignment Search over Suffix Arrays},
	booktitle = {IEEE International Conference on Bioinformatics and Biomedicine, 2009. BIBM {\textquoteright}09},
	year = {2009},
	month = {2009/11/01/4},
	pages = {83 - 87},
	publisher = {IEEE},
	organization = {IEEE},
	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},
	doi = {10.1109/BIBM.2009.25},
	author = {Ghodsi,M. and Pop, Mihai}
}
@conference {16466,
	title = {Optimized seamless integration of biomolecular data},
	booktitle = {Proceedings of the IEEE 2nd International Symposium on Bioinformatics and Bioengineering Conference, 2001},
	year = {2001},
	month = {2001/11/04/6},
	pages = {23 - 32},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Today, scientific data is inevitably digitized, stored in a variety of heterogeneous formats, and is accessible over the Internet. Scientists need to access an integrated view of multiple remote or local heterogeneous data sources. They then integrate the results of complex queries and apply further analysis and visualization to support the task of scientific discovery. Building a digital library for scientific discovery requires accessing and manipulating data extracted from flat files or databases, documents retrieved from the Web, as well as data that is locally materialized in warehouses or is generated by software. We consider several tasks to provide optimized and seamless integration of biomolecular data. Challenges to be addressed include capturing and representing source capabilities; developing a methodology to acquire and represent metadata about source contents and access costs; and decision support to select sources and capabilities using cost based and semantic knowledge, and generating low cost query evaluation plans},
	keywords = {analysis, Bioinformatics, biology computing, cost based knowledge, Costs, Data analysis, data mining, data visualisation, Data visualization, Data warehouses, decision support, digital library, Educational institutions, information resources, Internet, low cost query evaluation plans, Mediation, meta data, metadata, molecular biophysics, multiple local heterogeneous data sources, multiple remote heterogeneous data sources, optimized seamless biomolecular data integration, scientific discovery, scientific information systems, semantic knowledge, software libraries, visual databases, Visualization},
	isbn = {0-7695-1423-5},
	doi = {10.1109/BIBE.2001.974408},
	author = {Eckman,B. A and Lacroix,Z. and Raschid, Louiqa}
}
@conference {14621,
	title = {Hardness of flip-cut problems from optical mapping [DNA molecules application]},
	booktitle = {Compression and Complexity of Sequences 1997. Proceedings},
	year = {1997},
	month = {1997/06/11/13},
	pages = {275 - 284},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Optical mapping is a new technology for constructing restriction maps. Associated computational problems include aligning multiple partial restriction maps into a single {\textquotedblleft}consensus{\textquotedblright} restriction map, and determining the correct orientation of each molecule, which was formalized as the exclusive binary flip cut (EBFC) problem by Muthukrishnan and Parida (see Proc. of the First ACM Conference on Computational Molecular Biology (RECOMB), Santa Fe, p.209-19, 1997). Here, the authors prove that the EBFC problem, as well as a number of its variants, are NP-complete. They also identify another problem formalized as binary shift cut (BSC) problem motivated by the fact that there might be missing fragments at the beginnings and/or the ends of the molecules, and prove it to be NP-complete. Therefore, they do not have efficient, that is, polynomial time solutions unless P=NP},
	keywords = {binary shift cut, Biochemistry, Bioinformatics, biological techniques, Biology, biomedical optical imaging, combinatorial mathematics, combinatorial problem, computational complexity, computational problems, DNA, DNA molecule, exclusive binary flip cut, flip-cut problem hardness, Genetic engineering, Genomics, MATHEMATICS, molecular biology, molecular biophysics, molecule orientation, multiple partial restriction maps, NP-complete problem, optical mapping, polynomial time solutions, Polynomials, sequences},
	isbn = {0-8186-8132-2},
	doi = {10.1109/SEQUEN.1997.666922},
	author = {Dancik,V. and Hannenhalli, Sridhar and Muthukrishnan,S.}
}
@conference {14579,
	title = {A SIMD solution to the sequence comparison problem on the MGAP},
	booktitle = {International Conference on Application Specific Array Processors, 1994. Proceedings},
	year = {1994},
	month = {1994/08/22/24},
	pages = {336 - 345},
	publisher = {IEEE},
	organization = {IEEE},
	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},
	doi = {10.1109/ASAP.1994.331791},
	author = {Borah,M. and Bajwa,R. S and Hannenhalli, Sridhar and Irwin,M. J}
}
