Bernhard Haubold

Bernhard Haubold


Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
10 February 2010 in Molecular Ecology
Verified
Journal Article
Open access
PDF file
BHBernhard Haubold
Bernhard Haubold
PPPeter Pfaffelhuber
Peter Pfaffelhuber
MLMichael Lynch
Michael Lynch
Improvements in sequencing technology over the past 5 years are leading to routine application of shotgun sequencing in the fields of ecology and evolution. However, the theory to estimate evolutionary parameters from these data is still being worked out. Here we present an extension and implementation of part of this theory, mlRho. This program can efficiently compute the following three maximum likelihood estimators based on shotgun sequence data obtained from single diploid individuals: the population mutation rate (4Neμ), the sequencing error rate, and the population recombination rate (4Nec). We demonstrate the accuracy of mlRho by applying it to simulated data sets. In addition, we analyse the genomes of the sea squirt Ciona intestinalis and the water flea Daphnia pulex. Ciona intestinalis is an obligate outcrosser, while D. pulex is a cyclic parthenogen, and we discuss how these contrasting life histories are reflected in our parameter estimates. The program mlRho is freely available from http://guanine.evolbio.mpg.de/mlRho.

10 December 2014 in Bioinformatics
Verified
Journal Article
Open access
PDF file
BHBernhard Haubold
Bernhard Haubold
FKFabian Klötzl
Fabian Klötzl
PPPeter Pfaffelhuber
Peter Pfaffelhuber
Motivation: A standard approach to classifying sets of genomes is to calculate their pairwise distances. This is difficult for large samples. We have therefore developed an algorithm for rapidly computing the evolutionary distances between closely related genomes. Results: Our distance measure is based on ungapped local alignments that we anchor through pairs of maximal unique matches of a minimum length. These exact matches can be looked up efficiently using enhanced suffix arrays and our implementation requires approximately only 1 s and 45 MB RAM/Mbase analysed. The pairing of matches distinguishes non-homologous from homologous regions leading to accurate distance estimation. We show this by analysing simulated data and genome samples ranging from 29 Escherichia coli/Shigella genomes to 3085 genomes of Streptococcus pneumoniae. Availability and implementation: We have implemented the computation of anchor distances in the multithreaded UNIX command-line program andi for ANchor DIstances. C sources and documentation are posted at http://github.com/evolbioinf/andi/ Contact:haubold@evolbio.mpg.de Supplementary information: Supplementary data are available at Bioinformatics online.

29 November 2013 in Briefings in Bioinformatics
Verified
Journal Article
Open access
PDF file
BHBernhard Haubold
Bernhard Haubold
Phylogenetics and population genetics are central disciplines in evolutionary biology. Both are based on comparative data, today usually DNA sequences. These have become so plentiful that alignment-free sequence comparison is of growing importance in the race between scientists and sequencing machines. In phylogenetics, efficient distance computation is the major contribution of alignment-free methods. A distance measure should reflect the number of substitutions per site, which underlies classical alignment-based phylogeny reconstruction. Alignment-free distance measures are either based on word counts or on match lengths, and I apply examples of both approaches to simulated and real data to assess their accuracy and efficiency. While phylogeny reconstruction is based on the number of substitutions, in population genetics, the distribution of mutations along a sequence is also considered. This distribution can be explored by match lengths, thus opening the prospect of alignment-free population genomics.

1 October 2009 in Journal of Computational Biology
Verified
Journal Article
Closed access
BHBernhard Haubold
Bernhard Haubold
PPPeter Pfaffelhuber
Peter Pfaffelhuber
MDMirjana Domazet-Los˘o
Mirjana Domazet-Los˘o
TWThomas Wiehe
Thomas Wiehe
Alignment-free distance measures are generally less accurate but more efficient than traditional alignment-based metrics. In the context of genome sequence analysis, the efficiency gain is often so substantial that it outweights the loss in accuracy. However, a further disadvantage of alignment-free distances is that their relationship to evolutionary events such as substitutions is generally unknown. We have therefore derived an estimator of the number of substitutions per site between two unaligned DNA sequences, Kr. Simulations show that this estimator works well with “ideal” data. We compare Kr to two alternative alignment-free distances: a k-tuple distance and a measure of relative entropy based on average common substring length. All three measures are applied to 27 primate mitochondrial genomes, eight whole genomes of Streptococcus agalactiae strains, and 12 whole genomes of Drosophila species. In each case, the cluster diagrams based on Kr are equivalent to or significantly better than those based on the two alternative measures. This is due to the fact that in contrast to the alternative measures Kr is derived from an explicit model of evolution. The computation of Kr is efficiently implemented in the program kr, which can be downloaded freely from the internet.

6 April 2011 in Bioinformatics
Verified
Journal Article
Open access
PDF file
MDMirjana Domazet-Lošo
Mirjana Domazet-Lošo
BHBernhard Haubold
Bernhard Haubold
Motivation: Bacterial and viral genomes are often affected by horizontal gene transfer observable as abrupt switching in local homology. In addition to the resulting mosaic genome structure, they frequently contain regions not found in close relatives, which may play a role in virulence mechanisms. Due to this connection to medical microbiology, there are numerous methods available to detect horizontal gene transfer. However, these are usually aimed at individual genes and viral genomes rather than the much larger bacterial genomes. Here, we propose an efficient alignment-free approach to describe the mosaic structure of viral and bacterial genomes, including their unique regions. Results: Our method is based on the lengths of exact matches between pairs of sequences. Long matches indicate close homology, short matches more distant homology or none at all. These exact match lengths can be looked up efficiently using an enhanced suffix array. Our program implementing this approach, alfy (ALignment-Free local homologY), efficiently and accurately detects the recombination break points in simulated DNA sequences and among recombinant HIV-1 strains. We also apply alfy to Escherichia coli genomes where we detect new evidence for the hypothesis that strains pathogenic in poultry can infect humans. Availability: alfy is written in standard C and its source code is available under the GNU General Public License from http://guanine.evolbio.mpg.de/alfy/. The software package also includes documentation and example data. Contact:haubold@evolbio.mpg.de Supplementary information: Supplementary data are available at Bioinformatics online.

13 October 2009 in Bioinformatics
Verified
Journal Article
Open access
PDF file
MDMirjana Domazet-Lošo
Mirjana Domazet-Lošo
BHBernhard Haubold
Bernhard Haubold
Motivation: Genome comparison is central to contemporary genomics and typically relies on sequence alignment. However, genome-wide alignments are difficult to compute. We have, therefore, recently developed an accurate alignment-free estimator of the number of substitutions per site based on the lengths of exact matches between pairs of sequences. The previous implementation of this measure requires n(n−1) suffix tree constructions and traversals, where n is the number of sequences analyzed. This does not scale well for large n. Results: We present an algorithm to extract pairwise distances in a single traversal of a single suffix tree containing n sequences. As a result, the run time of the suffix tree construction phase of our algorithm is reduced from O(n2L) to O(nL), where L is the length of each sequence. We implement this algorithm in the program kr version 2 and apply it to 825 HIV genomes, 13 genomes of enterobacteria and the complete genomes of 12 Drosophila species. We show that, depending on the input dataset, the new program is at least 10 times faster than its predecessor. Availability: Version 2 of kr can be tested via a web interface at http://guanine.evolbio.mpg.de/kr2/. It is written in standard C and its source code is available under the GNU General Public License from the same web site. Contact:haubold@evolbio.mpg.de Supplementary informations: Supplementary data are available at Bioinformatics online.