http://www.bibsonomy.org/burst/user/dzerbino/Analysis,BibSonomy BuRST Feed for /user/dzerbino/Analysis,2008-10-07T19:32:38+02:00http://www.bibsonomy.org/bibtex/2aa8bc1f2986f316dcdd470da0aa1588d/dzerbinodzerbino2007-09-17T20:19:41+02:00Profiling, Analysis, Sequence DNA, Humans, Gene Algorithms, Alignment, Software, Consensus 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 graphs192003Profiling, Analysis, Sequence DNA, Humans, Gene Algorithms, Alignment, Software, Consensus 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/2150cd10c40aace2c238aaa20c8480e08/dzerbinodzerbino2007-09-17T20:19:41+02:00Algorithms, Mapping, Base Sequence, Data, DNA, Chromosome Interface Software, Sequence User-Computer Software Molecular Alignment, Analysis, Design, <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, Mapping, Base Sequence, Data, DNA, Chromosome Interface Software, Sequence User-Computer Software Molecular Alignment, Analysis, Design, 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/24296f5595607517ac76189523adbafdb/dzerbinodzerbino2007-09-17T20:19:41+02:00Algorithms, Alignment, Databases, Analysis, Genetic, Sequence Protein, Amino Software, Acid Homology, <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 elements142004Algorithms, Alignment, Databases, Analysis, Genetic, Sequence Protein, Amino Software, Acid Homology, 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/251d90db8174d7d1da830b654951e5ea0/dzerbinodzerbino2007-09-17T20:19:41+02:00Cluster (Genetics), Bacterial, Biology, Computational Multigene Sequences, Mapping, Acid, Artificial, Human, Repetitive Family Sequence Analysis, Linkage Alignment, Contig Nucleic Genome, Chromosomes, Humans, Algorithms, <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 assembly142004Cluster (Genetics), Bacterial, Biology, Computational Multigene Sequences, Mapping, Acid, Artificial, Human, Repetitive Family Sequence Analysis, Linkage Alignment, Contig Nucleic Genome, Chromosomes, Humans, Algorithms, 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/2187f0308ae9e5fa2f47476b9ab180a20/dzerbinodzerbino2007-09-17T20:19:41+02:00Data, Feasibility Sequence Studies, Algorithms, DNA, Profiling, Contig Analysis, Expression Molecular Mapping, Gene Base Alignment, <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 reads202004Data, Feasibility Sequence Studies, Algorithms, DNA, Profiling, Contig Analysis, Expression Molecular Mapping, Gene Base Alignment, 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:00Data, Base Mapping Chromosome Algorithms, Sequence Molecular Fragmentation, Analysis, Sequence, DNA, 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 22005Data, Base Mapping Chromosome Algorithms, Sequence Molecular Fragmentation, Analysis, Sequence, DNA, 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:00Molecular, Fibrosis Evolution, Phylogeny, Genetic Simulation, Animals, Functions, Base Variation Cystic Sequence, (Genetics), Alignment, Regulator, Conductance Analysis, Genome, Models, Data, Mammals, Molecular Sequence Transmembrane DNA, Likelihood Computer <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 silico142004Molecular, Fibrosis Evolution, Phylogeny, Genetic Simulation, Animals, Functions, Base Variation Cystic Sequence, (Genetics), Alignment, Regulator, Conductance Analysis, Genome, Models, Data, Mammals, Molecular Sequence Transmembrane DNA, Likelihood Computer 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/292574a7dfe4924f76351f0ac33eae32d/dzerbinodzerbino2007-09-17T20:19:41+02:00DNA, Sequence Algorithms, Molecular Data, Software, Mapping Base Mapping, Chromosome Sequence, Contig Analysis, <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 SSAKE232007DNA, Sequence Algorithms, Molecular Data, Software, Mapping Base Mapping, Chromosome Sequence, Contig Analysis, 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:00Computational Biology Drosophila Insect, Chromosome Genes, Genome, Data, Physical Sites, Chromatin, Sequence Acid, Animals, Contig Analysis, Sequences, Algorithms, Nucleic Molecular Repetitive DNA, Heterochromatin, Euchromatin, Tagged Mapping, melanogaster, <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 Drosophila2872000Computational Biology Drosophila Insect, Chromosome Genes, Genome, Data, Physical Sites, Chromatin, Sequence Acid, Animals, Contig Analysis, Sequences, Algorithms, Nucleic Molecular Repetitive DNA, Heterochromatin, Euchromatin, Tagged Mapping, melanogaster, 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:00Restriction Fragmentation Polymorphism, Gene DNA Consensus Alignment, Variation Sequence DNA, Profiling, Base Fragment Expression Analysis, Molecular Genetic, Sequence, Data, Length, (Genetics), Algorithms, <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 12002Restriction Fragmentation Polymorphism, Gene DNA Consensus Alignment, Variation Sequence DNA, Profiling, Base Fragment Expression Analysis, Molecular Genetic, Sequence, Data, Length, (Genetics), Algorithms, 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:00Analysis, Sequence DNA, Models, Animals, Genome, Statistical Humans, Algorithms, Genomics, <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 sequencing682006Analysis, Sequence DNA, Models, Animals, Genome, Statistical Humans, Algorithms, Genomics, 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:00Sequence Genomics, Genome, Studies, Chromosomes, Human, Pair 1, Feasibility DNA, Humans, Viral, Analysis, 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 sequencing332005Sequence Genomics, Genome, Studies, Chromosomes, Human, Pair 1, Feasibility DNA, Humans, Viral, Analysis, 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:00Sequence Algorithms, Biology, Computational Software Genomics, Analysis, Genome, DNA, <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 distances142007Sequence Algorithms, Biology, Computational Software Genomics, Analysis, Genome, DNA, 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/2e05ca61552c8d9f5951978da7619860d/dzerbinodzerbino2007-09-17T20:19:41+02:00Analysis, DNA, Biology, Sequence Gene Genome, Gammaproteobacteria, Duplication, Computational Bacterial Algorithms, Software, <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 duplicates142007Analysis, DNA, Biology, Sequence Gene Genome, Gammaproteobacteria, Duplication, Computational Bacterial Algorithms, Software, 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:00Analysis, Genome, Alignment, Software, Theoretical, lactis Campylobacter jejuni, meningitidis, Neisseria Algorithms, DNA, Sequence Contig Bacterial, Lactococcus Mapping, Models, <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 assembly982001Analysis, Genome, Alignment, Software, Theoretical, lactis Campylobacter jejuni, meningitidis, Neisseria Algorithms, DNA, Sequence Contig Bacterial, Lactococcus Mapping, Models, 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:00Regulation, Homology Chains, Software, Profiling, Alignment, Molecular, Gene Statistical, DNA, Markov Expression Sequence Protein, Genetic, Analysis, Models, Evolution, Cluster Algorithms, <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 12003Regulation, Homology Chains, Software, Profiling, Alignment, Molecular, Gene Statistical, DNA, Markov Expression Sequence Protein, Genetic, Analysis, Models, Evolution, Cluster Algorithms, 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.