@article {38290,
	title = {Genome assortment, not serogroup, defines Vibrio cholerae pandemic strains},
	journal = {NatureNature},
	year = {2009},
	abstract = {Vibrio cholerae, the causative agent of cholera, is a bacterium autochthonous to the aquatic environment, and a serious public health threat. V. cholerae serogroup O1 is responsible for the previous two cholera pandemics, in which classical and El Tor biotypes were dominant in the 6th and the current 7th pandemics, respectively. Cholera researchers continually face newly emerging and re-emerging pathogenic clones carrying combinations of new serogroups as well as of phenotypic and genotypic properties. These genotype and phenotype changes have hampered control of the disease. Here we compare the complete genome sequences of 23 strains of V. cholerae isolated from a variety of sources and geographical locations over the past 98 years in an effort to elucidate the evolutionary mechanisms governing genetic diversity and genesis of new pathogenic clones. The genome-based phylogeny revealed 12 distinct V. cholerae phyletic lineages, of which one, designated the V. cholerae core genome (CG), comprises both O1 classical and EI Tor biotypes. All 7th pandemic clones share nearly identical gene content, i.e., the same genome backbone. The transition from 6th to 7th pandemic strains is defined here as a {\textquoteright}shift{\textquoteright} between pathogenic clones belonging to the same O1 serogroup, but from significantly different phyletic lineages within the CG clade. In contrast, transition among clones during the present 7th pandemic period can be characterized as a {\textquoteright}drift{\textquoteright} between clones, differentiated mainly by varying composition of laterally transferred genomic islands, resulting in emergence of variants, exemplified by V.cholerae serogroup O139 and V.cholerae O1 El Tor hybrid clones that produce cholera toxin of classical biotype. Based on the comprehensive comparative genomics presented in this study it is concluded that V. cholerae undergoes extensive genetic recombination via lateral gene transfer, and, therefore, genome assortment, not serogroup, should be used to define pathogenic V. cholerae clones.},
	keywords = {59, CHOLERA, genes, Genetics, GENOTYPE, ISLANDS, ORIGIN, PHENOTYPE, PUBLIC HEALTH, recombination, STRAINS, Toxins},
	author = {Brettin, Thomas S. and Bruce, David C. and Challacombe, Jean F. and Detter, John C. and Han, Cliff S. and Munik, A. C. and Chertkov, Olga and Meincke, Linda and Saunders, Elizabeth and Choi, Seon Y. and Haley, Bradd J. and Taviani, Elisa and Jeon, Yoon-Seong and Kim, Dong Wook and Lee, Jae-Hak and Walters, Ronald A. and Hug, Anwar and Rita R. Colwell}
}
@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}
}
@article {38379,
	title = {Microbial oceanography in a sea of opportunity},
	journal = {NatureNature},
	volume = {459},
	year = {2009},
	type = {10.1038/nature08056},
	abstract = {Plankton use solar energy to drive the nutrient cycles that make the planet habitable for larger organisms. We can now explore the diversity and functions of plankton using genomics, revealing the gene repertoires associated with survival in the oceans. Such studies will help us to appreciate the sensitivity of ocean systems and of the ocean{\textquoteright}s response to climate change, improving the predictive power of climate models.},
	keywords = {Astronomy, astrophysics, Biochemistry, Bioinformatics, Biology, biotechnology, cancer, cell cycle, cell signalling, climate change, Computational Biology, development, developmental biology, DNA, drug discovery, earth science, ecology, environmental science, Evolution, evolutionary biology, functional genomics, Genetics, Genomics, geophysics, immunology, interdisciplinary science, life, marine biology, materials science, medical research, medicine, metabolomics, molecular biology, molecular interactions, nanotechnology, Nature, neurobiology, neuroscience, palaeobiology, pharmacology, Physics, proteomics, quantum physics, RNA, Science, science news, science policy, signal transduction, structural biology, systems biology, transcriptomics},
	isbn = {0028-0836},
	author = {Bowler, Chris and Karl, David M. and Rita R. Colwell}
}
@article {38138,
	title = {A book like its cover},
	journal = {HeredityHeredity},
	volume = {93},
	year = {2004},
	type = {10.1038/sj.hdy.6800475},
	abstract = {An official journal of the Genetics Society, Heredity publishes high-quality articles describing original research and theoretical insights in all areas of genetics. Research papers are complimented by News \& Commentary articles and reviews, keeping researchers and students abreast of hot topics in the field.},
	keywords = {animal and plant breeding, biometrical and statistical genetics, cytogenetics, ecological, eukaryotes, Genetics, Genomics, human population genetics, population and evolutionary genetics, post-genomics},
	isbn = {0018-067X},
	author = {Michael P. Cummings}
}
@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}
}
@article {38283,
	title = {Genetic consequences of ecological reserve design guidelines: An empirical investigation},
	journal = {Conserv GenetConserv Genet},
	volume = {4},
	year = {2003},
	abstract = {We assessed the genetic diversity consequences of applying ecological reserve design guidelines to four federally-listed globally-rare plant species. Consequences were measured using two metrics: proportion of all alleles and of common alleles included in reserves. Common alleles were defined as those alleles having a frequency of greater than or equal to0.05 in at least one population. Four conservation professionals applied ecological reserve guidelines to choose specific populations of each species for inclusion in reserves of size 1 to N - 1, where N is the total number of populations of each species. Information regarding genetic diversity was not used in selecting populations. The resulting reserve designs were compared to random designs, and the agreement among experts was assessed using Kendall{\textquoteright}s coefficient of concordance. Application of ecological reserve design guidelines proved mostly ineffective in capturing more genetic diversity than is captured selecting populations randomly. Meeting established targets for genetic diversity, such as one advocated by the Center for Plant Conservation, required larger numbers of populations than are suggested to be sufficient. Relative performance of expert designs differed among species and was dependent on whether the proportion of all alleles or of common alleles was used as a measure of diversity. Furthermore there was no significant concordance among experts in order in which populations were incorporated into reserves as experts differed in priority they placed on individual guidelines.},
	keywords = {albens, Astragulus, Bernardino, conservation, design, diversity, Erigeron, Eriogonum, genetic, Genetics, goodmaniana, Mountains, ovalifolium, Oxytheca, parishii, plant, reserve, San, var., vineum},
	author = {Neel, M. C. and Michael P. Cummings}
}
@article {38543,
	title = {Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals},
	journal = {J. ACMJ. ACM},
	volume = {46},
	year = {1999},
	type = {10.1145/300515.300516},
	abstract = {Genomes frequently evolve by reversals \&rgr;(i,j) that transform a gene order \&pgr;1 {\textellipsis} \&pgr;i\&pgr;i+1 {\textellipsis} \&pgr;j-1\&pgr;j {\textellipsis} \&pgr;n into \&pgr;1 {\textellipsis} \&pgr;i\&pgr;j-1 {\textellipsis} \&pgr;i+1\&pgr;j {\textellipsis} \&pgr;n. Reversal distance between permutations \&pgr; and \&sgr;is the minimum number of reversals to transform \&pgr; into \&Agr;. Analysis of genome rearrangements in molecular biology started in the late 1930{\textquoteright}s, when Dobzhansky and Sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions between the species of Drosophilia. Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. We study sorting of signed permutations by reversals, a problem that adequately models rearrangements in a small genomes like chloroplast or mitochondrial DNA. The previously suggested approximation algorithms for sorting signed permutations by reversals compute the reversal distance between permutations with an astonishing accuracy for both simulated and biological data. We prove a duality theorem explaining this intriguing performance and show that there exists a {\textquotedblleft}hidden{\textquotedblright} parameter that allows one to compute the reversal distance between signed permutations in polynomial time.},
	keywords = {Computational Biology, Genetics},
	isbn = {0004-5411},
	author = {Sridhar Hannenhalli and Pevzner, Pavel A.}
}
@proceedings {38545,
	title = {Transforming men into mice (polynomial algorithm for genomic distance problem)},
	year = {1995},
	month = {1995},
	publisher = {IEEE Computer Society},
	type = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1995.492588},
	address = {Los Alamitos, CA, USA},
	abstract = {Many people believe that transformations of humans into mice happen only in fairy tales. However, despite some differences in appearance and habits, men and mice are genetically very similar. In the pioneering paper, J.H. Nadeau and B.A. Taylor (1984) estimated that surprisingly few genomic rearrangements (178/spl plusmn/39) happened since the divergence of human and mouse 80 million years ago. However, their analysis is nonconstructive and no rearrangement scenario for human-mouse evolution has been suggested yet. The problem is complicated by the fact that rearrangements in multi chromosomal genomes include inversions, translocations, fusions and fissions of chromosomes, a rather complex set of operations. As a result, at first glance, a polynomial algorithm for the genomic distance problem with all these operations looks almost as improbable as the transformation of a (real) man into a (real) mouse. We prove a duality theorem which expresses the genomic distance in terms of easily computable parameters reflecting different combinatorial properties of sets of strings. This theorem leads to a polynomial time algorithm for computing most parsimonious rearrangement scenarios. Based on this result and the latest comparative physical mapping data we have constructed a scenario of human-mouse evolution with 131 reversals/translocaitons/fusions/fissions. A combination of the genome rearrangement algorithm with the recently proposed experimental technique called ZOO FISH suggests a new constructive approach to the 100 year old problem of reconstructing mammalian evolution.},
	keywords = {biology computing, combinatorial properties, comparative physical mapping data, computable parameters, duality (mathematics), duality theorem, evolution (biological), Genetics, genome rearrangement algorithm, genomic distance problem, genomic rearrangements, human-mouse evolution, mammalian evolution, multi chromosomal genomes, parsimonious rearrangement scenarios, pattern matching, polynomial algorithm, polynomial time algorithm, set theory, sorting, string matching, strings, zoo fish},
	author = {Sridhar Hannenhalli and Pevzner, P. A.}
}
@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.}
}
