@article {49606, title = {Orchestrating high-throughput genomic analysis with Bioconductor.}, volume = {12}, year = {2015}, month = {2015 Feb}, pages = {115-21}, abstract = {

Bioconductor is an open-source, open-development software project for the analysis and comprehension of high-throughput data in genomics and molecular biology. The project aims to enable interdisciplinary research, collaboration and rapid development of scientific software. Based on the statistical programming language R, Bioconductor comprises 934 interoperable packages contributed by a large, diverse community of scientists. Packages cover a range of bioinformatic and statistical applications. They undergo formal initial review and continuous automated testing. We present an overview for prospective users and contributors.

}, keywords = {Computational Biology, Gene Expression Profiling, Genomics, High-Throughput Screening Assays, Programming Languages, software, User-Computer Interface}, issn = {1548-7105}, doi = {10.1038/nmeth.3252}, author = {Huber, Wolfgang and Carey, Vincent J and Gentleman, Robert and Anders, Simon and Carlson, Marc and Carvalho, Benilton S and Bravo, H{\'e}ctor Corrada and Davis, Sean and Gatto, Laurent and Girke, Thomas and Gottardo, Raphael and Hahne, Florian and Hansen, Kasper D and Irizarry, Rafael A and Lawrence, Michael and Love, Michael I and MacDonald, James and Obenchain, Valerie and Ole{\'s}, Andrzej K and Pag{\`e}s, Herv{\'e} and Reyes, Alejandro and Shannon, Paul and Smyth, Gordon K and Tenenbaum, Dan and Waldron, Levi and Morgan, Martin} } @article {49726, title = {Predicting cancer-specific vulnerability via data-driven detection of synthetic lethality.}, journal = {Cell}, volume = {158}, year = {2014}, month = {2014 Aug 28}, pages = {1199-209}, abstract = {

Synthetic lethality occurs when the inhibition of two genes is lethal while the inhibition of each single gene is not. It can be harnessed to selectively treat cancer by identifying inactive genes in a given cancer and targeting their synthetic lethal (SL) partners. We present a data-driven computational pipeline for the genome-wide identification of SL interactions in cancer by analyzing large volumes of cancer genomic data. First, we show that the approach successfully captures known SL partners of tumor suppressors and oncogenes. We then validate SL predictions obtained for the tumor suppressor VHL. Next, we construct a genome-wide network of SL interactions in cancer and demonstrate its value in predicting gene essentiality and clinical prognosis. Finally, we identify synthetic lethality arising from gene overactivation and use it to predict drug efficacy. These results form a computational basis for exploiting synthetic lethality to uncover cancer-specific susceptibilities.

}, keywords = {Breast Neoplasms, Cell Line, Tumor, Computational Biology, Data Mining, Genes, Tumor Suppressor, HUMANS, Neoplasms, Oncogenes, RNA, Small Interfering, workflow}, issn = {1097-4172}, doi = {10.1016/j.cell.2014.07.027}, author = {Jerby-Arnon, Livnat and Pfetzer, Nadja and Waldman, Yedael Y and McGarry, Lynn and James, Daniel and Shanks, Emma and Seashore-Ludlow, Brinton and Weinstock, Adam and Geiger, Tamar and Clemons, Paul A and Gottlieb, Eyal and Ruppin, Eytan} } @article {49572, title = {Sailfish enables alignment-free isoform quantification from RNA-seq reads using lightweight algorithms.}, volume = {32}, year = {2014}, month = {2014 May}, pages = {462-4}, abstract = {

We introduce Sailfish, a computational method for quantifying the abundance of previously annotated RNA isoforms from RNA-seq data. Because Sailfish entirely avoids mapping reads, a time-consuming step in all current methods, it provides quantification estimates much faster than do existing approaches (typically 20 times faster) without loss of accuracy. By facilitating frequent reanalysis of data and reducing the need to optimize parameters, Sailfish exemplifies the potential of lightweight algorithms for efficiently processing sequencing reads.

}, keywords = {algorithms, Brain Chemistry, Computational Biology, HUMANS, Models, Biological, RNA Isoforms, Sequence Analysis, RNA, software}, issn = {1546-1696}, doi = {10.1038/nbt.2862}, author = {Patro, Rob and Mount, Stephen M and Kingsford, Carl} } @article {49736, title = {Stoichiometry of site-specific lysine acetylation in an entire proteome.}, journal = {J Biol Chem}, volume = {289}, year = {2014}, month = {2014 Aug 1}, pages = {21326-38}, abstract = {

Acetylation of lysine ϵ-amino groups influences many cellular processes and has been mapped to thousands of sites across many organisms. Stoichiometric information of acetylation is essential to accurately interpret biological significance. Here, we developed and employed a novel method for directly quantifying stoichiometry of site-specific acetylation in the entire proteome of Escherichia coli. By coupling isotopic labeling and a novel pairing algorithm, our approach performs an in silico enrichment of acetyl peptides, circumventing the need for immunoenrichment. We investigated the function of the sole NAD(+)-dependent protein deacetylase, CobB, on both site-specific and global acetylation. We quantified 2206 peptides from 899 proteins and observed a wide distribution of acetyl stoichiometry, ranging from less than 1\% up to 98\%. Bioinformatic analysis revealed that metabolic enzymes, which either utilize or generate acetyl-CoA, and proteins involved in transcriptional and translational processes displayed the highest degree of acetylation. Loss of CobB led to increased global acetylation at low stoichiometry sites and induced site-specific changes at high stoichiometry sites, and biochemical analysis revealed altered acetyl-CoA metabolism. Thus, this study demonstrates that sirtuin deacetylase deficiency leads to both site-specific and global changes in protein acetylation stoichiometry, affecting central metabolism.

}, keywords = {Acetylation, Amino Acid Sequence, Bacterial Proteins, Chromatography, High Pressure Liquid, Computational Biology, Escherichia coli, Lysine, Molecular Sequence Data, Proteome, Tandem Mass Spectrometry}, issn = {1083-351X}, doi = {10.1074/jbc.M114.581843}, author = {Baeza, Josue and Dowell, James A and Smallegan, Michael J and Fan, Jing and Amador-Noguez, Daniel and Khan, Zia and Denu, John M} } @article {49535, title = {Genomic analysis of sequence-dependent DNA curvature in Leishmania.}, volume = {8}, year = {2013}, month = {2013}, pages = {e63068}, abstract = {

Leishmania major is a flagellated protozoan parasite of medical importance. Like other members of the Trypanosomatidae family, it possesses unique mechanisms of gene expression such as constitutive polycistronic transcription of directional gene clusters, gene amplification, mRNA trans-splicing, and extensive editing of mitochondrial transcripts. The molecular signals underlying most of these processes remain under investigation. In order to investigate the role of DNA secondary structure signals in gene expression, we carried out a genome-wide in silico analysis of the intrinsic DNA curvature. The L. major genome revealed a lower frequency of high intrinsic curvature regions as well as inter- and intra- chromosomal distribution heterogeneity, when compared to prokaryotic and eukaryotic organisms. Using a novel method aimed at detecting region-integrated intrinsic curvature (RIIC), high DNA curvature was found to be associated with regions implicated in transcription initiation. Those include divergent strand-switch regions between directional gene clusters and regions linked to markers of active transcription initiation such as acetylated H3 histone, TRF4 and SNAP50. These findings suggest a role for DNA curvature in transcription initiation in Leishmania supporting the relevance of DNA secondary structures signals.

}, keywords = {Chromosome mapping, Comparative Genomic Hybridization, Computational Biology, DNA, Protozoan, Genome, Protozoan, Genomics, HUMANS, Leishmania, Nucleic Acid Conformation}, issn = {1932-6203}, doi = {10.1371/journal.pone.0063068}, author = {Smircich, Pablo and Forteza, Diego and El-Sayed, Najib M and Garat, Beatriz} } @article {38316, title = {Genomic insights to SAR86, an abundant and uncultivated marine bacterial lineage}, journal = {The ISME journalThe ISME journal}, volume = {6}, year = {2012}, note = {http://www.ncbi.nlm.nih.gov/pubmed/22170421?dopt=Abstract}, type = {10.1038/ismej.2011.189}, abstract = {Bacteria in the 16S rRNA clade SAR86 are among the most abundant uncultivated constituents of microbial assemblages in the surface ocean for which little genomic information is currently available. Bioinformatic techniques were used to assemble two nearly complete genomes from marine metagenomes and single-cell sequencing provided two more partial genomes. Recruitment of metagenomic data shows that these SAR86 genomes substantially increase our knowledge of non-photosynthetic bacteria in the surface ocean. Phylogenomic analyses establish SAR86 as a basal and divergent lineage of γ-proteobacteria, and the individual genomes display a temperature-dependent distribution. Modestly sized at 1.25-1.7 Mbp, the SAR86 genomes lack several pathways for amino-acid and vitamin synthesis as well as sulfate reduction, trends commonly observed in other abundant marine microbes. SAR86 appears to be an aerobic chemoheterotroph with the potential for proteorhodopsin-based ATP generation, though the apparent lack of a retinal biosynthesis pathway may require it to scavenge exogenously-derived pigments to utilize proteorhodopsin. The genomes contain an expanded capacity for the degradation of lipids and carbohydrates acquired using a wealth of tonB-dependent outer membrane receptors. Like the abundant planktonic marine bacterial clade SAR11, SAR86 exhibits metabolic streamlining, but also a distinct carbon compound specialization, possibly avoiding competition.}, keywords = {Computational Biology, Gammaproteobacteria, Genome, Bacterial, Genomic Library, metagenomics, Oceans and Seas, Phylogeny, plankton, Rhodopsin, RNA, Ribosomal, 16S, Seawater}, author = {Dupont, Chris L. and Rusch, Douglas B. and Yooseph, Shibu and Lombardo, Mary-Jane and Richter, R. Alexander and Valas, Ruben and Novotny, Mark and Yee-Greenbaum, Joyclyn and J. Selengut and Haft, Dan H. and Halpern, Aaron L. and Lasken, Roger S. and Nealson, Kenneth and Friedman, Robert and Venter, J. Craig} } @article {49774, title = {Genomic insights to SAR86, an abundant and uncultivated marine bacterial lineage.}, journal = {ISME J}, volume = {6}, year = {2012}, month = {2012 Jun}, pages = {1186-99}, abstract = {

Bacteria in the 16S rRNA clade SAR86 are among the most abundant uncultivated constituents of microbial assemblages in the surface ocean for which little genomic information is currently available. Bioinformatic techniques were used to assemble two nearly complete genomes from marine metagenomes and single-cell sequencing provided two more partial genomes. Recruitment of metagenomic data shows that these SAR86 genomes substantially increase our knowledge of non-photosynthetic bacteria in the surface ocean. Phylogenomic analyses establish SAR86 as a basal and divergent lineage of γ-proteobacteria, and the individual genomes display a temperature-dependent distribution. Modestly sized at 1.25-1.7 Mbp, the SAR86 genomes lack several pathways for amino-acid and vitamin synthesis as well as sulfate reduction, trends commonly observed in other abundant marine microbes. SAR86 appears to be an aerobic chemoheterotroph with the potential for proteorhodopsin-based ATP generation, though the apparent lack of a retinal biosynthesis pathway may require it to scavenge exogenously-derived pigments to utilize proteorhodopsin. The genomes contain an expanded capacity for the degradation of lipids and carbohydrates acquired using a wealth of tonB-dependent outer membrane receptors. Like the abundant planktonic marine bacterial clade SAR11, SAR86 exhibits metabolic streamlining, but also a distinct carbon compound specialization, possibly avoiding competition.

}, keywords = {Computational Biology, Gammaproteobacteria, Genome, Bacterial, Genomic Library, metagenomics, Oceans and Seas, Phylogeny, plankton, Rhodopsin, Rhodopsins, Microbial, RNA, Ribosomal, 16S, Seawater}, issn = {1751-7370}, doi = {10.1038/ismej.2011.189}, author = {Dupont, Chris L and Rusch, Douglas B and Yooseph, Shibu and Lombardo, Mary-Jane and Richter, R Alexander and Valas, Ruben and Novotny, Mark and Yee-Greenbaum, Joyclyn and Selengut, Jeremy D and Haft, Dan H and Halpern, Aaron L and Lasken, Roger S and Nealson, Kenneth and Friedman, Robert and Venter, J Craig} } @article {49740, title = {Global secretome analysis identifies novel mediators of bone metastasis.}, journal = {Cell Res}, volume = {22}, year = {2012}, month = {2012 Sep}, pages = {1339-55}, abstract = {

Bone is the one of the most common sites of distant metastasis of solid tumors. Secreted proteins are known to influence pathological interactions between metastatic cancer cells and the bone stroma. To comprehensively profile secreted proteins associated with bone metastasis, we used quantitative and non-quantitative mass spectrometry to globally analyze the secretomes of nine cell lines of varying bone metastatic ability from multiple species and cancer types. By comparing the secretomes of parental cells and their bone metastatic derivatives, we identified the secreted proteins that were uniquely associated with bone metastasis in these cell lines. We then incorporated bioinformatic analyses of large clinical metastasis datasets to obtain a list of candidate novel bone metastasis proteins of several functional classes that were strongly associated with both clinical and experimental bone metastasis. Functional validation of selected proteins indicated that in vivo bone metastasis can be promoted by high expression of (1) the salivary cystatins CST1, CST2, and CST4; (2) the plasminogen activators PLAT and PLAU; or (3) the collagen functionality proteins PLOD2 and COL6A1. Overall, our study has uncovered several new secreted mediators of bone metastasis and therefore demonstrated that secretome analysis is a powerful method for identification of novel biomarkers and candidate therapeutic targets.

}, keywords = {Animals, Biomarkers, Tumor, Bone Neoplasms, Cell Line, Tumor, Collagen Type VI, Computational Biology, HUMANS, Mass Spectrometry, Mice, Neoplasms, Plasminogen Activators, Procollagen-Lysine, 2-Oxoglutarate 5-Dioxygenase, Proteome, proteomics, Salivary Cystatins}, issn = {1748-7838}, doi = {10.1038/cr.2012.89}, author = {Blanco, Mario Andres and LeRoy, Gary and Khan, Zia and Ale{\v c}kovi{\'c}, Ma{\v s}a and Zee, Barry M and Garcia, Benjamin A and Kang, Yibin} } @article {49536, title = {Transcript expression analysis of putative Trypanosoma brucei GPI-anchored surface proteins during development in the tsetse and mammalian hosts.}, volume = {6}, year = {2012}, month = {2012}, pages = {e1708}, abstract = {

Human African Trypanosomiasis is a devastating disease caused by the parasite Trypanosoma brucei. Trypanosomes live extracellularly in both the tsetse fly and the mammal. Trypanosome surface proteins can directly interact with the host environment, allowing parasites to effectively establish and maintain infections. Glycosylphosphatidylinositol (GPI) anchoring is a common posttranslational modification associated with eukaryotic surface proteins. In T. brucei, three GPI-anchored major surface proteins have been identified: variant surface glycoproteins (VSGs), procyclic acidic repetitive protein (PARP or procyclins), and brucei alanine rich proteins (BARP). The objective of this study was to select genes encoding predicted GPI-anchored proteins with unknown function(s) from the T. brucei genome and characterize the expression profile of a subset during cyclical development in the tsetse and mammalian hosts. An initial in silico screen of putative T. brucei proteins by Big PI algorithm identified 163 predicted GPI-anchored proteins, 106 of which had no known functions. Application of a second GPI-anchor prediction algorithm (FragAnchor), signal peptide and trans-membrane domain prediction software resulted in the identification of 25 putative hypothetical proteins. Eighty-one gene products with hypothetical functions were analyzed for stage-regulated expression using semi-quantitative RT-PCR. The expression of most of these genes were found to be upregulated in trypanosomes infecting tsetse salivary gland and proventriculus tissues, and 38\% were specifically expressed only by parasites infecting salivary gland tissues. Transcripts for all of the genes specifically expressed in salivary glands were also detected in mammalian infective metacyclic trypomastigotes, suggesting a possible role for these putative proteins in invasion and/or establishment processes in the mammalian host. These results represent the first large-scale report of the differential expression of unknown genes encoding predicted T. brucei surface proteins during the complete developmental cycle. This knowledge may form the foundation for the development of future novel transmission blocking strategies against metacyclic parasites.

}, keywords = {Animals, Computational Biology, Gastrointestinal Tract, Gene Expression Profiling, GPI-Linked Proteins, HUMANS, Male, Membrane Proteins, Protozoan Proteins, Real-Time Polymerase Chain Reaction, Salivary Glands, Trypanosoma brucei brucei, Trypanosomiasis, African, Tsetse Flies}, issn = {1935-2735}, doi = {10.1371/journal.pntd.0001708}, author = {Savage, Amy F and Cerqueira, Gustavo C and Regmi, Sandesh and Wu, Yineng and El Sayed, Najib M and Aksoy, Serap} } @article {49745, title = {A computational statistics approach for estimating the spatial range of morphogen gradients.}, journal = {Development}, volume = {138}, year = {2011}, month = {2011 Nov}, pages = {4867-74}, abstract = {

A crucial issue in studies of morphogen gradients relates to their range: the distance over which they can act as direct regulators of cell signaling, gene expression and cell differentiation. To address this, we present a straightforward statistical framework that can be used in multiple developmental systems. We illustrate the developed approach by providing a point estimate and confidence interval for the spatial range of the graded distribution of nuclear Dorsal, a transcription factor that controls the dorsoventral pattern of the Drosophila embryo.

}, keywords = {Animals, Biostatistics, Cleavage Stage, Ovum, Computational Biology, Computer simulation, Drosophila, Drosophila Proteins, Embryo, Nonmammalian, Gene Expression Regulation, Developmental, Genes, Developmental, Imaging, Three-Dimensional, In Situ Hybridization, Fluorescence, Morphogenesis, Osmolar Concentration, Tissue Distribution}, issn = {1477-9129}, doi = {10.1242/dev.071571}, author = {Kanodia, Jitendra S and Kim, Yoosik and Tomer, Raju and Khan, Zia and Chung, Kwanghun and Storey, John D and Lu, Hang and Keller, Philipp J and Shvartsman, Stanislav Y} } @article {38185, title = {A cost-aggregating integer linear program for motif finding}, journal = {Journal of Discrete AlgorithmsJournal of Discrete Algorithms}, volume = {9}, year = {2011}, type = {10.1016/j.jda.2011.04.001}, abstract = {In the motif finding problem one seeks a set of mutually similar substrings within a collection of biological sequences. This is an important and widely-studied problem, as such shared motifs in DNA often correspond to regulatory elements. We study a combinatorial framework where the goal is to find substrings of a given length such that the sum of their pairwise distances is minimized. We describe a novel integer linear program for the problem, which uses the fact that distances between substrings come from a limited set of possibilities allowing for aggregate consideration of sequence position pairs with the same distances. We show how to tighten its linear programming relaxation by adding an exponential set of constraints and give an efficient separation algorithm that can find violated constraints, thereby showing that the tightened linear program can still be solved in polynomial time. We apply our approach to find optimal solutions for the motif finding problem and show that it is effective in practice in uncovering known transcription factor binding sites.}, keywords = {Computational Biology, Integer linear programming, Sequence motif finding}, isbn = {1570-8667}, author = {Kingsford, Carl and Zaslavsky, Elena and Singh, Mona} } @article {49651, title = {Identification of Schistosoma mansoni microRNAs.}, journal = {BMC Genomics}, volume = {12}, year = {2011}, month = {2011}, pages = {47}, abstract = {

BACKGROUND: MicroRNAs (miRNAs) constitute a class of single-stranded RNAs which play a crucial role in regulating development and controlling gene expression by targeting mRNAs and triggering either translation repression or messenger RNA (mRNA) degradation. miRNAs are widespread in eukaryotes and to date over 14,000 miRNAs have been identified by computational and experimental approaches. Several miRNAs are highly conserved across species. In Schistosoma, the full set of miRNAs and their expression patterns during development remain poorly understood. Here we report on the development and implementation of a homology-based detection strategy to search for miRNA genes in Schistosoma mansoni. In addition, we report results on the experimental detection of miRNAs by means of cDNA cloning and sequencing of size-fractionated RNA samples.

RESULTS: Homology search using the high-throughput pipeline was performed with all known miRNAs in miRBase. A total of 6,211 mature miRNAs were used as reference sequences and 110 unique S. mansoni sequences were returned by BLASTn analysis. The existing mature miRNAs that produced these hits are reported, as well as the locations of the homologous sequences in the S. mansoni genome. All BLAST hits aligned with at least 95\% of the miRNA sequence, resulting in alignment lengths of 19-24 nt. Following several filtering steps, 15 potential miRNA candidates were identified using this approach. By sequencing small RNA cDNA libraries from adult worm pairs, we identified 211 novel miRNA candidates in the S. mansoni genome. Northern blot analysis was used to detect the expression of the 30 most frequent sequenced miRNAs and to compare the expression level of these miRNAs between the lung stage schistosomula and adult worm stages. Expression of 11 novel miRNAs was confirmed by northern blot analysis and some presented a stage-regulated expression pattern. Three miRNAs previously identified from S. japonicum were also present in S. mansoni.

CONCLUSION: Evidence for the presence of miRNAs in S. mansoni is presented. The number of miRNAs detected by homology-based computational methods in S. mansoni is limited due to the lack of close relatives in the miRNA repository. In spite of this, the computational approach described here can likely be applied to the identification of pre-miRNA hairpins in other organisms. Construction and analysis of a small RNA library led to the experimental identification of 14 novel miRNAs from S. mansoni through a combination of molecular cloning, DNA sequencing and expression studies. Our results significantly expand the set of known miRNAs in multicellular parasites and provide a basis for understanding the structural and functional evolution of miRNAs in these metazoan parasites.

}, keywords = {Animals, Computational Biology, Genome, Helminth, MicroRNAs, Schistosoma mansoni}, issn = {1471-2164}, doi = {10.1186/1471-2164-12-47}, author = {Sim{\~o}es, Mariana C and Lee, Jonathan and Djikeng, Appolinaire and Cerqueira, Gustavo C and Zerlotini, Adhemar and da Silva-Pereira, Rosiane A and Dalby, Andrew R and LoVerde, Philip and El-Sayed, Najib M and Oliveira, Guilherme} } @article {49728, title = {Predicting selective drug targets in cancer through metabolic networks.}, journal = {Mol Syst Biol}, volume = {7}, year = {2011}, month = {2011}, pages = {501}, abstract = {

The interest in studying metabolic alterations in cancer and their potential role as novel targets for therapy has been rejuvenated in recent years. Here, we report the development of the first genome-scale network model of cancer metabolism, validated by correctly identifying genes essential for cellular proliferation in cancer cell lines. The model predicts 52 cytostatic drug targets, of which 40\% are targeted by known, approved or experimental anticancer drugs, and the rest are new. It further predicts combinations of synthetic lethal drug targets, whose synergy is validated using available drug efficacy and gene expression measurements across the NCI-60 cancer cell line collection. Finally, potential selective treatments for specific cancers that depend on cancer type-specific downregulation of gene expression and somatic mutations are compiled.

}, keywords = {Cell Line, Tumor, Cell Proliferation, Computational Biology, Cytostatic Agents, Down-Regulation, Drug Delivery Systems, Gene Expression Regulation, Neoplastic, HUMANS, Metabolic Networks and Pathways, Models, Biological, Neoplasms, RNA, Small Interfering}, issn = {1744-4292}, doi = {10.1038/msb.2011.35}, author = {Folger, Ori and Jerby, Livnat and Frezza, Christian and Gottlieb, Eyal and Ruppin, Eytan and Shlomi, Tomer} } @article {38522, title = {Tackling the widespread and critical impact of batch effects in high-throughput data}, journal = {Nature reviews. GeneticsNature reviews. Genetics}, volume = {11}, year = {2010}, note = {http://www.ncbi.nlm.nih.gov/pubmed/20838408?dopt=Abstract}, type = {10.1038/nrg2825}, abstract = {High-throughput technologies are widely used, for example to assay genetic variants, gene and protein expression, and epigenetic modifications. One often overlooked complication with such studies is batch effects, which occur because measurements are affected by laboratory conditions, reagent lots and personnel differences. This becomes a major problem when batch effects are correlated with an outcome of interest and lead to incorrect conclusions. Using both published studies and our own analyses, we argue that batch effects (as well as other technical and biological artefacts) are widespread and critical to address. We review experimental and computational approaches for doing so.}, keywords = {biotechnology, Computational Biology, Genomics, Oligonucleotide Array Sequence Analysis, Periodicals as Topic, Research Design, Sequence Analysis, DNA}, author = {Leek, Jeffrey T. and Scharpf, Robert B. and H{\'e}ctor Corrada Bravo and Simcha, David and Langmead, Benjamin and Johnson, W. Evan and Geman, Donald and Baggerly, Keith and Irizarry, Rafael A.} } @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 {49680, title = {A computational survey of candidate exonic splicing enhancer motifs in the model plant Arabidopsis thaliana.}, journal = {BMC Bioinformatics}, volume = {8}, year = {2007}, month = {2007}, pages = {159}, abstract = {

BACKGROUND: Algorithmic approaches to splice site prediction have relied mainly on the consensus patterns found at the boundaries between protein coding and non-coding regions. However exonic splicing enhancers have been shown to enhance the utilization of nearby splice sites.

RESULTS: We have developed a new computational technique to identify significantly conserved motifs involved in splice site regulation. First, 84 putative exonic splicing enhancer hexamers are identified in Arabidopsis thaliana. Then a Gibbs sampling program called ELPH was used to locate conserved motifs represented by these hexamers in exonic regions near splice sites in confirmed genes. Oligomers containing 35 of these motifs have been shown experimentally to induce significant inclusion of A. thaliana exons. Second, integration of our regulatory motifs into two different splice site recognition programs significantly improved the ability of the software to correctly predict splice sites in a large database of confirmed genes. We have released GeneSplicerESE, the improved splice site recognition code, as open source software.

CONCLUSION: Our results show that the use of the ESE motifs consistently improves splice site prediction accuracy.

}, keywords = {Alternative Splicing, Arabidopsis, Computational Biology, Enhancer Elements, Genetic, Exons, Genes, Plant, RNA, Plant}, issn = {1471-2105}, doi = {10.1186/1471-2105-8-159}, author = {Pertea, Mihaela and Mount, Stephen M and Salzberg, Steven L} } @article {49678, title = {Features generated for computational splice-site prediction correspond to functional elements.}, journal = {BMC Bioinformatics}, volume = {8}, year = {2007}, month = {2007}, pages = {410}, abstract = {

BACKGROUND: Accurate selection of splice sites during the splicing of precursors to messenger RNA requires both relatively well-characterized signals at the splice sites and auxiliary signals in the adjacent exons and introns. We previously described a feature generation algorithm (FGA) that is capable of achieving high classification accuracy on human 3{\textquoteright} splice sites. In this paper, we extend the splice-site prediction to 5{\textquoteright} splice sites and explore the generated features for biologically meaningful splicing signals.

RESULTS: We present examples from the observed features that correspond to known signals, both core signals (including the branch site and pyrimidine tract) and auxiliary signals (including GGG triplets and exon splicing enhancers). We present evidence that features identified by FGA include splicing signals not found by other methods.

CONCLUSION: Our generated features capture known biological signals in the expected sequence interval flanking splice sites. The method can be easily applied to other species and to similar classification problems, such as tissue-specific regulatory elements, polyadenylation sites, promoters, etc.

}, keywords = {Computational Biology, HUMANS, Predictive Value of Tests, RNA Splice Sites, RNA, Messenger}, issn = {1471-2105}, doi = {10.1186/1471-2105-8-410}, author = {Dogan, Rezarta Islamaj and Getoor, Lise and Wilbur, W John and Mount, Stephen M} } @article {49681, title = {Spliceosomal small nuclear RNA genes in 11 insect genomes.}, journal = {RNA}, volume = {13}, year = {2007}, month = {2007 Jan}, pages = {5-14}, abstract = {

The removal of introns from the primary transcripts of protein-coding genes is accomplished by the spliceosome, a large macromolecular complex of which small nuclear RNAs (snRNAs) are crucial components. Following the recent sequencing of the honeybee (Apis mellifera) genome, we used various computational methods, ranging from sequence similarity search to RNA secondary structure prediction, to search for putative snRNA genes (including their promoters) and to examine their pattern of conservation among 11 available insect genomes (A. mellifera, Tribolium castaneum, Bombyx mori, Anopheles gambiae, Aedes aegypti, and six Drosophila species). We identified candidates for all nine spliceosomal snRNA genes in all the analyzed genomes. All the species contain a similar number of snRNA genes, with the exception of A. aegypti, whose genome contains more U1, U2, and U5 genes, and A. mellifera, whose genome contains fewer U2 and U5 genes. We found that snRNA genes are generally more closely related to homologs within the same genus than to those in other genera. Promoter regions for all spliceosomal snRNA genes within each insect species share similar sequence motifs that are likely to correspond to the PSEA (proximal sequence element A), the binding site for snRNA activating protein complex, but these promoter elements vary in sequence among the five insect families surveyed here. In contrast to the other insect species investigated, Dipteran genomes are characterized by a rapid evolution (or loss) of components of the U12 spliceosome and a striking loss of U12-type introns.

}, keywords = {Animals, Base Sequence, Bees, Computational Biology, Diptera, Evolution, Molecular, Genes, Insect, Genome, Insect, Molecular Sequence Data, Nucleic Acid Conformation, Phylogeny, Promoter Regions, Genetic, RNA Splicing, RNA, Small Nuclear, Sequence Analysis, RNA, Spliceosomes}, issn = {1355-8382}, doi = {10.1261/rna.259207}, author = {Mount, Stephen M and Gotea, Valer and Lin, Chiao-Feng and Hernandez, Kristina and Makalowski, Wojciech} } @article {49679, title = {SplicePort--an interactive splice-site analysis tool.}, journal = {Nucleic Acids Res}, volume = {35}, year = {2007}, month = {2007 Jul}, pages = {W285-91}, abstract = {

SplicePort is a web-based tool for splice-site analysis that allows the user to make splice-site predictions for submitted sequences. In addition, the user can also browse the rich catalog of features that underlies these predictions, and which we have found capable of providing high classification accuracy on human splice sites. Feature selection is optimized for human splice sites, but the selected features are likely to be predictive for other mammals as well. With our interactive feature browsing and visualization tool, the user can view and explore subsets of features used in splice-site prediction (either the features that account for the classification of a specific input sequence or the complete collection of features). Selected feature sets can be searched, ranked or displayed easily. The user can group features into clusters and frequency plot WebLogos can be generated for each cluster. The user can browse the identified clusters and their contributing elements, looking for new interesting signals, or can validate previously observed signals. The SplicePort web server can be accessed at http://www.cs.umd.edu/projects/SplicePort and http://www.spliceport.org.

}, keywords = {Base Sequence, Chromosome mapping, Computational Biology, Computer simulation, DNA, Genome, HUMANS, Internet, Models, Genetic, Molecular Sequence Data, Pattern Recognition, Automated, RNA Splice Sites, sequence alignment, Sequence Analysis, DNA, User-Computer Interface}, issn = {1362-4962}, doi = {10.1093/nar/gkm407}, author = {Dogan, Rezarta Islamaj and Getoor, Lise and Wilbur, W John and Mount, Stephen M} } @article {49641, title = {Analysis of fat body transcriptome from the adult tsetse fly, Glossina morsitans morsitans.}, journal = {Insect Mol Biol}, volume = {15}, year = {2006}, month = {2006 Aug}, pages = {411-24}, abstract = {

Tsetse flies (Diptera: Glossinidia) are vectors of pathogenic African trypanosomes. To develop a foundation for tsetse physiology, a normalized expressed sequence tag (EST) library was constructed from fat body tissue of immune-stimulated Glossina morsitans morsitans. Analysis of 20,257 high-quality ESTs yielded 6372 unique genes comprised of 3059 tentative consensus (TC) sequences and 3313 singletons (available at http://aksoylab.yale.edu). We analysed the putative fat body transcriptome based on homology to other gene products with known functions available in the public domain. In particular, we describe the immune-related products, reproductive function related yolk proteins and milk-gland protein, iron metabolism regulating ferritins and transferrin, and tsetse{\textquoteright}s major energy source proline biosynthesis. Expression analysis of the three yolk proteins indicates that all are detected in females, while only the yolk protein with similarity to lipases, is expressed in males. Milk gland protein, apparently important for larval nutrition, however, is primarily synthesized by accessory milk gland tissue.

}, keywords = {Adipose Tissue, Animals, Base Sequence, Computational Biology, DNA Primers, Egg Proteins, Expressed Sequence Tags, Female, Gene Expression Profiling, Insect Vectors, Male, Molecular Sequence Data, Reverse Transcriptase Polymerase Chain Reaction, Sequence Analysis, DNA, Sex Factors, Tsetse Flies}, issn = {0962-1075}, doi = {10.1111/j.1365-2583.2006.00649.x}, author = {Attardo, G M and Strickler-Dinglasan, P and Perkin, S A H and Caler, E and Bonaldo, M F and Soares, M B and El-Sayeed, N and Aksoy, S} } @article {49635, title = {Gene synteny and evolution of genome architecture in trypanosomatids.}, journal = {Mol Biochem Parasitol}, volume = {134}, year = {2004}, month = {2004 Apr}, pages = {183-91}, abstract = {

The trypanosomatid protozoa Trypanosoma brucei, Trypanosoma cruzi and Leishmania major are related human pathogens that cause markedly distinct diseases. Using information from genome sequencing projects currently underway, we have compared the sequences of large chromosomal fragments from each species. Despite high levels of divergence at the sequence level, these three species exhibit a striking conservation of gene order, suggesting that selection has maintained gene order among the trypanosomatids over hundreds of millions of years of evolution. The few sites of genome rearrangement between these species are marked by the presence of retrotransposon-like elements, suggesting that retrotransposons may have played an important role in shaping trypanosomatid genome organization. A degenerate retroelement was identified in L. major by examining the regions near breakage points of the synteny. This is the first such element found in L. major suggesting that retroelements were found in the common ancestor of all three species.

}, keywords = {Animals, Computational Biology, Evolution, Molecular, Gene Order, Genome, Protozoan, Genomics, Leishmania major, Multigene Family, Recombination, Genetic, Retroelements, Selection, Genetic, Synteny, Trypanosoma brucei brucei, Trypanosoma cruzi, Trypanosomatina}, issn = {0166-6851}, doi = {10.1016/j.molbiopara.2003.11.012}, author = {Ghedin, Elodie and Bringaud, Frederic and Peterson, Jeremy and Myler, Peter and Berriman, Matthew and Ivens, Alasdair and Andersson, Bj{\"o}rn and Bontempi, Esteban and Eisen, Jonathan and Angiuoli, Sam and Wanless, David and Von Arx, Anna and Murphy, Lee and Lennard, Nicola and Salzberg, Steven and Adams, Mark D and White, Owen and Hall, Neil and Stuart, Kenneth and Fraser, Claire M and el-Sayed, Najib M A} } @article {49687, title = {The draft genome of Ciona intestinalis: insights into chordate and vertebrate origins.}, journal = {Science}, volume = {298}, year = {2002}, month = {2002 Dec 13}, pages = {2157-67}, abstract = {

The first chordates appear in the fossil record at the time of the Cambrian explosion, nearly 550 million years ago. The modern ascidian tadpole represents a plausible approximation to these ancestral chordates. To illuminate the origins of chordate and vertebrates, we generated a draft of the protein-coding portion of the genome of the most studied ascidian, Ciona intestinalis. The Ciona genome contains approximately 16,000 protein-coding genes, similar to the number in other invertebrates, but only half that found in vertebrates. Vertebrate gene families are typically found in simplified form in Ciona, suggesting that ascidians contain the basic ancestral complement of genes involved in cell signaling and development. The ascidian genome has also acquired a number of lineage-specific innovations, including a group of genes engaged in cellulose metabolism that are related to those in bacteria and fungi.

}, keywords = {Alleles, Animals, Apoptosis, Base Sequence, Cellulose, Central Nervous System, Ciona intestinalis, Computational Biology, Endocrine System, Gene Dosage, Gene Duplication, genes, Genes, Homeobox, Genome, Heart, Immunity, Molecular Sequence Data, Multigene Family, Muscle Proteins, Organizers, Embryonic, Phylogeny, Polymorphism, Genetic, Proteins, Sequence Analysis, DNA, Sequence Homology, Nucleic Acid, Species Specificity, Thyroid Gland, Urochordata, Vertebrates}, issn = {1095-9203}, doi = {10.1126/science.1080049}, author = {Dehal, Paramvir and Satou, Yutaka and Campbell, Robert K and Chapman, Jarrod and Degnan, Bernard and De Tomaso, Anthony and Davidson, Brad and Di Gregorio, Anna and Gelpke, Maarten and Goodstein, David M and Harafuji, Naoe and Hastings, Kenneth E M and Ho, Isaac and Hotta, Kohji and Huang, Wayne and Kawashima, Takeshi and Lemaire, Patrick and Martinez, Diego and Meinertzhagen, Ian A and Necula, Simona and Nonaka, Masaru and Putnam, Nik and Rash, Sam and Saiga, Hidetoshi and Satake, Masanobu and Terry, Astrid and Yamada, Lixy and Wang, Hong-Gang and Awazu, Satoko and Azumi, Kaoru and Boore, Jeffrey and Branno, Margherita and Chin-Bow, Stephen and DeSantis, Rosaria and Doyle, Sharon and Francino, Pilar and Keys, David N and Haga, Shinobu and Hayashi, Hiroko and Hino, Kyosuke and Imai, Kaoru S and Inaba, Kazuo and Kano, Shungo and Kobayashi, Kenji and Kobayashi, Mari and Lee, Byung-In and Makabe, Kazuhiro W and Manohar, Chitra and Matassi, Giorgio and Medina, Monica and Mochizuki, Yasuaki and Mount, Steve and Morishita, Tomomi and Miura, Sachiko and Nakayama, Akie and Nishizaka, Satoko and Nomoto, Hisayo and Ohta, Fumiko and Oishi, Kazuko and Rigoutsos, Isidore and Sano, Masako and Sasaki, Akane and Sasakura, Yasunori and Shoguchi, Eiichi and Shin-i, Tadasu and Spagnuolo, Antoinetta and Stainier, Didier and Suzuki, Miho M and Tassy, Olivier and Takatori, Naohito and Tokuoka, Miki and Yagi, Kasumi and Yoshizaki, Fumiko and Wada, Shuichi and Zhang, Cindy and Hyatt, P Douglas and Larimer, Frank and Detter, Chris and Doggett, Norman and Glavina, Tijana and Hawkins, Trevor and Richardson, Paul and Lucas, Susan and Kohara, Yuji and Levine, Michael and Satoh, Nori and Rokhsar, Daniel S} } @article {49630, title = {Identification of non-autonomous non-LTR retrotransposons in the genome of Trypanosoma cruzi.}, journal = {Mol Biochem Parasitol}, volume = {124}, year = {2002}, month = {2002 Sep-Oct}, pages = {73-8}, abstract = {

As observed for most eukaryotic cells, trypanosomatids contains non-LTR retrotransposons randomly inserted in the nuclear genome. Autonomous retroelements which, code for their own transposition, have been characterized in Trypanosoma brucei (ingi) and Trypanosoma cruzi (L1Tc), whereas non-autonomous retroelements have only been characterized in T. brucei (RIME). Here, we have characterized in the genome of Trypanosoma cruzi four complete copies of a non-autonomous non-LTR retrotransposon, called NARTc. This 0.26 kb NARTc element has the characteristics of non-LTR retrotransposons: the presence a poly(dA) tail and of a short flanking duplicated motif. Analysis of the Genome Survey Sequence databases indicated that the Trypanosoma cruzi haploid genome contains about 140 NARTc copies and about twice as many L1Tc copies. Interestingly, the NARTc and L1Tc retroelements share, with the Trypanosoma brucei ingi and RIME retrotransposons, a common sequence (the first 45 bp with 91\% identity), whereas the remaining sequences are very divergent. This suggests that these four trypanosome non-LTR retrotransposons were derived from the same common ancester and the sequence of their 5{\textquoteright}-extremity may have a functional role. In addition, the genome of Leishmania major contains the same conserved motif present in the trypanosome retroelements, whicle no transposable elements have been detected so far in Leishmania sp.

}, keywords = {Animals, Base Sequence, Computational Biology, Genome, Protozoan, Long Interspersed Nucleotide Elements, Molecular Sequence Data, Retroelements, Short Interspersed Nucleotide Elements, Trypanosoma cruzi}, issn = {0166-6851}, author = {Bringaud, Frederic and Garc{\'\i}a-P{\'e}rez, Jos{\'e} Luis and Heras, Sara R and Ghedin, Elodie and El-Sayed, Najib M and Andersson, Bj{\"o}rn and Baltz, Th{\'e}o and Lopez, Manuel C} } @article {49692, title = {The genome sequence of Drosophila melanogaster.}, journal = {Science}, volume = {287}, year = {2000}, month = {2000 Mar 24}, pages = {2185-95}, abstract = {

The fly Drosophila melanogaster is one of the most intensively studied organisms in biology and serves as a model system for the investigation of many developmental and cellular processes common to higher eukaryotes, including humans. We have determined the nucleotide sequence of nearly all of the approximately 120-megabase euchromatic portion of the Drosophila genome using a whole-genome shotgun sequencing strategy supported by extensive clone-based sequence and a high-quality bacterial artificial chromosome physical map. Efforts are under way to close the remaining gaps; however, the sequence is of sufficient accuracy and contiguity to be declared substantially complete and to support an initial analysis of genome structure and preliminary gene annotation and interpretation. The genome encodes approximately 13,600 genes, somewhat fewer than the smaller Caenorhabditis elegans genome, but with comparable functional diversity.

}, keywords = {Animals, Biological Transport, Chromatin, Cloning, Molecular, Computational Biology, Contig Mapping, Cytochrome P-450 Enzyme System, DNA Repair, DNA Replication, Drosophila melanogaster, Euchromatin, Gene Library, Genes, Insect, Genome, Heterochromatin, Insect Proteins, Nuclear Proteins, Protein Biosynthesis, Sequence Analysis, DNA, Transcription, Genetic}, issn = {0036-8075}, author = {Adams, M D and Celniker, S E and Holt, R A and Evans, C A and Gocayne, J D and Amanatides, P G and Scherer, S E and Li, P W and Hoskins, R A and Galle, R F and George, R A and Lewis, S E and Richards, S and Ashburner, M and Henderson, S N and Sutton, G G and Wortman, J R and Yandell, M D and Zhang, Q and Chen, L X and Brandon, R C and Rogers, Y H and Blazej, R G and Champe, M and Pfeiffer, B D and Wan, K H and Doyle, C and Baxter, E G and Helt, G and Nelson, C R and Gabor, G L and Abril, J F and Agbayani, A and An, H J and Andrews-Pfannkoch, C and Baldwin, D and Ballew, R M and Basu, A and Baxendale, J and Bayraktaroglu, L and Beasley, E M and Beeson, K Y and Benos, P V and Berman, B P and Bhandari, D and Bolshakov, S and Borkova, D and Botchan, M R and Bouck, J and Brokstein, P and Brottier, P and Burtis, K C and Busam, D A and Butler, H and Cadieu, E and Center, A and Chandra, I and Cherry, J M and Cawley, S and Dahlke, C and Davenport, L B and Davies, P and de Pablos, B and Delcher, A and Deng, Z and Mays, A D and Dew, I and Dietz, S M and Dodson, K and Doup, L E and Downes, M and Dugan-Rocha, S and Dunkov, B C and Dunn, P and Durbin, K J and Evangelista, C C and Ferraz, C and Ferriera, S and Fleischmann, W and Fosler, C and Gabrielian, A E and Garg, N S and Gelbart, W M and Glasser, K and Glodek, A and Gong, F and Gorrell, J H and Gu, Z and Guan, P and Harris, M and Harris, N L and Harvey, D and Heiman, T J and Hernandez, J R and Houck, J and Hostin, D and Houston, K A and Howland, T J and Wei, M H and Ibegwam, C and Jalali, M and Kalush, F and Karpen, G H and Ke, Z and Kennison, J A and Ketchum, K A and Kimmel, B E and Kodira, C D and Kraft, C and Kravitz, S and Kulp, D and Lai, Z and Lasko, P and Lei, Y and Levitsky, A A and Li, J and Li, Z and Liang, Y and Lin, X and Liu, X and Mattei, B and McIntosh, T C and McLeod, M P and McPherson, D and Merkulov, G and Milshina, N V and Mobarry, C and Morris, J and Moshrefi, A and Mount, S M and Moy, M and Murphy, B and Murphy, L and Muzny, D M and Nelson, D L and Nelson, D R and Nelson, K A and Nixon, K and Nusskern, D R and Pacleb, J M and Palazzolo, M and Pittman, G S and Pan, S and Pollard, J and Puri, V and Reese, M G and Reinert, K and Remington, K and Saunders, R D and Scheeler, F and Shen, H and Shue, B C and Sid{\'e}n-Kiamos, I and Simpson, M and Skupski, M P and Smith, T and Spier, E and Spradling, A C and Stapleton, M and Strong, R and Sun, E and Svirskas, R and Tector, C and Turner, R and Venter, E and Wang, A H and Wang, X and Wang, Z Y and Wassarman, D A and Weinstock, G M and Weissenbach, J and Williams, S M and Worley, K C and Wu, D and Yang, S and Yao, Q A and Ye, J and Yeh, R F and Zaveri, J S and Zhan, M and Zhang, G and Zhao, Q and Zheng, L and Zheng, X H and Zhong, F N and Zhong, W and Zhou, X and Zhu, S and Zhu, X and Smith, H O and Gibbs, R A and Myers, E W and Rubin, G M and Venter, J C} } @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.} }