Solving the String Statistics Problem (2002)
Gerth Stlting Brodal, Rune B. Lyngs, Anna Ostlin, Christian N. S. Pedersen
The string statistics problem consists of preprocessing a string of length n such that given a query pattern of length m, the maximum number of non-overlapping occurrences of the query pattern in the...
During four years of arduous service, a Ph. D. student is expected to familiarise himself with his field of research, and, hopefully, contribute to this field. This is reflected by the division of...
Complexity of Comparing Hidden Markov Models (2001)
Rune B. Lyngs, Christian N. S. Pedersen
The basic theory of hidden Markov models was developed and applied to problems in speech recognition in the late 1960's, and has since then been applied to numerous problems, e.g. biological sequence...
Comparing an HMM and an SCFG (2001)
Arun Jagota, Rune B. Lyngs, Christian N. S. Pedersen
Stochastic models are commonly used in bioinformatics, e.g. hidden Markov models for modeling sequence families or stochastic...
Comparing an HMM and an SCFG (2001)
Arun Jagota, Rune B. Lyngs, Christian N. S. Pedersen
Stochastic models are commonly used in bioinformatics, e.g. hidden Markov models for modeling sequence families or stochastic context-free grammars for modeling RNA secondary structure formation....
Comparing Stochastic Models (2001)
Arun Jagota, Rune B. Lyngs, Christian N. S. Pedersen
Stochastic models are commonly used in bioinformatics, e.g. hidden Markov models for modeling sequence families or stochastic context -free grammars for modeling RNA secondary structure formation....
Complexity of Comparing Hidden Markov Models (2001)
Rune B. Lyngs, Christian N. S. Pedersen
The basic theory of hidden Markov models was developed and applied to problems in speech recognition in the late 1960's, and has since then been applied to numerous problems, e.g. biological sequence...
Protein folding in the 2D HP model (2000)
Rune B. Lyngs, Christian N. S. Pedersen
We study folding algorithms in the two dimensional Hydrophobic-Hydrophilic model for protein structure formation. We consider three generalizations of the best known approximation algorithm. We show...
Pseudoknots in RNA Secondary Structures (2000)
Rune B. Lyngs, Christian N. S. Pedersen
RNA molecules are sequences of nucleotides that serve as more than mere intermediaries between DNA and proteins, e.g. as catalytic molecules. Computational prediction of RNA secondary structure is...
Pseudoknots in RNA Secondary Structures (1999)
Rune B. Lyngs, Christian N. S. Pedersen
RNA molecules are sequences of nucleotides that serve as more than mere intermediaries between DNA and proteins, e.g. as catalytic molecules. Computational prediction of RNA secondary structure is...
Finding Maximal Pairs with Bounded Gap (1999)
Gerth Stlting Brodal, Rune B. Lyngs, Copyright C, Gerth Stlting, Brodal Rune, B. Lyngs, ...
A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them different. The...
Finding Maximal Pairs with Bounded Gap (1999)
Gerth Stlting Brodal, Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye
A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...
Protein folding in the 2D HP model (1999)
Rune B. Lyngs, Christian N. S. Pedersen
We study folding algorithms in the two dimensional Hydrophobic-Hydrophilic model (2D HP model) for protein structure formation. We consider three generalizations of the best known approximation...
An Improved Algorithm for RNA Secondary Structure Prediction (1999)
Rune B. Lyngs, Christian N. S. Pedersen
Though not as abundant in known biological processes as proteins, RNA molecules serve as more than mere intermediaries between DNA and proteins, e.g. as catalytic molecules. Furthermore, RNA...
Protein Folding in the 2D HP Model (1999)
We study folding algorithms in the two dimensional HydrophobicHydrophilic model (2D HP model) for protein structure formation. We consider three generalizations of the best known approximation...
Measures on Hidden Markov Models (1999)
Hidden Markov models were introduced in the beginning of the 1970's as a tool in speech recognition. During the last decade they have been found useful in addressing problems in computational biology...
Finding Maximal Pairs With Bounded Gap (1999)
Gerth Stlting Brodal, Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye
A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...
Protein folding in the 2D HP model (1999)
Rune B. Lyngs, Christian N. S. Pedersen
We study folding algorithms in the two dimensional HydrophobicHydrophilic model (2D HP model) for protein structure formation. We consider three generalizations of the best known approximation...
Protein folding in the 2D HP model (1999)
Rune B. Lyngs, Christian N. S. Pedersen
We study folding algorithms in the two dimensional HydrophobicHydrophilic model (2D HP model) for protein structure formation. We consider three generalizations of the best known approximation...
Measures on Hidden Markov Models (1999)
Rune B. Lyngs, Christian N. S. Pedersen, Henrik Nielsen
Hidden Markov models were introduced in the beginning of the 1970's as a tool in speech recognition. During the last decade they have been found useful in addressing problems in computational biology...
Finding Maximal Pairs With Bounded Gap (1999)
Gerth Stlting Brodal, Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye
A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...
Finding Maximal Pairs with Bounded Gap (1999)
Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye
A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them different. The...
Finding Maximal Pairs With Bounded Gap (1999)
Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye
. A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...
Measures on hidden Markov models (1999)
Rune B. Lyngs, Christian N. S. Pedersen, Henrik Nielsen
Hidden Markov models were introduced in the beginning of the 1970's as a tool in speech recognition. During the last decade they have been found useful in addressing problems in computational biology...
Internal loops in RNA secondary structure prediction (1999)
Rune B. Lyngs, Michael Zuker, Christian N. S. Pedersen
We present an analysis of currently used free energy functions for internal loop stability in RNA secondary structure. This analysis enables us to present an O(|s|³) algorithm for evaluating...
Finding Maximal Pairs With Bounded Gap (1999)
Rune B. Lyngs, Christian N. S. Pedersen, Jens Stoye
. A pair in a string is the occurrence of the same substring twice. A pair is maximal if the two occurrences of the substring cannot be extended to the left and right without making them dierent. The...
Prediction of Protein Structures Using Simple Exact Models (1999)
Christian N. Storm P, Rune B. Lyngs
this paper so as not to obfuscate the meaning with minor details.
Comparison of Coding DNA (1999)
Christian N. S. Pedersen, Rune B. Lyngs, Jotun Hein
We discuss a model for the evolutionary distance between two coding DNA sequences which specializes to the DNA/protein model proposed in Hein [3]. We discuss the DNA/protein model in details and...
Internal loops in RNA secondary structure prediction (1999)
Rune B. Lyngs, Michael Zuker, Christian N. S. Pedersen
We present an analysis of currently used free energy functions for internal loop stability in RNA secondary structure. This analysis enables us to present an O(jsj 3 ) algorithm for evaluating...
The Polygamic Marriage Problem (1998)
Peer Berg, Bernt Guldbr, Rune B. Lyngs, Christian N. Storm P
this paper we consider matchings of a certain kind, namely matchings where each male is paired with at least m and at most n females and each female is paired with at most one male. Denote these...
Computational Aspects of Biological Sequences and Structures (1997)
This report is subdivided in three main parts corresponding to the structural hierarchy of biological molecules. Each part starts with a survey of what I consider the key problems and results of the...
Prediction of Protein Structures Using (1996)
Christian N. Storm P, Rune B. Lyngs
this paper so as not to obfuscate the meaning with minor details
Pseudoknots in RNA Secondary Structures (1970)
Rune B. Lyngs, Christian N. S. Pedersen
RNA molecules are sequences of nucleotides that serve as more than mere intermediaries between DNA and proteins, e.g. as catalytic molecules. Computational prediction of RNA secondary structure is...