http://www.bibsonomy.org/burst/user/dzerbino/DNA,BibSonomy BuRST Feed for /user/dzerbino/DNA,2008-09-05T07:25:28+02:00http://www.bibsonomy.org/bibtex/2aa8bc1f2986f316dcdd470da0aa1588d/dzerbinodzerbino2007-09-17T20:19:41+02:00Consensus Analysis, Algorithms, Gene Alignment, Sequence DNA, Software, Humans, Profiling, Expression <span style="color:#555555;">Christopher <a href="http://www.bibsonomy.org/author/Lee">Lee</a> </span><em>Bioinformatics</em><em>19(8):999--1008</em><em>May2003. </em>Mon Sep 17 20:19:41 CEST 2007BioinformaticsMay8999--1008Generating consensus sequences from partial order multiple sequence alignment graphs192003Consensus Analysis, Algorithms, Gene Alignment, Sequence DNA, Software, Humans, Profiling, Expression MOTIVATION: Consensus sequence generation is important in many kinds of sequence analysis ranging from sequence assembly to profile-based iterative search methods. However, how can a consensus be constructed when its inherent assumption-that the aligned sequences form a single linear consensus-is not true? RESULTS: Partial Order Alignment (POA) enables construction and analysis of multiple sequence alignments as directed acyclic graphs containing complex branching structure. Here we present a dynamic programming algorithm (heaviest_bundle) for generating multiple consensus sequences from such complex alignments. The number and relationships of these consensus sequences reveals the degree of structural complexity of the source alignment. This is a powerful and general approach for analyzing and visualizing complex alignment structures, and can be applied to any alignment. We illustrate its value for analyzing expressed sequence alignments to detect alternative splicing, reconstruct full length mRNA isoform sequences from EST fragments, and separate paralog mixtures that can cause incorrect SNP predictions. AVAILABILITY: The heaviest_bundle source code is available at http://www.bioinformatics.ucla.edu/poahttp://www.bibsonomy.org/bibtex/2094f2ea8388f71a5fb448d2e3517059b/dzerbinodzerbino2007-09-17T20:19:41+02:00Acid, Nucleic Repetitive DNA, Genetic, Molecular Homology, Base Alignment, Sequence, Models, Acid Data, Sequences, Sequence <span style="color:#555555;">Yu <a href="http://www.bibsonomy.org/author/Zhang">Zhang</a> und Michael S <a href="http://www.bibsonomy.org/author/Waterman">Waterman</a> </span><em>Proc Natl Acad Sci USA</em><em>102(5):1285--90</em><em>Feb2005. </em>Mon Sep 17 20:19:41 CEST 2007Proc Natl Acad Sci USAFeb51285--90An Eulerian path approach to local multiple alignment for DNA sequences1022005Acid, Nucleic Repetitive DNA, Genetic, Molecular Homology, Base Alignment, Sequence, Models, Acid Data, Sequences, Sequence Expensive computation in handling a large number of sequences limits the application of local multiple sequence alignment. We present an Eulerian path approach to local multiple alignment for DNA sequences. The computational time and memory usage of this approach is approximately linear to the total size of sequences analyzed; hence, it can handle thousands of sequences or millions of letters simultaneously. By constructing a De Bruijn graph, most of the conserved segments are amplified as heavy Eulerian paths in the graph, and the original patterns distributed in sequences are recovered even if they do not exist in any single sequence. This approach can accurately detect unknown conserved regions, for both short and long, conserved and degenerate patterns. We further present a Poisson heuristic to estimate the significance of a local multiple alignment. The performance of our method is demonstrated by finding Alu repeats in the human genome. We compare the results with Alus marked by repeatmasker, where the two programs are in good agreement. Our method is robust under various conditions and superior to other methods in terms of efficiency and accuracy.http://www.bibsonomy.org/bibtex/2150cd10c40aace2c238aaa20c8480e08/dzerbinodzerbino2007-09-17T20:19:41+02:00Algorithms, Alignment, Sequence, Sequence Data, User-Computer Molecular Base Chromosome Analysis, Software, Software Mapping, DNA, Design, Interface <span style="color:#555555;">Daniel D <a href="http://www.bibsonomy.org/author/Sommer">Sommer</a> und Arthur L <a href="http://www.bibsonomy.org/author/Delcher">Delcher</a> und Steven L <a href="http://www.bibsonomy.org/author/Salzberg">Salzberg</a> und Mihai <a href="http://www.bibsonomy.org/author/Pop">Pop</a> </span><em>BMC Bioinformatics</em><em>Feb2007. </em>Mon Sep 17 20:19:41 CEST 2007BMC BioinformaticsFeb64Minimus: a fast, lightweight genome assembler82007Algorithms, Alignment, Sequence, Sequence Data, User-Computer Molecular Base Chromosome Analysis, Software, Software Mapping, DNA, Design, Interface BACKGROUND: Genome assemblers have grown very large and complex in response to the need for algorithms to handle the challenges of large whole-genome sequencing projects. Many of the most common uses of assemblers, however, are best served by a simpler type of assembler that requires fewer software components, uses less memory, and is far easier to install and run. RESULTS: We have developed the Minimus assembler to address these issues, and tested it on a range of assembly problems. We show that Minimus performs well on several small assembly tasks, including the assembly of viral genomes, individual genes, and BAC clones. In addition, we evaluate Minimus' performance in assembling bacterial genomes in order to assess its suitability as a component of a larger assembly pipeline. We show that, unlike other software currently used for these tasks, Minimus produces significantly fewer assembly errors, at the cost of generating a more fragmented assembly. CONCLUSION: We find that for small genomes and other small assembly tasks, Minimus is faster and far more flexible than existing tools. Due to its small size and modular design Minimus is perfectly suited to be a component of complex assembly pipelines. Minimus is released as an open-source software project and the code is available as part of the AMOS project at Sourceforge.http://www.bibsonomy.org/bibtex/281238c67b322e3148e22776c9d9cbf3d/dzerbinodzerbino2007-09-17T20:19:41+02:00Glucose-1-Phosphate Humans, Algorithms, Homology, Nucleotidyltransferases, Plant Sequence RNA, Data, Expressed Databases, Adenylyltransferase, Models, Factors, Genetic, Molecular Messenger, Sensitivity Software, Statistical, Proteins, Sequence, Specificity, Alignment, Tags, Time DNA, Base and Control Quality <span style="color:#555555;">Christopher <a href="http://www.bibsonomy.org/author/Lee">Lee</a> und Catherine <a href="http://www.bibsonomy.org/author/Grasso">Grasso</a> und Mark F <a href="http://www.bibsonomy.org/author/Sharlow">Sharlow</a> </span><em>Bioinformatics</em><em>18(3):452--64</em><em>Mar2002. </em>Mon Sep 17 20:19:41 CEST 2007BioinformaticsMar3452--64Multiple sequence alignment using partial order graphs182002Glucose-1-Phosphate Humans, Algorithms, Homology, Nucleotidyltransferases, Plant Sequence RNA, Data, Expressed Databases, Adenylyltransferase, Models, Factors, Genetic, Molecular Messenger, Sensitivity Software, Statistical, Proteins, Sequence, Specificity, Alignment, Tags, Time DNA, Base and Control Quality MOTIVATION: Progressive Multiple Sequence Alignment (MSA) methods depend on reducing an MSA to a linear profile for each alignment step. However, this leads to loss of information needed for accurate alignment, and gap scoring artifacts. RESULTS: We present a graph representation of an MSA that can itself be aligned directly by pairwise dynamic programming, eliminating the need to reduce the MSA to a profile. This enables our algorithm (Partial Order Alignment (POA)) to guarantee that the optimal alignment of each new sequence versus each sequence in the MSA will be considered. Moreover, this algorithm introduces a new edit operator, homologous recombination, important for multidomain sequences. The algorithm has improved speed (linear time complexity) over existing MSA algorithms, enabling construction of massive and complex alignments (e.g. an alignment of 5000 sequences in 4 h on a Pentium II). We demonstrate the utility of this algorithm on a family of multidomain SH2 proteins, and on EST assemblies containing alternative splicing and polymorphism. AVAILABILITY: The partial order alignment program POA is available at http://www.bioinformatics.ucla.edu/poa.http://www.bibsonomy.org/bibtex/2187f0308ae9e5fa2f47476b9ab180a20/dzerbinodzerbino2007-09-17T20:19:41+02:00Molecular Gene Feasibility DNA, Contig Analysis, Base Sequence Data, Mapping, Expression Algorithms, Profiling, Alignment, Studies, <span style="color:#555555;">Mark <a href="http://www.bibsonomy.org/author/Chaisson">Chaisson</a> und Pavel <a href="http://www.bibsonomy.org/author/Pevzner">Pevzner</a> und Haixu <a href="http://www.bibsonomy.org/author/Tang">Tang</a> </span><em>Bioinformatics</em><em>20(13):2067--74</em><em>Sep2004. </em>Mon Sep 17 20:19:41 CEST 2007BioinformaticsSep132067--74Fragment assembly with short reads202004Molecular Gene Feasibility DNA, Contig Analysis, Base Sequence Data, Mapping, Expression Algorithms, Profiling, Alignment, Studies, MOTIVATION: Current DNA sequencing technology produces reads of about 500-750 bp, with typical coverage under 10x. New sequencing technologies are emerging that produce shorter reads (length 80-200 bp) but allow one to generate significantly higher coverage (30x and higher) at low cost. Modern assembly programs and error correction routines have been tuned to work well with current read technology but were not designed for assembly of short reads. RESULTS: We analyze the limitations of assembling reads generated by these new technologies and present a routine for base-calling in reads prior to their assembly. We demonstrate that while it is feasible to assemble such short reads, the resulting contigs will require significant (if not prohibitive) finishing efforts. AVAILABILITY: Available from the web at http://www.cse.ucsd.edu/groups/bioinformatics/software.htmlhttp://www.bibsonomy.org/bibtex/238f73cc8ed9f2f976ae6a7360b532cfe/dzerbinodzerbino2007-09-17T20:19:41+02:00Mapping Fragmentation, Analysis, Chromosome Algorithms, Data, DNA Sequence, Base Sequence Molecular DNA, <span style="color:#555555;">Eugene W <a href="http://www.bibsonomy.org/author/Myers">Myers</a> </span><em>Bioinformatics</em><em>Sep2005. </em>Mon Sep 17 20:19:41 CEST 2007BioinformaticsSepii79--85The fragment assembly string graph21 Suppl 22005Mapping Fragmentation, Analysis, Chromosome Algorithms, Data, DNA Sequence, Base Sequence Molecular DNA, We present a concept and formalism, the string graph, which represents all that is inferable about a DNA sequence from a collection of shotgun sequencing reads collected from it. We give time and space efficient algorithms for constructing a string graph given the collection of overlaps between the reads and, in particular, present a novel linear expected time algorithm for transitive reduction in this context. The result demonstrates that the decomposition of reads into kmers employed in the de Bruijn graph approach described earlier is not essential, and exposes its close connection to the unitig approach we developed at Celera. This paper is a preliminary piece giving the basic algorithm and results that demonstrate the efficiency and scalability of the method. These ideas are being used to build a next-generation whole genome assembler called BOA (Berkeley Open Assembler) that will easily scale to mammalian genomes.http://www.bibsonomy.org/bibtex/208726a1ee302ce26b55d2d0ae419d2b4/dzerbinodzerbino2007-09-17T20:19:41+02:00Functions, Genetic Regulator, Alignment, Fibrosis Base Likelihood Computer (Genetics), Mammals, Simulation, Cystic Variation Conductance Transmembrane Animals, Molecular Sequence, Molecular, Analysis, Evolution, Phylogeny, Sequence Data, Genome, Models, DNA, <span style="color:#555555;">Mathieu <a href="http://www.bibsonomy.org/author/Blanchette">Blanchette</a> und Eric D <a href="http://www.bibsonomy.org/author/Green">Green</a> und Webb <a href="http://www.bibsonomy.org/author/Miller">Miller</a> und David <a href="http://www.bibsonomy.org/author/Haussler">Haussler</a> </span><em>Genome Res</em><em>14(12):2412--23</em><em>Dec2004. </em>Mon Sep 17 20:19:41 CEST 2007Genome ResDec122412--23Reconstructing large regions of an ancestral mammalian genome in silico142004Functions, Genetic Regulator, Alignment, Fibrosis Base Likelihood Computer (Genetics), Mammals, Simulation, Cystic Variation Conductance Transmembrane Animals, Molecular Sequence, Molecular, Analysis, Evolution, Phylogeny, Sequence Data, Genome, Models, DNA, It is believed that most modern mammalian lineages arose from a series of rapid speciation events near the Cretaceous-Tertiary boundary. It is shown that such a phylogeny makes the common ancestral genome sequence an ideal target for reconstruction. Simulations suggest that with methods currently available, we can expect to get 98% of the bases correct in reconstructing megabase-scale euchromatic regions of an eutherian ancestral genome from the genomes of approximately 20 optimally chosen modern mammals. Using actual genomic sequences from 19 extant mammals, we reconstruct 1.1 Mb of ancient genome sequence around the CFTR locus. Detailed examination suggests the reconstruction is accurate and that it allows us to identify features in modern species, such as remnants of ancient transposon insertions, that were not identified by direct analysis. Tracing the predicted evolutionary history of the bases in the reconstructed region, estimates are made of the amount of DNA turnover due to insertion, deletion, and substitution in the different placental mammalian lineages since the common eutherian ancestor, showing considerable variation between lineages. In coming years, such reconstructions may help in identifying and understanding the genetic features common to eutherian mammals and may shed light on the evolution of human or primate-specific traits.http://www.bibsonomy.org/bibtex/239fe09991ee839c5c69c0ad2c0461d33/dzerbinodzerbino2007-09-17T20:19:41+02:00Statistical Results, of Reproducibility Probability, Mathematics, Models, Sequence, Base DNA, Oligodeoxyribonucleotides, <span style="color:#555555;">E W <a href="http://www.bibsonomy.org/author/Myers">Myers</a> </span><em>J Comput Biol</em><em>2(2):275--90</em><em>Jan1995. </em>Mon Sep 17 20:19:41 CEST 2007J Comput BiolJan2275--90Toward simplifying and accurately formulating fragment assembly21995Statistical Results, of Reproducibility Probability, Mathematics, Models, Sequence, Base DNA, Oligodeoxyribonucleotides, The fragment assembly problem is that of reconstructing a DNA sequence from a collection of randomly sampled fragments. Traditionally, the objective of this problem has been to produce the shortest string that contains all the fragments as substrings, but in the case of repetitive target sequences this objective produces answers that are overcompressed. In this paper, the problem is reformulated as one of finding a maximum-likelihood reconstruction with respect to the two-sided Kolmogorov-Smirnov statistic, and it is argued that this is a better formulation of the problem. Next the fragment assembly problem is recast in graph-theoretic terms as one of finding a noncyclic subgraph with certain properties and the objectives of being shortest or maximally likely are also recast in this framework. Finally, a series of graph reduction transformations are given that dramatically reduce the size of the graph to be explored in practical instances of the problem. This reduction is very important as the underlying problems are NP-hard. In practice, the transformed problems are so small that simple branch-and-bound algorithms successfully solve them, thus permitting auxiliary experimental information to be taken into account in the form of overlap, orientation, and distance constraints.http://www.bibsonomy.org/bibtex/292574a7dfe4924f76351f0ac33eae32d/dzerbinodzerbino2007-09-17T20:19:41+02:00Base Contig Molecular Data, Mapping Sequence, Sequence Analysis, Software, Chromosome Algorithms, DNA, Mapping, <span style="color:#555555;">Ren'e L <a href="http://www.bibsonomy.org/author/Warren">Warren</a> und Granger G <a href="http://www.bibsonomy.org/author/Sutton">Sutton</a> und Steven J M <a href="http://www.bibsonomy.org/author/Jones">Jones</a> und Robert A <a href="http://www.bibsonomy.org/author/Holt">Holt</a> </span><em>Bioinformatics</em><em>23(4):500--1</em><em>Feb2007. </em>Mon Sep 17 20:19:41 CEST 2007BioinformaticsFeb4500--1Assembling millions of short DNA sequences using SSAKE232007Base Contig Molecular Data, Mapping Sequence, Sequence Analysis, Software, Chromosome Algorithms, DNA, Mapping, Novel DNA sequencing technologies with the potential for up to three orders magnitude more sequence throughput than conventional Sanger sequencing are emerging. The instrument now available from Solexa Ltd, produces millions of short DNA sequences of 25 nt each. Due to ubiquitous repeats in large genomes and the inability of short sequences to uniquely and unambiguously characterize them, the short read length limits applicability for de novo sequencing. However, given the sequencing depth and the throughput of this instrument, stringent assembly of highly identical sequences can be achieved. We describe SSAKE, a tool for aggressively assembling millions of short nucleotide sequences by progressively searching through a prefix tree for the longest possible overlap between any two sequences. SSAKE is designed to help leverage the information from short sequence reads by stringently assembling them into contiguous sequences that can be used to characterize novel sequencing targets. Availability: http://www.bcgsc.ca/bioinfo/software/ssake.http://www.bibsonomy.org/bibtex/211f0d08db68b4f73ce33ffab95ffef98/dzerbinodzerbino2007-09-17T20:19:41+02:00Acid, Biology Animals, Chromosome Genes, Molecular Sequences, Repetitive Sequence Heterochromatin, Insect, Analysis, Drosophila Tagged Contig Sites, Euchromatin, Physical melanogaster, Chromatin, Computational Mapping, Data, DNA, Algorithms, Nucleic Genome, <span style="color:#555555;">E W <a href="http://www.bibsonomy.org/author/Myers">Myers</a> und G G <a href="http://www.bibsonomy.org/author/Sutton">Sutton</a> und A L <a href="http://www.bibsonomy.org/author/Delcher">Delcher</a> und I M <a href="http://www.bibsonomy.org/author/Dew">Dew</a> und D P <a href="http://www.bibsonomy.org/author/Fasulo">Fasulo</a> und M J <a href="http://www.bibsonomy.org/author/Flanigan">Flanigan</a> und S A <a href="http://www.bibsonomy.org/author/Kravitz">Kravitz</a> und C M <a href="http://www.bibsonomy.org/author/Mobarry">Mobarry</a> und K H <a href="http://www.bibsonomy.org/author/Reinert">Reinert</a> und K A <a href="http://www.bibsonomy.org/author/Remington">Remington</a> und E L <a href="http://www.bibsonomy.org/author/Anson">Anson</a> und R A <a href="http://www.bibsonomy.org/author/Bolanos">Bolanos</a> und H H <a href="http://www.bibsonomy.org/author/Chou">Chou</a> und C M <a href="http://www.bibsonomy.org/author/Jordan">Jordan</a> und A L <a href="http://www.bibsonomy.org/author/Halpern">Halpern</a> und S <a href="http://www.bibsonomy.org/author/Lonardi">Lonardi</a> und E M <a href="http://www.bibsonomy.org/author/Beasley">Beasley</a> und R C <a href="http://www.bibsonomy.org/author/Brandon">Brandon</a> und L <a href="http://www.bibsonomy.org/author/Chen">Chen</a> und P J <a href="http://www.bibsonomy.org/author/Dunn">Dunn</a> und Z <a href="http://www.bibsonomy.org/author/Lai">Lai</a> und Y <a href="http://www.bibsonomy.org/author/Liang">Liang</a> und D R <a href="http://www.bibsonomy.org/author/Nusskern">Nusskern</a> und M <a href="http://www.bibsonomy.org/author/Zhan">Zhan</a> und Q <a href="http://www.bibsonomy.org/author/Zhang">Zhang</a> und X <a href="http://www.bibsonomy.org/author/Zheng">Zheng</a> und G M <a href="http://www.bibsonomy.org/author/Rubin">Rubin</a> und M D <a href="http://www.bibsonomy.org/author/Adams">Adams</a> und J C <a href="http://www.bibsonomy.org/author/Venter">Venter</a> </span><em>Science</em><em>287(5461):2196--204</em><em>Mar2000. </em>Mon Sep 17 20:19:41 CEST 2007ScienceMar54612196--204A whole-genome assembly of Drosophila2872000Acid, Biology Animals, Chromosome Genes, Molecular Sequences, Repetitive Sequence Heterochromatin, Insect, Analysis, Drosophila Tagged Contig Sites, Euchromatin, Physical melanogaster, Chromatin, Computational Mapping, Data, DNA, Algorithms, Nucleic Genome, We report on the quality of a whole-genome assembly of Drosophila melanogaster and the nature of the computer algorithms that accomplished it. Three independent external data sources essentially agree with and support the assembly's sequence and ordering of contigs across the euchromatic portion of the genome. In addition, there are isolated contigs that we believe represent nonrepetitive pockets within the heterochromatin of the centromeres. Comparison with a previously sequenced 2.9- megabase region indicates that sequencing accuracy within nonrepetitive segments is greater than 99. 99% without manual curation. As such, this initial reconstruction of the Drosophila sequence should be of substantial value to the scientific community.http://www.bibsonomy.org/bibtex/2ee9d2aa5c67377101e1ad619b08eac15/dzerbinodzerbino2007-09-17T20:19:41+02:00Algorithms, Fragmentation DNA Expression Fragment Restriction Profiling, Length, Base Polymorphism, Molecular Alignment, Analysis, Gene Variation Data, DNA, Sequence, (Genetics), Consensus Sequence Genetic, <span style="color:#555555;">Daniel <a href="http://www.bibsonomy.org/author/Fasulo">Fasulo</a> und Aaron <a href="http://www.bibsonomy.org/author/Halpern">Halpern</a> und Ian <a href="http://www.bibsonomy.org/author/Dew">Dew</a> und Clark <a href="http://www.bibsonomy.org/author/Mobarry">Mobarry</a> </span><em>Bioinformatics</em><em>Jan2002. </em>Mon Sep 17 20:19:41 CEST 2007BioinformaticsJanS294--302Efficiently detecting polymorphisms during the fragment assembly process18 Suppl 12002Algorithms, Fragmentation DNA Expression Fragment Restriction Profiling, Length, Base Polymorphism, Molecular Alignment, Analysis, Gene Variation Data, DNA, Sequence, (Genetics), Consensus Sequence Genetic, MOTIVATION: Current genomic sequence assemblers assume that the input data is derived from a single, homogeneous source. However, recent whole-genome shotgun sequencing projects have violated this assumption, resulting in input fragments covering the same region of the genome whose sequences differ due to polymorphic variation in the population. While single-nucleotide polymorphisms (SNPs) do not pose a significant problem to state-of-the-art assembly methods, these methods do not handle insertion/deletion (indel) polymorphisms of more than a few bases. RESULTS: This paper describes an efficient method for detecting sequence discrepencies due to polymorphism that avoids resorting to global use of more costly, less stringent affine sequence alignments. Instead, the algorithm uses graph-based methods to determine the small set of fragments involved in each polymorphism and performs more sophisticated alignments only among fragments in that set. Results from the incorporation of this method into the Celera Assembler are reported for the D. melanogaster, H. sapiens, and M. musculus genomes.http://www.bibsonomy.org/bibtex/29acd2b8b071ac8bb83b8007ef69b9d88/dzerbinodzerbino2007-09-17T20:19:41+02:00Algorithms, Genome, Models, Genomics, Humans, DNA, Analysis, Statistical Animals, Sequence <span style="color:#555555;">Michael C <a href="http://www.bibsonomy.org/author/Wendl">Wendl</a> </span><em>Bull Math Biol</em><em>68(1):179--96</em><em>Jan2006. </em>Mon Sep 17 20:19:41 CEST 2007Bull Math BiolJan1179--96Occupancy modeling of coverage distribution for whole genome shotgun DNA sequencing682006Algorithms, Genome, Models, Genomics, Humans, DNA, Analysis, Statistical Animals, Sequence Expected-value models have long provided a rudimentary theoretical foundation for random DNA sequencing. Here, we are interested in improving characterization of genome coverage in terms of its underlying probability distributions. We find that the mathematical notion of occupancy serves as a good model for evolution of the coverage distribution function and reveals new insights related to sequence redundancy. Established concepts, such as "full shotgun depth," have been assumed invariant, but actually depend on project size and decrease over time. For most microbial projects, the full shotgun milestone should be revised downward by about 30%. Accordingly, many already-completed genomes appear to have been over-sequenced. Results also suggest that read lengths for emerging high-throughput sequencing methods must be increased substantially before they can be considered as possible successors to the standard Sanger method. In particular, gains in throughput and sequence depth cannot be made to compensate for diminished read length. Limits are well approximated by a simple logarithmic equation, which should be useful in estimating maximum coverage-based redundancy for future projects.http://www.bibsonomy.org/bibtex/2502e0622b4d381412eafa06bb77d377e/dzerbinodzerbino2007-09-17T20:19:41+02:00Humans, Studies, Human, Genomics, Analysis, Pair Feasibility Genome, 1, Chromosomes, DNA, Sequence Viral, Bacterial <span style="color:#555555;">Nava <a href="http://www.bibsonomy.org/author/Whiteford">Whiteford</a> und Niall <a href="http://www.bibsonomy.org/author/Haslam">Haslam</a> und Gerald <a href="http://www.bibsonomy.org/author/Weber">Weber</a> und Adam <a href="http://www.bibsonomy.org/author/Pr{\&#034;u}gel-Bennett">Pr&#252;gel-Bennett</a> und Jonathan W <a href="http://www.bibsonomy.org/author/Essex">Essex</a> und Peter L <a href="http://www.bibsonomy.org/author/Roach">Roach</a> und Mark <a href="http://www.bibsonomy.org/author/Bradley">Bradley</a> und Cameron <a href="http://www.bibsonomy.org/author/Neylon">Neylon</a> </span><em>Nucleic Acids Res</em><em>33(19):e171</em><em>Nov2005. </em>Mon Sep 17 20:19:41 CEST 2007Nucleic Acids ResNov19e171An analysis of the feasibility of short read sequencing332005Humans, Studies, Human, Genomics, Analysis, Pair Feasibility Genome, 1, Chromosomes, DNA, Sequence Viral, Bacterial Several methods for ultra high-throughput DNA sequencing are currently under investigation. Many of these methods yield very short blocks of sequence information (reads). Here we report on an analysis showing the level of genome sequencing possible as a function of read length. It is shown that re-sequencing and de novo sequencing of the majority of a bacterial genome is possible with read lengths of 20-30 nt, and that reads of 50 nt can provide reconstructed contigs (a contiguous fragment of sequence data) of 1000 nt and greater that cover 80% of human chromosome 1.http://www.bibsonomy.org/bibtex/21dc921e2ef4587944697d75bf48c2db4/dzerbinodzerbino2007-09-17T20:19:41+02:00Software DNA, Analysis, Sequence Genomics, Computational Genome, Biology, Algorithms, <span style="color:#555555;">Guillaume <a href="http://www.bibsonomy.org/author/Blin">Blin</a> und Eric <a href="http://www.bibsonomy.org/author/Blais">Blais</a> und Danny <a href="http://www.bibsonomy.org/author/Hermelin">Hermelin</a> und Pierre <a href="http://www.bibsonomy.org/author/Guillon">Guillon</a> und Mathieu <a href="http://www.bibsonomy.org/author/Blanchette">Blanchette</a> und Nadia <a href="http://www.bibsonomy.org/author/El-Mabrouk">El-Mabrouk</a> </span><em>J Comput Biol</em><em>14(4):394--407</em><em>May2007. </em>Mon Sep 17 20:19:41 CEST 2007J Comput BiolMay4394--407Gene maps linearization using genomic rearrangement distances142007Software DNA, Analysis, Sequence Genomics, Computational Genome, Biology, Algorithms, A preliminary step to most comparative genomics studies is the annotation of chromosomes as ordered sequences of genes. Different genetic mapping techniques often give rise to different maps with unequal gene content and sets of unordered neighboring genes. Only partial orders can thus be obtained from combining such maps. However, once a total order O is known for a given genome, it can be used as a reference to order genes of a closely related species characterized by a partial order P. Our goal is to find a linearization of P that is as close as possible to O, in term of a given genomic distance. We first prove NP-completeness complexity results considering the breakpoint and the common interval distances. We then focus on the breakpoint distance and give a dynamic programming algorithm whose running time is exponential for general partial orders, but polynomial when the partial order is derived from a bounded number of genetic maps. A time-efficient greedy heuristic is then given for the general case and is empirically shown to produce solutions within 10% of the optimal solution, on simulated data. Applications to the analysis of grass genomes are presented.http://www.bibsonomy.org/bibtex/2d35d83616ff5162f0dc9ae73792e90bf/dzerbinodzerbino2007-09-17T20:19:41+02:00Sensitivity Alignment, Management Sequence, Composition, Specificity and Base DNA, Databases, Factual, Database Systems, Sequence Algorithms, Software, <span style="color:#555555;">Z <a href="http://www.bibsonomy.org/author/Ning">Ning</a> und A J <a href="http://www.bibsonomy.org/author/Cox">Cox</a> und J C <a href="http://www.bibsonomy.org/author/Mullikin">Mullikin</a> </span><em>Genome Res</em><em>11(10):1725--9</em><em>Oct2001. </em>Mon Sep 17 20:19:41 CEST 2007Genome ResOct101725--9SSAHA: a fast search method for large DNA databases112001Sensitivity Alignment, Management Sequence, Composition, Specificity and Base DNA, Databases, Factual, Database Systems, Sequence Algorithms, Software, We describe an algorithm, SSAHA (Sequence Search and Alignment by Hashing Algorithm), for performing fast searches on databases containing multiple gigabases of DNA. Sequences in the database are preprocessed by breaking them into consecutive k-tuples of k contiguous bases and then using a hash table to store the position of each occurrence of each k-tuple. Searching for a query sequence in the database is done by obtaining from the hash table the "hits" for each k-tuple in the query sequence and then performing a sort on the results. We discuss the effect of the tuple length k on the search speed, memory usage, and sensitivity of the algorithm and present the results of computational experiments which show that SSAHA can be three to four orders of magnitude faster than BLAST or FASTA, while requiring less memory than suffix tree methods. The SSAHA algorithm is used for high-throughput single nucleotide polymorphism (SNP) detection and very large scale sequence assembly. Also, it provides Web-based sequence search facilities for Ensembl projects.http://www.bibsonomy.org/bibtex/2e05ca61552c8d9f5951978da7619860d/dzerbinodzerbino2007-09-17T20:19:41+02:00Sequence Duplication, Bacterial Algorithms, Genome, Software, Gene Computational Gammaproteobacteria, DNA, Biology, Analysis, <span style="color:#555555;">S'ebastien <a href="http://www.bibsonomy.org/author/Angibaud">Angibaud</a> und Guillaume <a href="http://www.bibsonomy.org/author/Fertin">Fertin</a> und Irena <a href="http://www.bibsonomy.org/author/Rusu">Rusu</a> und St'ephane <a href="http://www.bibsonomy.org/author/Vialette">Vialette</a> </span><em>J Comput Biol</em><em>14(4):379--93</em><em>May2007. </em>Mon Sep 17 20:19:41 CEST 2007J Comput BiolMay4379--93A pseudo-boolean framework for computing rearrangement distances between genomes with duplicates142007Sequence Duplication, Bacterial Algorithms, Genome, Software, Gene Computational Gammaproteobacteria, DNA, Biology, Analysis, Computing genomic distances between whole genomes is a fundamental problem in comparative genomics. Recent researches have resulted in different genomic distance definitions, for example, number of breakpoints, number of common intervals, number of conserved intervals, and Maximum Adjacency Disruption number. Unfortunately, it turns out that, in presence of duplications, most problems are NP-hard, and hence several heuristics have been recently proposed. However, while it is relatively easy to compare heuristics between them, until now very little is known about the absolute accuracy of these heuristics. Therefore, there is a great need for algorithmic approaches that compute exact solutions for these genomic distances. In this paper, we present a novel generic pseudo-boolean approach for computing the exact genomic distance between two whole genomes in presence of duplications, and put strong emphasis on common intervals under the maximum matching model. Of particular importance, we show three heuristics which provide very good results on a well-known public dataset of gamma-Proteobacteria.http://www.bibsonomy.org/bibtex/285853a4fe7db3494508d6631d10f55ca/dzerbinodzerbino2007-09-17T20:19:41+02:00Models, Contig Software, Analysis, lactis Sequence Mapping, DNA, Algorithms, Theoretical, Alignment, Bacterial, Neisseria Campylobacter Genome, jejuni, Lactococcus meningitidis, <span style="color:#555555;">P A <a href="http://www.bibsonomy.org/author/Pevzner">Pevzner</a> und H <a href="http://www.bibsonomy.org/author/Tang">Tang</a> und M S <a href="http://www.bibsonomy.org/author/Waterman">Waterman</a> </span><em>Proc Natl Acad Sci USA</em><em>98(17):9748--53</em><em>Aug2001. </em>Mon Sep 17 20:19:41 CEST 2007Proc Natl Acad Sci USAAug179748--53An Eulerian path approach to DNA fragment assembly982001Models, Contig Software, Analysis, lactis Sequence Mapping, DNA, Algorithms, Theoretical, Alignment, Bacterial, Neisseria Campylobacter Genome, jejuni, Lactococcus meningitidis, For the last 20 years, fragment assembly in DNA sequencing followed the "overlap-layout-consensus" paradigm that is used in all currently available assembly tools. Although this approach proved useful in assembling clones, it faces difficulties in genomic shotgun assembly. We abandon the classical "overlap-layout-consensus" approach in favor of a new euler algorithm that, for the first time, resolves the 20-year-old "repeat problem" in fragment assembly. Our main result is the reduction of the fragment assembly to a variation of the classical Eulerian path problem that allows one to generate accurate solutions of large-scale sequencing problems. euler, in contrast to the celera assembler, does not mask such repeats but uses them instead as a powerful fragment assembly tool.http://www.bibsonomy.org/bibtex/26fefee7c3e5e1c27b6a90750a6c4c153/dzerbinodzerbino2007-09-17T20:19:41+02:00Gene Sequence Analysis, Algorithms, Alignment, Expression Genetic, Regulation, Chains, Profiling, DNA, Markov Molecular, Cluster Homology Evolution, Statistical, Protein, Models, Software, <span style="color:#555555;">I <a href="http://www.bibsonomy.org/author/Holmes">Holmes</a> </span><em>Bioinformatics</em><em>Jan2003. </em>Mon Sep 17 20:19:41 CEST 2007BioinformaticsJani147--57Using guide trees to construct multiple-sequence evolutionary HMMs19 Suppl 12003Gene Sequence Analysis, Algorithms, Alignment, Expression Genetic, Regulation, Chains, Profiling, DNA, Markov Molecular, Cluster Homology Evolution, Statistical, Protein, Models, Software, MOTIVATION: Score-based progressive alignment algorithms do dynamic programming on successive branches of a guide tree. The analogous probabilistic construct is an Evolutionary HMM. This is a multiple-sequence hidden Markov model (HMM) made by combining transducers (conditionally normalised Pair HMMs) on the branches of a phylogenetic tree. METHODS: We present general algorithms for constructing an Evolutionary HMM from any Pair HMM and for doing dynamic programming to any Multiple-sequence HMM. RESULTS: Our prototype implementation, Handel, is based on the Thorne-Kishino-Felsenstein evolutionary model and is benchmarked using structural reference alignments.