@article {46925, title = {Nuclear accessibility of β-actin mRNA is measured by 3D single-molecule real-time tracking.}, journal = {Journal of Cell Biology}, volume = {209}, year = {2015}, month = {2015 May 25}, pages = {609-19}, abstract = {

Imaging single proteins or RNAs allows direct visualization of the inner workings of the cell. Typically, three-dimensional (3D) images are acquired by sequentially capturing a series of 2D sections. The time required to step through the sample often impedes imaging of large numbers of rapidly moving molecules. Here we applied multifocus microscopy (MFM) to instantaneously capture 3D single-molecule real-time images in live cells, visualizing cell nuclei at 10 volumes per second. We developed image analysis techniques to analyze messenger RNA (mRNA) diffusion in the entire volume of the nucleus. Combining MFM with precise registration between fluorescently labeled mRNA, nuclear pore complexes, and chromatin, we obtained globally optimal image alignment within 80-nm precision using transformation models. We show that β-actin mRNAs freely access the entire nucleus and fewer than 60\% of mRNAs are more than 0.5 {\textmu}m away from a nuclear pore, and we do so for the first time accounting for spatial inhomogeneity of nuclear organization.

}, issn = {1540-8140}, doi = {10.1083/jcb.201411032}, author = {Smith, Carlas S and Preibisch, Stephan and Joseph, Aviva and Abrahamsson, Sara and Rieger, Bernd and Myers, Eugene and Singer, Robert H and Grunwald, David} } @article {45418, title = {Atlas-builder software and the eNeuro atlas: resources for developmental biology and neuroscience.}, journal = {Development}, volume = {141}, year = {2014}, month = {2014 Jun}, pages = {2524-32}, abstract = {

A major limitation in understanding embryonic development is the lack of cell type-specific markers. Existing gene expression and marker atlases provide valuable tools, but they typically have one or more limitations: a lack of single-cell resolution; an inability to register multiple expression patterns to determine their precise relationship; an inability to be upgraded by users; an inability to compare novel patterns with the database patterns; and a lack of three-dimensional images. Here, we develop new {\textquoteright}atlas-builder{\textquoteright} software that overcomes each of these limitations. A newly generated atlas is three-dimensional, allows the precise registration of an infinite number of cell type-specific markers, is searchable and is open-ended. Our software can be used to create an atlas of any tissue in any organism that contains stereotyped cell positions. We used the software to generate an {\textquoteright}eNeuro{\textquoteright} atlas of the Drosophila embryonic CNS containing eight transcription factors that mark the major CNS cell types (motor neurons, glia, neurosecretory cells and interneurons). We found neuronal, but not glial, nuclei occupied stereotyped locations. We added 75 new Gal4 markers to the atlas to identify over 50\% of all interneurons in the ventral CNS, and these lines allowed functional access to those interneurons for the first time. We expect the atlas-builder software to benefit a large proportion of the developmental biology community, and the eNeuro atlas to serve as a publicly accessible hub for integrating neuronal attributes - cell lineage, gene expression patterns, axon/dendrite projections, neurotransmitters--and linking them to individual neurons.

}, keywords = {Animals, Axons, Cell Lineage, Central Nervous System, Computational Biology, Databases, Genetic, Dendrites, Drosophila melanogaster, Drosophila Proteins, Gene Expression Profiling, Gene Expression Regulation, Developmental, Genetic Markers, Interneurons, Mice, Neurons, Neurotransmitter Agents, Rats, Software}, issn = {1477-9129}, doi = {10.1242/dev.108720}, author = {Heckscher, Ellie S and Long, Fuhui and Layden, Michael J and Chuang, Chein-Hui and Manning, Laurina and Richart, Jourdain and Pearson, Joseph C and Crews, Stephen T and Peng, Hanchuan and Myers, Eugene and Doe, Chris Q} } @article {6962, title = {Efficient Bayesian-based multiview deconvolution.}, journal = {Nature Methods}, volume = {11}, year = {2014}, month = {2014 Apr 20}, pages = {645-8}, abstract = {

Light-sheet fluorescence microscopy is able to image large specimens with high resolution by capturing the samples from multiple angles. Multiview deconvolution can substantially improve the resolution and contrast of the images, but its application has been limited owing to the large size of the data sets. Here we present a Bayesian-based derivation of multiview deconvolution that drastically improves the convergence time, and we provide a fast implementation using graphics hardware.

}, issn = {1548-7105}, doi = {10.1038/nmeth.2929}, author = {Preibisch, Stephan and Amat, Fernando and Stamataki, Evangelia and Sarov, Mihail and Singer, Robert H and Myers, Eugene and Tomancak, Pavel} } @article {45064, title = {Virtual finger boosts three-dimensional imaging and microsurgery as well as terabyte volume image visualization and analysis.}, journal = {Nature Communications}, volume = {5}, year = {2014}, month = {2014 Jul 11}, pages = {4342}, abstract = {

Three-dimensional (3D) bioimaging, visualization and data analysis are in strong need of powerful 3D exploration techniques. We develop virtual finger (VF) to generate 3D curves, points and regions-of-interest in the 3D space of a volumetric image with a single finger operation, such as a computer mouse stroke, or click or zoom from the 2D-projection plane of an image as visualized with a computer. VF provides efficient methods for acquisition, visualization and analysis of 3D images for roundworm, fruitfly, dragonfly, mouse, rat and human. Specifically, VF enables instant 3D optical zoom-in imaging, 3D free-form optical microsurgery, and 3D visualization and annotation of terabytes of whole-brain image volumes. VF also leads to orders of magnitude better efficiency of automated 3D reconstruction of neurons and similar biostructures over our previous systems. We use VF to generate from images of 1,107 Drosophila GAL4 lines a projectome of a Drosophila brain.

}, issn = {2041-1723}, doi = {10.1038/ncomms5342}, author = {Peng, Hanchuan and Tang, Jianyong and Xiao, Hang and Bria, Alessandro and Zhou, Jianlong and Butler, Victoria and Zhou, Zhi and Gonzalez-Bellido, Paloma T and Oh, Seung W and Chen, Jichao and Mitra, Ananya and Tsien, Richard W and Zeng, Hongkui and Ascoli, Giorgio A and Iannello, Giulio and Hawrylycz, Michael and Myers, Eugene and Long, Fuhui} } @proceedings {46791, title = {Introduction to ImgLib2}, year = {2012}, month = {2012 Oct 24}, address = {Mondorf-les-Bains, Luxembourg}, author = {Preibisch, Stephan and Pietzsch, Tobias and Myers, Eugene and Tomancak, Pavel and Saalfeld, Stephan} } @article {4487, title = {mGRASP enables mapping mammalian synaptic connectivity with light microscopy.}, journal = {Nature Methods}, volume = {9}, year = {2012}, month = {2012 Jan}, pages = {96-102}, abstract = {

The GFP reconstitution across synaptic partners (GRASP) technique, based on functional complementation between two nonfluorescent GFP fragments, can be used to detect the location of synapses quickly, accurately and with high spatial resolution. The method has been previously applied in the nematode and the fruit fly but requires substantial modification for use in the mammalian brain. We developed mammalian GRASP (mGRASP) by optimizing transmembrane split-GFP carriers for mammalian synapses. Using in silico protein design, we engineered chimeric synaptic mGRASP fragments that were efficiently delivered to synaptic locations and reconstituted GFP fluorescence in vivo. Furthermore, by integrating molecular and cellular approaches with a computational strategy for the three-dimensional reconstruction of neurons, we applied mGRASP to both long-range circuits and local microcircuits in the mouse hippocampus and thalamocortical regions, analyzing synaptic distribution in single neurons and in dendritic compartments.

}, issn = {1548-7105}, doi = {10.1038/nmeth.1784}, author = {Kim, Jinhyun and Zhao, Ting and Petralia, Ronald S and Yu, Yang and Peng, Hanchuan and Myers, Eugene and Magee, Jeffrey C} } @article {4310, title = {Anisotropic path searching for automatic neuron reconstruction.}, journal = {Medical Image Analysis}, volume = {15}, year = {2011}, month = {2011 Oct}, pages = {680-9}, abstract = {

Full reconstruction of neuron morphology is of fundamental interest for the analysis and understanding of their functioning. We have developed a novel method capable of automatically tracing neurons in three-dimensional microscopy data. In contrast to template-based methods, the proposed approach makes no assumptions about the shape or appearance of neurite structure. Instead, an efficient seeding approach is applied to capture complex neuronal structures and the tracing problem is solved by computing the optimal reconstruction with a weighted graph. The optimality is determined by the cost function designed for the path between each pair of seeds and by topological constraints defining the component interrelations and completeness. In addition, an automated neuron comparison method is introduced for performance evaluation and structure analysis. The proposed algorithm is computationally efficient and has been validated using different types of microscopy data sets including Drosophila{\textquoteright}s projection neurons and fly neurons with presynaptic sites. In all cases, the approach yielded promising results.

}, issn = {1361-8423}, doi = {10.1016/j.media.2011.05.013}, author = {Xie, Jun and Zhao, Ting and Lee, Tzumin and Myers, Eugene and Peng, Hanchuan} } @article {2700, title = {Automated reconstruction of neuronal morphology based on local geometrical and global structural models.}, journal = {Neuroinformatics}, volume = {9}, year = {2011}, month = {2011 May 6}, pages = {247-61}, abstract = {

Digital reconstruction of neurons from microscope images is an important and challenging problem in neuroscience. In this paper, we propose a model-based method to tackle this problem. We first formulate a model structure, then develop an algorithm for computing it by carefully taking into account morphological characteristics of neurons, as well as the image properties under typical imaging protocols. The method has been tested on the data sets used in the DIADEM competition and produced promising results for four out of the five data sets.

}, issn = {1559-0089}, doi = {10.1007/s12021-011-9120-3}, author = {Zhao, Ting and Xie, Jun and Amat, Fernando and Clack, Nathan and Ahammad, Parvez and Peng, Hanchuan and Long, Fuhui and Myers, Eugene} } @conference {2721, title = {Automatic 3D neuron tracing using all-paths pruning.}, booktitle = {Conference on Intelligent Systems for Molecular Biology}, year = {2011}, month = {2011}, address = {Vienna}, abstract = {

Motivation: Digital reconstruction, or tracing, of 3D neuron structures is critical toward reverse engineering the wiring and functions of a brain. However, despite a number of existing studies, this task is still challenging, especially when a 3D microscopic image has low signal-to-noise ratio (SNR) and fragmented neuron segments. Published work can handle these hard situations only by introducing global prior information, such as where a neurite segment starts and terminates. However, manual incorporation of such global information can be very time consuming. Thus, a completely automatic approach for these hard situations is highly desirable.

Results: We have developed an automatic graph algorithm, called the all-path pruning (APP), to trace the 3D structure of a neuron. To avoid potential mis-tracing of some parts of a neuron, an APP first produces an initial over-reconstruction, by tracing the optimal geodesic shortest path from the seed location to every possible destination voxel/pixel location in the image. Since the initial reconstruction contains all the possible paths and thus could contain redundant structural components (SC), we simplify the entire reconstruction without compromising its connectedness by pruning the redundant structural elements, using a new maximal-covering minimal-redundant (MCMR) subgraph algorithm. We show that MCMR has a linear computational complexity and will converge. We examined the performance of our method using challenging 3D neuronal image datasets of model organisms (e.g. fruit fly).

}, author = {Long, Fuhui and Peng, Hanchuan and Myers, Eugene} } @article {2720, title = {Limiting amounts of centrosome material set centrosome size in C.elegans embryos.}, journal = {Current Biology}, volume = {21}, year = {2011}, month = {2011 Aug 9}, pages = {1259-67}, abstract = {

The ways in which cells set the size of intracellular structures is an important but largely unsolved problem [1]. Early embryonic divisions pose special problems in this regard. Many checkpoints common in somatic cells are missing from these divisions, which are characterized by rapid reductions in cell size and short cell cycles [2]. Embryonic cells must therefore possess simple and robust mechanisms that allow the size of many of their intracellular structures to rapidly scale with cell size.

}, issn = {1879-0445}, doi = {10.1016/j.cub.2011.06.002}, author = {Decker, Markus and Jaensch, Steffen and Pozniakovsky, A and Zinke, A and O{\textquoteright}Connell, K F and Zachariae, W and Myers, Eugene and Hyman, Anthony A} } @article {5297, title = {Proof-editing is the bottleneck of 3D neuron reconstruction: the problem and solutions.}, journal = {Neuroinformatics}, volume = {9}, year = {2011}, month = {2011 Sep}, pages = {103-5}, keywords = {Algorithms, Animals, Computer-Assisted, Data Mining, Humans, Image Cytometry, Image Processing, Imaging, Neuroanatomical Tract-Tracing Techniques, Neurons, Software, Software Design, Three-Dimensional}, issn = {1559-0089}, doi = {10.1007/s12021-010-9090-x}, author = {Peng, Hanchuan and Long, Fuhui and Zhao, Ting and Myers, Eugene} } @article {3839, title = {Simultaneous recognition and segmentation of cells: application in C. elegans.}, journal = {Bioinformatics}, volume = {27}, year = {2011}, month = {2011 Aug 17}, pages = {2895-902}, abstract = {

MOTIVATION: Automatic recognition of cell identities is critical for quantitative measurement, targeting, and manipulation of cells of model animals at single-cell resolution. It has been shown to be a powerful tool for studying gene expression and regulation, cell lineages, and cell fates. Existing methods first segment cells, before applying a recognition algorithm in the second step. As a result, the segmentation errors in the first step directly affect and complicate the subsequent cell recognition step. Moreover, in new experimental settings, some of the image features that have been previously relied upon to recognize cells may not be easy to reproduce, due to limitations on the number of color channels available for fluorescent imaging or to the cost of building transgenic animals. An approach that is more accurate and relies on only a single signal channel is clearly desirable. RESULTS: We have developed a new method, called SRS (for Simultaneous Recognition and Segmentation of cells), and applied it to 3D image stacks of the model organism C. elegans. Given a 3D image stack of the animal and a 3D atlas of target cells, SRS is effectively an atlas-guided voxel classification process: cell recognition is realized by smoothly deforming the atlas to best fit the image, where the segmentation is obtained naturally via classification of all image voxels. The method achieved a 97.7\% overall recognition accuracy in recognizing a key class of marker cells, the body wall muscle (BWM) cells, on a data set of 175 C. elegans image stacks containing 14,118 manually curated BWM cells providing the "ground-truth" for accuracy. This result was achieved without any additional fiducial image features. SRS also automatically identified 14 of the image stacks as involving {\textpm}90-degree rotations. With these stacks excluded from the data set, the recognition accuracy rose to 99.1\%. We also show SRS is generally applicable to other cell-types, e.g. intestinal cells. AVAILABILITY: The supplementary movies can be downloaded from our website http://penglab.janelia.org/proj/celegans_seganno. The method has been implemented as a plug-in program within the V3D system (http://penglab.janelia.org/proj/v3d) and will be released in the V3D plugin source code repository.

}, issn = {1367-4811}, doi = {10.1093/bioinformatics/btr480}, author = {Qu, Lei and Long, Fuhui and Liu, Xiao and Kim, Stuart and Myers, Eugene and Peng, Hanchuan} } @article {2698, title = {Automatic neuron tracing in volumetric microscopy images with anisotropic path searching.}, journal = {Medical Image Computing and Computer-Assisted Intervention: MICCAI International Conference on Medical Image Computing and Computer-Assisted Intervention}, volume = {13}, year = {2010}, month = {2010}, pages = {472-9}, abstract = {

Full reconstruction of neuron morphology is of fundamental interest for the analysis and understanding of neuron function. We have developed a novel method capable of tracing neurons in three-dimensional microscopy data automatically. In contrast to template-based methods, the proposed approach makes no assumptions on the shape or appearance of neuron{\textquoteright}s body. Instead, an efficient seeding approach is applied to find significant pixels almost certainly within complex neuronal structures and the tracing problem is solved by computing an graph tree structure connecting these seeds. In addition, an automated neuron comparison method is introduced for performance evaluation and structure analysis. The proposed algorithm is computationally efficient. Experiments on different types of data show promising results.

}, keywords = {Algorithms, Animals, Anisotropy, Artificial Intelligence, Automated, Cells, Computer-Assisted, Cultured, Humans, Image Enhancement, Image Interpretation, Imaging, Microscopy, Neurons, Pattern Recognition, Reproducibility of Results, Sensitivity and Specificity, Three-Dimensional}, author = {Xie, Jun and Zhao, Ting and Lee, Tzumin and Myers, Eugene and Peng, Hanchuan} } @article {2149, title = {A 3D digital atlas of C. elegans and its application to single-cell analyses.}, journal = {Nature Methods}, volume = {6}, year = {2009}, month = {2009 Sep}, pages = {667-72}, abstract = {

We built a digital nuclear atlas of the newly hatched, first larval stage (L1) of the wild-type hermaphrodite of Caenorhabditis elegans at single-cell resolution from confocal image stacks of 15 individual worms. The atlas quantifies the stereotypy of nuclear locations and provides other statistics on the spatial patterns of the 357 nuclei that could be faithfully segmented and annotated out of the 558 present at this developmental stage. We then developed an automated approach to assign cell names to each nucleus in a three-dimensional image of an L1 worm. We achieved 86\% accuracy in identifying the 357 nuclei automatically. This computational method will allow high-throughput single-cell analyses of the post-embryonic worm, such as gene expression analysis, or ablation or stimulation of cells under computer control in a high-throughput functional screen.

}, keywords = {Animals, Automatic Data Processing, Biological, Caenorhabditis elegans, Cell Lineage, Cell Nucleus, Models}, issn = {1548-7105}, doi = {10.1007/s12021-010-9090-x}, author = {Long, Fuhui and Peng, Hanchuan and Liu, Xiao and Kim, Stuart K and Myers, Eugene} } @conference {2719, title = {Automatic recognition of cells (ARC) for 3D images of C. elegans.}, booktitle = {Proceedings of the 2008 Conference on Computational Molecular Biology (RECOMB) (Singapore, 2008)}, year = {2008}, month = {2008 Apr 2}, abstract = {

The development of high-resolution microscopy makes possible the high-throughput screening of cellular information, such as gene expression at single cell resolution. One of the critical enabling techniques yet to be developed is the automatic recognition or annotation of specific cells in a 3D image stack. In this paper, we present a novel graph-based algorithm, ARC, that determines cell identities in a 3D confocal image of C. elegans based on their highly stereotyped arrangement. This is an essential step in our work on gene expression analysis of C. elegans at the resolution of single cells. Our ARC method integrates both the absolute and relative spatial locations of cells in a C. elegans body. It uses a marker-guided, spatially-constrained, two-stage bipartite matching to find the optimal match between cells in a subject image and cells in 15 template images that have been manually annotated and vetted. We applied ARC to the recognition of cells in 3D confocal images of the first larval stage (L1) of C. elegans hermaphrodites, and achieved an average accuracy of 94.91\%.

}, author = {Long, Fuhui and Peng, Hanchuan and Liu, X and Kim, Stuart K and Myers, Eugene} } @article {2718, title = {Automatic segmentation of nuclei in 3D microscopy images of C. elegans.}, journal = {2007 4TH IEEE International Symposium on Biomedical Imaging: Macro to Nano, VOLS 1-3}, year = {2007}, month = {2007 Apr 12-15}, pages = {536-9}, abstract = {

Automatic segmentation of nuclei in 3D microscopy images is essential for many biological studies including high throughput analysis of gene expression level, morphology, and phenotypes in single cell level. The complexity and variability of the microscopy images present many difficulties to the traditional image segmentation methods. In this paper, we present a new method based on 3D watershed algorithm to segment such images. By using both the intensity information of the image and the geometry information of the appropriately detected foreground mask, our method is robust to intensity fluctuation within nuclei and at the same time sensitive to the intensity and geometrical cues between nuclei. Besides, the method can automatically correct potential segmentation errors by using several post-processing steps. We tested this algorithm on the 3D confocal images of C.elegans, an organism that has been widely used in biological studies. Our results show that the algorithm can segment nuclei in high accuracy despite the non-uniform background, tightly clustered nuclei with different sizes and shapes, fluctuated intensities, and hollow-shaped staining patterns in the images.

}, author = {Long, Fuhui and Peng, Hanchuan and Myers, Eugene} } @article {6494, title = {Evolution of genes and genomes on the Drosophila phylogeny.}, journal = {Nature}, volume = {450}, year = {2007}, month = {2007 Nov 8}, pages = {203-18}, abstract = {

Comparative analysis of multiple genomes in a phylogenetic framework dramatically improves the precision and sensitivity of evolutionary inference, producing more robust results than single-genome analyses can provide. The genomes of 12 Drosophila species, ten of which are presented here for the first time (sechellia, simulans, yakuba, erecta, ananassae, persimilis, willistoni, mojavensis, virilis and grimshawi), illustrate how rates and patterns of sequence divergence across taxa can illuminate evolutionary processes on a genomic scale. These genome sequences augment the formidable genetic tools that have made Drosophila melanogaster a pre-eminent model for animal genetics, and will further catalyse fundamental research on mechanisms of development, cell biology, genetics, disease, neurobiology, behaviour, physiology and evolution. Despite remarkable similarities among these Drosophila species, we identified many putatively non-neutral changes in protein-coding genes, non-coding RNA genes, and cis-regulatory regions. These may prove to underlie differences in the ecology and behaviour of these diverse species.

}, keywords = {Animals, Codon, DNA, DNA Transposable Elements, Drosophila, Drosophila Proteins, Evolution, Gene Order, Genes, Genome, Genomics, Immunity, Insect, Mitochondrial, Molecular, Multigene Family, Phylogeny, Reproduction, RNA, Sequence Alignment, Sequence Analysis, Synteny, Untranslated}, issn = {1476-4687}, doi = {10.1038/nature06341}, author = {Clark, Andrew G and Eisen, Michael B and Smith, Douglas R and Bergman, Casey M and Oliver, Brian and Markow, Therese A and Kaufman, Thomas C and Kellis, Manolis and Gelbart, William and Iyer, Venky N and Pollard, Daniel A and Sackton, Timothy B and Larracuente, Amanda M and Singh, Nadia D and Abad, Jose P and Abt, Dawn N and Adryan, Boris and Aguade, Montserrat and Akashi, Hiroshi and Anderson, Wyatt W and Aquadro, Charles F and Ardell, David H and Arguello, Roman and Artieri, Carlo G and Barbash, Daniel A and Barker, Daniel and Barsanti, Paolo and Batterham, Phil and Batzoglou, Serafim and Begun, Dave and Bhutkar, Arjun and Blanco, Enrico and Bosak, Stephanie A and Bradley, Robert K and Brand, Adrianne D and Brent, Michael R and Brooks, Angela N and Brown, Randall H and Butlin, Roger K and Caggese, Corrado and Calvi, Brian R and Bernardo de Carvalho, A and Caspi, Anat and Castrezana, Sergio and Celniker, Susan E and Chang, Jean L and Chapple, Charles and Chatterji, Sourav and Chinwalla, Asif and Civetta, Alberto and Clifton, Sandra W and Comeron, Josep M and Costello, James C and Coyne, Jerry A and Daub, Jennifer and David, Robert G and Delcher, Arthur L and Delehaunty, Kim and Do, Chuong B and Ebling, Heather and Edwards, Kevin and Eickbush, Thomas and Evans, Jay D and Filipski, Alan and Findeiss, Sven and Freyhult, Eva and Fulton, Lucinda and Fulton, Robert and Garcia, Ana C L and Gardiner, Anastasia and Garfield, David A and Garvin, Barry E and Gibson, Greg and Gilbert, Don and Gnerre, Sante and Godfrey, Jennifer and Good, Robert and Gotea, Valer and Gravely, Brenton and Greenberg, Anthony J and Griffiths-Jones, Sam and Gross, Samuel and Guigo, Roderic and Gustafson, Erik A and Haerty, Wilfried and Hahn, Matthew W and Halligan, Daniel L and Halpern, Aaron L and Halter, Gillian M and Han, Mira V and Heger, Andreas and Hillier, LaDeana and Hinrichs, Angie S and Holmes, Ian and Hoskins, Roger A and Hubisz, Melissa J and Hultmark, Dan and Huntley, Melanie A and Jaffe, David B and Jagadeeshan, Santosh and Jeck, William R and Johnson, Justin and Jones, Corbin D and Jordan, William C and Karpen, Gary H and Kataoka, Eiko and Keightley, Peter D and Kheradpour, Pouya and Kirkness, Ewen F and Koerich, Leonardo B and Kristiansen, Karsten and Kudrna, Dave and Kulathinal, Rob J and Kumar, Sudhir and Kwok, Roberta and Lander, Eric and Langley, Charles H and Lapoint, Richard and Lazzaro, Brian P and Lee, So-Jeong and Levesque, Lisa and Li, Ruiqiang and Lin, Chiao-Feng and Lin, Michael F and Lindblad-Toh, Kerstin and Llopart, Ana and Long, Manyuan and Low, Lloyd and Lozovsky, Elena and Lu, Jian and Luo, Meizhong and Machado, Carlos A and Makalowski, Wojciech and Marzo, Mar and Matsuda, Muneo and Matzkin, Luciano and McAllister, Bryant and McBride, Carolyn S and McKernan, Brendan and McKernan, Kevin and Mendez-Lago, Maria and Minx, Patrick and Mollenhauer, Michael U and Montooth, Kristi and Mount, Stephen M and Mu, Xu and Myers, Eugene and Negre, Barbara and Newfeld, Stuart and Nielsen, Rasmus and Noor, Mohamed A F and O{\textquoteright}Grady, Patrick and Pachter, Lior and Papaceit, Montserrat and Parisi, Matthew J and Parisi, Michael and Parts, Leopold and Pedersen, Jakob S and Pesole, Graziano and Phillippy, Adam M and Ponting, Chris P and Pop, Mihai and Porcelli, Damiano and Powell, Jeffrey R and Prohaska, Sonja and Pruitt, Kim and Puig, Marta and Quesneville, Hadi and Ram, Kristipati Ravi and Rand, David and Rasmussen, Matthew D and Reed, Laura K and Reenan, Robert and Reily, Amy and Remington, Karin A and Rieger, Tania T and Ritchie, Michael G and Robin, Charles and Rogers, Yu-Hui and Rohde, Claudia and Rozas, Julio and Rubenfield, Marc J and Ruiz, Alfredo and Russo, Susan and Salzberg, Steven L and Sanchez-Gracia, Alejandro and Saranga, David J and Sato, Hajime and Schaeffer, Stephen W and Schatz, Michael C and Schlenke, Todd and Schwartz, Russell and Segarra, Carmen and Singh, Rama S and Sirot, Laura and Sirota, Marina and Sisneros, Nicholas B and Smith, Chris D and Smith, Temple F and Spieth, John and Stage, Deborah E and Stark, Alexander and Stephan, Wolfgang and Strausberg, Robert L and Strempel, Sebastian and Sturgill, David and Sutton, Granger and Sutton, Granger G and Tao, Wei and Teichmann, Sarah and Tobari, Yoshiko N and Tomimura, Yoshihiko and Tsolas, Jason M and Valente, Vera L S and Venter, Eli and Venter, J Craig and Vicario, Saverio and Vieira, Filipe G and Vilella, Albert J and Villasante, Alfredo and Walenz, Brian and Wang, Jun and Wasserman, Marvin and Watts, Thomas and Wilson, Derek and Wilson, Richard K and Wing, Rod A and Wolfner, Mariana F and Wong, Alex and Wong, Gane Ka-Shu and Wu, Chung-I and Wu, Gabriel and Yamamoto, Daisuke and Yang, Hsiao-Pei and Yang, Shiaw-Pyng and Yorke, James A and Yoshida, Kiyohito and Zdobnov, Evgeny and Zhang, Peili and Zhang, Yu and Zimin, Aleksey V and Baldwin, Jennifer and Abdouelleil, Amr and Abdulkadir, Jamal and Abebe, Adal and Abera, Brikti and Abreu, Justin and Acer, St Christophe and Aftuck, Lynne and Alexander, Allen and An, Peter and Anderson, Erica and Anderson, Scott and Arachi, Harindra and Azer, Marc and Bachantsang, Pasang and Barry, Andrew and Bayul, Tashi and Berlin, Aaron and Bessette, Daniel and Bloom, Toby and Blye, Jason and Boguslavskiy, Leonid and Bonnet, Claude and Boukhgalter, Boris and Bourzgui, Imane and Brown, Adam and Cahill, Patrick and Channer, Sheridon and Cheshatsang, Yama and Chuda, Lisa and Citroen, Mieke and Collymore, Alville and Cooke, Patrick and Costello, Maura and D{\textquoteright}Aco, Katie and Daza, Riza and De Haan, Georgius and DeGray, Stuart and DeMaso, Christina and Dhargay, Norbu and Dooley, Kimberly and Dooley, Erin and Doricent, Missole and Dorje, Passang and Dorjee, Kunsang and Dupes, Alan and Elong, Richard and Falk, Jill and Farina, Abderrahim and Faro, Susan and Ferguson, Diallo and Fisher, Sheila and Foley, Chelsea D and Franke, Alicia and Friedrich, Dennis and Gadbois, Loryn and Gearin, Gary and Gearin, Christina R and Giannoukos, Georgia and Goode, Tina and Graham, Joseph and Grandbois, Edward and Grewal, Sharleen and Gyaltsen, Kunsang and Hafez, Nabil and Hagos, Birhane and Hall, Jennifer and Henson, Charlotte and Hollinger, Andrew and Honan, Tracey and Huard, Monika D and Hughes, Leanne and Hurhula, Brian and Husby, M Erii and Kamat, Asha and Kanga, Ben and Kashin, Seva and Khazanovich, Dmitry and Kisner, Peter and Lance, Krista and Lara, Marcia and Lee, William and Lennon, Niall and Letendre, Frances and LeVine, Rosie and Lipovsky, Alex and Liu, Xiaohong and Liu, Jinlei and Liu, Shangtao and Lokyitsang, Tashi and Lokyitsang, Yeshi and Lubonja, Rakela and Lui, Annie and MacDonald, Pen and Magnisalis, Vasilia and Maru, Kebede and Matthews, Charles and McCusker, William and McDonough, Susan and Mehta, Teena and Meldrim, James and Meneus, Louis and Mihai, Oana and Mihalev, Atanas and Mihova, Tanya and Mittelman, Rachel and Mlenga, Valentine and Montmayeur, Anna and Mulrain, Leonidas and Navidi, Adam and Naylor, Jerome and Negash, Tamrat and Nguyen, Thu and Nguyen, Nga and Nicol, Robert and Norbu, Choe and Norbu, Nyima and Novod, Nathaniel and O{\textquoteright}Neill, Barry and Osman, Sahal and Markiewicz, Eva and Oyono, Otero L and Patti, Christopher and Phunkhang, Pema and Pierre, Fritz and Priest, Margaret and Raghuraman, Sujaa and Rege, Filip and Reyes, Rebecca and Rise, Cecil and Rogov, Peter and Ross, Keenan and Ryan, Elizabeth and Settipalli, Sampath and Shea, Terry and Sherpa, Ngawang and Shi, Lu and Shih, Diana and Sparrow, Todd and Spaulding, Jessica and Stalker, John and Stange-Thomann, Nicole and Stavropoulos, Sharon and Stone, Catherine and Strader, Christopher and Tesfaye, Senait and Thomson, Talene and Thoulutsang, Yama and Thoulutsang, Dawa and Topham, Kerri and Topping, Ira and Tsamla, Tsamla and Vassiliev, Helen and Vo, Andy and Wangchuk, Tsering and Wangdi, Tsering and Weiand, Michael and Wilkinson, Jane and Wilson, Adam and Yadav, Shailendra and Young, Geneva and Yu, Qing and Zembek, Lisa and Zhong, Danni and Zimmer, Andrew and Zwirko, Zac and Jaffe, David B and Alvarez, Pablo and Brockman, Will and Butler, Jonathan and Chin, CheeWhye and Gnerre, Sante and Grabherr, Manfred and Kleber, Michael and Mauceli, Evan and MacCallum, Iain} } @article {2725, title = {A sublinear algorithm for approximate keyword matching.}, journal = {Algorithmica}, volume = {12}, year = {1994}, month = {1994 Nov}, pages = {345-74}, abstract = {

Given a relatively short query stringW of lengthP, a long subject stringA of lengthN, and a thresholdD, theapproximate keyword search problem is to find all substrings ofA that align withW with not more than D insertions, deletions, and mismatches. In typical applications, such as searching a DNA sequence database, the size of the {\textquotedblleft}database{\textquotedblright}A is much larger than that of the queryW, e.g.,N is on the order of millions or billions andP is a hundred to a thousand. In this paper we present an algorithm that given a precomputedindex of the databaseA, finds rare matches in time that issublinear inN, i.e.,N c for somec\<1. The sequenceA must be overa. finite alphabet σ. More precisely, our algorithm requires 0(DN pow(ɛ)\  logN) expected-time where ɛ=D/P is the maximum number of differences as a percentage of query length, and pow(ɛ) is an increasing and concave function that is 0 when ɛ=0. Thus the algorithm is superior to current O(DN) algorithms when ɛ is small enough to guarantee that pow(ɛ) \< 1. As seen in the paper, this is true for a wide range of ɛ, e.g., ɛ. up to 33\% for DNA sequences ({\textbrokenbar}⌆{\textbrokenbar}=4) and 56\% for proteins sequences ({\textbrokenbar}⌆{\textbrokenbar}=20). In preliminary practical experiments, the approach gives a 50-to 500-fold improvement over previous algorithms for prolems of interest in molecular biology.

}, author = {Myers, Eugene} } @article {2724, title = {Suffix arrays: a new method for on-line string searches.}, journal = {SIAM Journal on Scientific Computing: A Publication of the Society for Industrial and Applied Mathematics}, volume = {22}, year = {1993}, month = {1993}, pages = {935-48}, abstract = {

A new and conceptually simple data structure, called a suffix array, for on-line string searches is introduced in this paper. Constructing and querying suffix arrays is reduced to a sort and search paradigm that employs novel algorithms. The main advantage of suffix arrays over suffix trees is that, in practice, they use three to five times less space. From a complexity standpoint, suffix arrays permit on-line string searches of the type, {\textquoteleft}{\textquoteleft}Is W a substring of A?{\textquoteright}{\textquoteright} to be answered in time O(P + log N), where P is the length of W and N is the length of A, which is competitive with (and in some cases slightly better than) suffix trees. The only drawback is that in those instances where the underlying alphabet is finite and small, suffix trees can be constructed in O(N) time in the worst case, versus O(N log N) time for suffix arrays.

However, we give an augmented algorithm that, regardless of the alphabet size, constructs suffix arrays in O(N) expected time, albeit with lesser space efficiency. We believe that suffix arrays will prove to be better in practice than suffix trees for many applications.

}, author = {Manber, U and Myers, Eugene} } @article {2723, title = {An O(ND) difference algorithm and its variations.}, journal = {Algorithmica}, volume = {1}, year = {1986}, month = {1986 Nov}, pages = {251-66}, abstract = {

The problems of finding a longest common subsequence of two sequences A and B and a shortest edit script for transforming A into B have long been known to be dual problems. In this paper, they are shown to be equivalent to finding a shortest/longest path in an edit graph. Using this perspective, a simple O(ND) time and space algorithm is developed where N is the sum of the lengths of A and B and D is the size of the minimum edit script for A and B. The algorithm performs well when differences are small (sequences are similar) and is consequently fast in typical applications. The algorithm is shown to have O(N +D expected-time performance under a basic stochastic model. A refinement of the algorithm requires only O(N) space, and the use of suffix trees leads to an O(NlgN +D ) time variation.

}, author = {Myers, Eugene} }