Algorithms in Computational Biology - BRICS Dissertation Series DS-00-4 - Ph.D. Dissertation Abstract

Sep 21, 2026

This Ph.D. dissertation focuses on constructing and analyzing algorithms for biological problems within computational biology and bioinformatics. It addresses how DNA, RNA, and proteins can be modeled as strings over finite alphabets, enabling string algorithms to compare and analyze biological data. The work studies sequence comparison with protein-aware scoring, improving alignment efficiency by a quadratic factor. It also develops measures and dynamic-programming methods for comparing hidden Markov models and deriving compact representations of sequence families.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages225

Reading Time9 h 27 min

AccessFree to download

Abstract

Biological problems in computational biology

String representation and algorithmic techniques

Sequence comparison and alignment model

Comparing hidden Markov models for sequence families

Finding regularities in a single biological sequence

Maximal equal substrings and tandem repeat generalization

Maximal quasiperiodic substrings and performance improvement

BRICS DS-00-4 C. N. S. Pedersen: Algorithms in Computational Biology BRICS Basic Research in Computer Science Algorithms in Computational Biology Christian N. S. Pedersen BRICS Dissertation Series DS-00-4 ISSN 1396-7002 March 2000 Copyright 􀀍c 2000, Christian N. S. Pedersen. BRICS, Department of Computer Science University of Aarhus. All rights reserved. Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS Dissertation Series publications. Copies may be obtained by contacting: BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark Telephone: +45 8942 3360 Telefax: +45 8942 3255 Internet: [BRICS@brics.dk](BRICS@brics.dk) BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs: [http://www.brics.dk](http://www.brics.dk) [ftp://ftp.brics.dk](ftp://ftp.brics.dk) This document in subdirectory DS/00/4/ Algorithms in Computational Biology Christian N􀀜rgaard Storm Pedersen Ph. D. Dissertation Department of Computer Science University of Aarhus Denmark Algorithms in Computational Biology A Dissertation Presented to the Faculty of Science of the University of Aarhus in Partial Ful􀀌llment of the Requirements for the Ph.D. Degree by Christian N􀀜rgaard Storm Pedersen August 31, 1999 Abstract In this thesis we are concerned with constructing algorithms that address problems of biological relevance. This activity is part of a broader interdisciplinary area called computational biology, or bioinformatics, that focuses on utilizing the capacities of computers to gain knowledge from biological data. The majority of problems in computational biology relate to molecular or evolutionary biology, and focus on analyzing and comparing the genetic material of organisms. One deciding factor in shaping the area of computational biology is that DNA, RNA and proteins that are responsible for storing and utilizing the genetic material in an organism, can be described as strings over 􀀌nite alphabets. The string representation of biomolecules allows for a wide range of algorithmic techniques concerned with strings to be applied for analyzing and comparing biological data. We contribute to the 􀀌eld of computational biology by constructing and analyzing algorithms that address problems of relevance to biological sequence analysis and structure prediction. The genetic material of organisms evolves by discrete mutations, most prominently substitutions, insertions and deletions of nucleotides. Since the genetic material is stored in DNA sequences and re􀀍ected in RNA and protein sequences, it makes sense to compare two or more biological sequences to look for similarities and di􀀋erences that can be used to infer the relatedness of the sequences. In the thesis we consider the problem of comparing two sequences of coding DNA when the relationship between DNA and proteins is taken into account. We do this by using a model that penalizes an event on the DNA by the change it induces on the encoded protein. We analyze the model in detail, and construct an alignment algorithm that improves on the existing best alignment algorithm in the model by reducing its running time by a quadratic factor. This makes the running time of our alignment algorithm equal to the running time of alignment algorithms based on much simpler models. If a family of related biological sequences is available, it is natural to derive a compact characterization of the sequence family. Among other things, such a characterization can be used to search for unknown members of the sequence family. One widely used way to describe the characteristics of a sequence family is to construct a hidden Markov model that generates members of the sequence family with high probability and non-member

FAQs

What is the dissertation’s main focus?

The dissertation focuses on designing and analyzing algorithms for problems relevant to biological sequence analysis and structure prediction within computational biology.

How does the thesis model biomolecules for algorithmic work?

It treats DNA, RNA, and proteins as strings over finite alphabets, which allows applying string-based algorithmic techniques to biological data.

What alignment problem does the thesis address and what improvement is reported?

It compares coding DNA sequences while accounting for the relationship between DNA and proteins, using a model that penalizes DNA events by their induced protein changes, and it builds an alignment algorithm that reduces running time by a quadratic factor.

Sep 21, 2026

Uploaded by Emma Wilson