http://www.bibsonomy.org/burst/user/dzerbino/Algorithms,BibSonomy BuRST Feed for /user/dzerbino/Algorithms,2008-10-13T08:55:09+02:00http://www.bibsonomy.org/bibtex/2aa8bc1f2986f316dcdd470da0aa1588d/dzerbinodzerbino2007-09-17T20:19:41+02:00Profiling, Gene Software, Humans, Consensus Expression Sequence Alignment, Algorithms, DNA, Analysis, <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 graphs192003Profiling, Gene Software, Humans, Consensus Expression Sequence Alignment, Algorithms, DNA, Analysis, 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/217ec918bb871c3d8239479bd26364a71/dzerbinodzerbino2007-09-17T20:19:41+02:00Fungal, Humans Human, melanogaster, influenzae, Consensus Haemophilus Algorithms, Alignment, Contig Animals, Genome, cerevisiae, Software, Saccharomyces Sequence, Mapping, Sequence Bacterial, Drosophila <span style="color:#555555;">Serafim <a href="http://www.bibsonomy.org/author/Batzoglou">Batzoglou</a> und David B <a href="http://www.bibsonomy.org/author/Jaffe">Jaffe</a> und Ken <a href="http://www.bibsonomy.org/author/Stanley">Stanley</a> und Jonathan <a href="http://www.bibsonomy.org/author/Butler">Butler</a> und Sante <a href="http://www.bibsonomy.org/author/Gnerre">Gnerre</a> und Evan <a href="http://www.bibsonomy.org/author/Mauceli">Mauceli</a> und Bonnie <a href="http://www.bibsonomy.org/author/Berger">Berger</a> und Jill P <a href="http://www.bibsonomy.org/author/Mesirov">Mesirov</a> und Eric S <a href="http://www.bibsonomy.org/author/Lander">Lander</a> </span><em>Genome Res</em><em>12(1):177--89</em><em>Jan2002. </em>Mon Sep 17 20:19:41 CEST 2007Genome ResJan1177--89ARACHNE: a whole-genome shotgun assembler122002Fungal, Humans Human, melanogaster, influenzae, Consensus Haemophilus Algorithms, Alignment, Contig Animals, Genome, cerevisiae, Software, Saccharomyces Sequence, Mapping, Sequence Bacterial, Drosophila We describe a new computer system, called ARACHNE, for assembling genome sequence using paired-end whole-genome shotgun reads. ARACHNE has several key features, including an efficient and sensitive procedure for finding read overlaps, a procedure for scoring overlaps that achieves high accuracy by correcting errors before assembly, read merger based on forward-reverse links, and detection of repeat contigs by forward-reverse link inconsistency. To test ARACHNE, we created simulated reads providing approximately 10-fold coverage of the genomes of H. influenzae, S. cerevisiae, and D. melanogaster, as well as human chromosomes 21 and 22. The assemblies of these simulated reads yielded nearly complete coverage of the respective genomes, with a small number of contigs joined into a smaller number of supercontigs (or scaffolds). For example, analysis of the D. melanogaster genome yielded approximately 98% coverage with an N50 contig length of 324 kb and an N50 supercontig length of 5143 kb. The assembly accuracy was high, although not perfect: small errors occurred at a frequency of roughly 1 per 1 Mb (typically, deletion of approximately 1 kb in size), with a very small number of other misassemblies. The assembly was rapid: the Drosophila assembly required only 21 hours on a single 667 MHz processor and used 8.4 Gb of memory.http://www.bibsonomy.org/bibtex/2150cd10c40aace2c238aaa20c8480e08/dzerbinodzerbino2007-09-17T20:19:41+02:00Software Base Chromosome User-Computer Algorithms, Alignment, Analysis, Interface Software, Mapping, Sequence, Sequence Design, Data, Molecular DNA, <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 assembler82007Software Base Chromosome User-Computer Algorithms, Alignment, Analysis, Interface Software, Mapping, Sequence, Sequence Design, Data, Molecular DNA, 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/2e2924e542de58d497e99b128d8659faa/dzerbinodzerbino2007-09-17T20:19:41+02:00Animals, Genome, Software, Humans Mapping, Computational Sequence Alignment, Algorithms, Mice, Contig Biology, <span style="color:#555555;">Xiaoqiu <a href="http://www.bibsonomy.org/author/Huang">Huang</a> und Jianmin <a href="http://www.bibsonomy.org/author/Wang">Wang</a> und Srinivas <a href="http://www.bibsonomy.org/author/Aluru">Aluru</a> und Shiaw-Pyng <a href="http://www.bibsonomy.org/author/Yang">Yang</a> und LaDeana <a href="http://www.bibsonomy.org/author/Hillier">Hillier</a> </span><em>Genome Res</em><em>13(9):2164--70</em><em>Sep2003. </em>Mon Sep 17 20:19:41 CEST 2007Genome ResSep92164--70PCAP: a whole-genome assembly program132003Animals, Genome, Software, Humans Mapping, Computational Sequence Alignment, Algorithms, Mice, Contig Biology, We describe a whole-genome assembly program named PCAP for processing tens of millions of reads. The PCAP program has several features to address efficiency and accuracy issues in assembly. Multiple processors are used to perform most time-consuming computations in assembly. A more sensitive method is used to avoid missing overlaps caused by sequencing errors. Repetitive regions of reads are detected on the basis of many overlaps with other reads, instead of many shorter word matches with other reads. Contaminated end regions of reads are identified and removed. Generation of a consensus sequence for a contig is based on an alignment of reads in the contig, in which both base quality values and coverage information are used to determine every consensus base. The PCAP program was tested on a mouse whole-genome data set of 30 million reads and a human Chromosome 20 data set of 1.7 million reads. The program is freely available for academic use.http://www.bibsonomy.org/bibtex/24296f5595607517ac76189523adbafdb/dzerbinodzerbino2007-09-17T20:19:41+02:00Software, Homology, Acid Protein, Databases, Amino Sequence Genetic, Alignment, Algorithms, Analysis, <span style="color:#555555;">Benjamin <a href="http://www.bibsonomy.org/author/Raphael">Raphael</a> und Degui <a href="http://www.bibsonomy.org/author/Zhi">Zhi</a> und Haixu <a href="http://www.bibsonomy.org/author/Tang">Tang</a> und Pavel <a href="http://www.bibsonomy.org/author/Pevzner">Pevzner</a> </span><em>Genome Res</em><em>14(11):2336--46</em><em>Nov2004. </em>Mon Sep 17 20:19:41 CEST 2007Genome ResNov112336--46A novel method for multiple alignment of sequences with repeated and shuffled elements142004Software, Homology, Acid Protein, Databases, Amino Sequence Genetic, Alignment, Algorithms, Analysis, We describe ABA (A-Bruijn alignment), a new method for multiple alignment of biological sequences. The major difference between ABA and existing multiple alignment methods is that ABA represents an alignment as a directed graph, possibly containing cycles. This representation provides more flexibility than does a traditional alignment matrix or the recently introduced partial order alignment (POA) graph by allowing a larger class of evolutionary relationships between the aligned sequences. Our graph representation is particularly well-suited to the alignment of protein sequences with shuffled and/or repeated domain structure, and allows one to construct multiple alignments of proteins containing (1) domains that are not present in all proteins, (2) domains that are present in different orders in different proteins, and (3) domains that are present in multiple copies in some proteins. In addition, ABA is useful in the alignment of genomic sequences that contain duplications and inversions. We provide several examples illustrating the applications of ABA.http://www.bibsonomy.org/bibtex/281238c67b322e3148e22776c9d9cbf3d/dzerbinodzerbino2007-09-17T20:19:41+02:00Base Humans, Proteins, Quality Databases, Nucleotidyltransferases, Alignment, Algorithms, Control Specificity, RNA, Time Software, Homology, Tags, Factors, Genetic, Sequence Glucose-1-Phosphate Molecular Sensitivity Plant Adenylyltransferase, Messenger, and Models, Expressed Statistical, Sequence, Data, DNA, <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 graphs182002Base Humans, Proteins, Quality Databases, Nucleotidyltransferases, Alignment, Algorithms, Control Specificity, RNA, Time Software, Homology, Tags, Factors, Genetic, Sequence Glucose-1-Phosphate Molecular Sensitivity Plant Adenylyltransferase, Messenger, and Models, Expressed Statistical, Sequence, Data, DNA, 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/251d90db8174d7d1da830b654951e5ea0/dzerbinodzerbino2007-09-17T20:19:41+02:00Humans, Human, Multigene Linkage (Genetics), Algorithms, Alignment, Cluster Sequences, Nucleic Analysis, Biology, Contig Acid, Genome, Mapping, Computational Family Artificial, Chromosomes, Sequence Repetitive Bacterial, <span style="color:#555555;">Pavel A <a href="http://www.bibsonomy.org/author/Pevzner">Pevzner</a> und Paul A <a href="http://www.bibsonomy.org/author/Pevzner">Pevzner</a> und Haixu <a href="http://www.bibsonomy.org/author/Tang">Tang</a> und Glenn <a href="http://www.bibsonomy.org/author/Tesler">Tesler</a> </span><em>Genome Res</em><em>14(9):1786--96</em><em>Sep2004. </em>Mon Sep 17 20:19:41 CEST 2007Genome ResSep91786--96De novo repeat classification and fragment assembly142004Humans, Human, Multigene Linkage (Genetics), Algorithms, Alignment, Cluster Sequences, Nucleic Analysis, Biology, Contig Acid, Genome, Mapping, Computational Family Artificial, Chromosomes, Sequence Repetitive Bacterial, Repetitive sequences make up a significant fraction of almost any genome, and an important and still open question in bioinformatics is how to represent all repeats in DNA sequences. We propose a new approach to repeat classification that represents all repeats in a genome as a mosaic of sub-repeats. Our key algorithmic idea also leads to new approaches to multiple alignment and fragment assembly. In particular, we show that our FragmentGluer assembler improves on Phrap and ARACHNE in assembly of BACs and bacterial genomes.http://www.bibsonomy.org/bibtex/2ccc1431d60d762580edc392082a74be9/dzerbinodzerbino2007-09-17T20:19:41+02:00Software Acid Protein, Databases, Benchmarking, Algorithms, Alignment, Biology, Software, (Genetics) Amino Sequence, Computational Variation Validation, Sequence Data, Molecular <span style="color:#555555;">Chuong B <a href="http://www.bibsonomy.org/author/Do">Do</a> und Mahathi S P <a href="http://www.bibsonomy.org/author/Mahabhashyam">Mahabhashyam</a> und Michael <a href="http://www.bibsonomy.org/author/Brudno">Brudno</a> und Serafim <a href="http://www.bibsonomy.org/author/Batzoglou">Batzoglou</a> </span><em>Genome Res</em><em>15(2):330--40</em><em>Feb2005. </em>Mon Sep 17 20:19:41 CEST 2007Genome ResFeb2330--40ProbCons: Probabilistic consistency-based multiple sequence alignment152005Software Acid Protein, Databases, Benchmarking, Algorithms, Alignment, Biology, Software, (Genetics) Amino Sequence, Computational Variation Validation, Sequence Data, Molecular To study gene evolution across a wide range of organisms, biologists need accurate tools for multiple sequence alignment of protein families. Obtaining accurate alignments, however, is a difficult computational problem because of not only the high computational cost but also the lack of proper objective functions for measuring alignment quality. In this paper, we introduce probabilistic consistency, a novel scoring function for multiple sequence comparisons. We present ProbCons, a practical tool for progressive protein multiple sequence alignment based on probabilistic consistency, and evaluate its performance on several standard alignment benchmark data sets. On the BAliBASE, SABmark, and PREFAB benchmark alignment databases, ProbCons achieves statistically significant improvement over other leading methods while maintaining practical speed. ProbCons is publicly available as a Web resource.http://www.bibsonomy.org/bibtex/2187f0308ae9e5fa2f47476b9ab180a20/dzerbinodzerbino2007-09-17T20:19:41+02:00Base Feasibility Gene Profiling, Studies, Algorithms, Alignment, Analysis, Contig Mapping, Expression Sequence Data, Molecular DNA, <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 reads202004Base Feasibility Gene Profiling, Studies, Algorithms, Alignment, Analysis, Contig Mapping, Expression Sequence Data, Molecular DNA, 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:00Base Fragmentation, Sequence, DNA Chromosome Mapping Sequence Algorithms, Molecular Data, DNA, Analysis, <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 22005Base Fragmentation, Sequence, DNA Chromosome Mapping Sequence Algorithms, Molecular Data, DNA, Analysis, 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/2d9334e2d25ffcac3e74f3caa0122db9e/dzerbinodzerbino2007-09-17T20:19:41+02:00Evolution, Gene Humans, Human, Order, Rearrangement, Algorithms, Animals, Cats, Molecular, Chromosomes Genome, Models, Chromosomes, Genetic, Mice, <span style="color:#555555;">Guillaume <a href="http://www.bibsonomy.org/author/Bourque">Bourque</a> und Pavel A <a href="http://www.bibsonomy.org/author/Pevzner">Pevzner</a> </span><em>Genome Res</em><em>12(1):26--36</em><em>Jan2002. </em>Mon Sep 17 20:19:41 CEST 2007Genome ResJan126--36Genome-scale evolution: reconstructing gene orders in the ancestral species122002Evolution, Gene Humans, Human, Order, Rearrangement, Algorithms, Animals, Cats, Molecular, Chromosomes Genome, Models, Chromosomes, Genetic, Mice, Recent progress in genome-scale sequencing and comparative mapping raises new challenges in studies of genome rearrangements. Although the pairwise genome rearrangement problem is well-studied, algorithms for reconstructing rearrangement scenarios for multiple species are in great need. The previous approaches to multiple genome rearrangement problem were largely based on the breakpoint distance rather than on a more biologically accurate rearrangement (reversal) distance. Another shortcoming of the existing software tools is their inability to analyze rearrangements (inversions, translocations, fusions, and fissions) of multichromosomal genomes. This paper proposes a new multiple genome rearrangement algorithm that is based on the rearrangement (rather than breakpoint) distance and that is applicable to both unichromosomal and multichromosomal genomes. We further apply this algorithm for genome-scale phylogenetic tree reconstruction and deriving ancestral gene orders. In particular, our analysis suggests a new improved rearrangement scenario for a very difficult Campanulaceae cpDNA dataset and a putative rearrangement scenario for human, mouse and cat genomes.http://www.bibsonomy.org/bibtex/292574a7dfe4924f76351f0ac33eae32d/dzerbinodzerbino2007-09-17T20:19:41+02:00Base Chromosome Algorithms, Analysis, Contig Software, Mapping, Sequence, Mapping Sequence Data, Molecular DNA, <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 Chromosome Algorithms, Analysis, Contig Software, Mapping, Sequence, Mapping Sequence Data, Molecular DNA, 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:00Genes, Tagged melanogaster, Chromosome Algorithms, Contig Analysis, Nucleic Sites, Computational Mapping, Sequence Repetitive Molecular Chromatin, Heterochromatin, Insect, Euchromatin, Sequences, Animals, Physical Acid, Genome, Drosophila Data, DNA, Biology <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 Drosophila2872000Genes, Tagged melanogaster, Chromosome Algorithms, Contig Analysis, Nucleic Sites, Computational Mapping, Sequence Repetitive Molecular Chromatin, Heterochromatin, Insect, Euchromatin, Sequences, Animals, Physical Acid, Genome, Drosophila Data, DNA, Biology 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:00Base Profiling, Gene Consensus (Genetics), Algorithms, Alignment, Restriction Analysis, Fragmentation Sequence, DNA Variation Length, Expression Polymorphism, Sequence Genetic, Molecular Data, DNA, Fragment <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 12002Base Profiling, Gene Consensus (Genetics), Algorithms, Alignment, Restriction Analysis, Fragmentation Sequence, DNA Variation Length, Expression Polymorphism, Sequence Genetic, Molecular Data, DNA, Fragment 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:00Animals, Statistical Genome, Models, Humans, Sequence Algorithms, Genomics, DNA, Analysis, <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 sequencing682006Animals, Statistical Genome, Models, Humans, Sequence Algorithms, Genomics, DNA, Analysis, 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/21dc921e2ef4587944697d75bf48c2db4/dzerbinodzerbino2007-09-17T20:19:41+02:00Software Genome, Computational Sequence Algorithms, Genomics, DNA, Biology, Analysis, <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 Genome, Computational Sequence Algorithms, Genomics, DNA, Biology, Analysis, 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:00Systems, Base Sensitivity Management Specificity Database Databases, Algorithms, Alignment, and Composition, Software, Factual, Sequence, Sequence DNA, <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 databases112001Systems, Base Sensitivity Management Specificity Database Databases, Algorithms, Alignment, and Composition, Software, Factual, Sequence, Sequence DNA, 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:00Duplication, Genome, Gene Software, Computational Gammaproteobacteria, Sequence Bacterial Algorithms, 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 duplicates142007Duplication, Genome, Gene Software, Computational Gammaproteobacteria, Sequence Bacterial Algorithms, 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/2003fc7a74e62f697dad1196f70c46da8/dzerbinodzerbino2007-09-17T20:19:41+02:00Molecular, Folding, Models, Conformation, Chemical Algorithms, Protein <span style="color:#555555;">R <a href="http://www.bibsonomy.org/author/Agarwala">Agarwala</a> und S <a href="http://www.bibsonomy.org/author/Batzoglou">Batzoglou</a> und V <a href="http://www.bibsonomy.org/author/Danc{\&#039;\i}k">Danc'ik</a> und S E <a href="http://www.bibsonomy.org/author/Decatur">Decatur</a> und S <a href="http://www.bibsonomy.org/author/Hannenhalli">Hannenhalli</a> und M <a href="http://www.bibsonomy.org/author/Farach">Farach</a> und S <a href="http://www.bibsonomy.org/author/Muthukrishnan">Muthukrishnan</a> und S <a href="http://www.bibsonomy.org/author/Skiena">Skiena</a> </span><em>J Comput Biol</em><em>4(3):275--96</em><em>Jan1997. </em>Mon Sep 17 20:19:41 CEST 2007J Comput BiolJan3275--96Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model41997Molecular, Folding, Models, Conformation, Chemical Algorithms, Protein We consider the problem of determining the three-dimensional folding of a protein given its one-dimensional amino acid sequence. We use the HP model for protein folding proposed by Dill (1985), which models protein as a chain of amino acid residues that are either hydrophobic or polar, and hydrophobic interactions are the dominant initial driving force for the protein folding. Hart and Istrail (1996a) gave approximation algorithms for folding proteins on the cubic lattice under the HP model. In this paper, we examine the choice of a lattice by considering its algorithmic and geometric implications and argue that the triangular lattice is a more reasonable choice. We present a set of folding rules for a triangular lattice and analyze the approximation ratio they achieve. In addition, we introduce a generalization of the HP model to account for residues having different levels of hydrophobicity. After describing the biological foundation for this generalization, we show that in the new model we are able to achieve similar constant factor approximation guarantees on the triangular lattice as were achieved in the standard HP model. While the structures derived from our folding rules are probably still far from biological reality, we hope that having a set of folding rules with different properties will yield more interesting folds when combined.http://www.bibsonomy.org/bibtex/285853a4fe7db3494508d6631d10f55ca/dzerbinodzerbino2007-09-17T20:19:41+02:00meningitidis, lactis Neisseria Campylobacter Theoretical, Algorithms, Alignment, Analysis, Contig jejuni, Genome, Models, Software, Mapping, Lactococcus Sequence Bacterial, DNA, <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 assembly982001meningitidis, lactis Neisseria Campylobacter Theoretical, Algorithms, Alignment, Analysis, Contig jejuni, Genome, Models, Software, Mapping, Lactococcus Sequence Bacterial, DNA, 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.