Biomedical subjects

Katharina A Lehmann

Publications and source records attributed to Katharina A Lehmann.

3 recordsLinked to original sources

PubMed2006

On the maximal cliques in c-max-tolerance graphs and their application in clustering molecular sequences.

Given a set S of n locally aligned sequences, it is a needed prerequisite to partition it into groups of very similar sequences to facilitate subsequent computations, such as the generation of a phylogenetic tree. This article introduces a new method of clustering which partitions S into subsets such that the overlap of each pair of sequences within a subset is at least a given percentage c of the lengths of the two sequences. We show that this problem can be reduced to finding all maximal cliques in a special kind of max-tolerance graph which we call a c-max-tolerance graph. Previously we have shown that finding all maximal cliques in general max-tolerance graphs can be done efficiently in O(n3 + out). Here, using a new kind of sweep-line algorithm, we show that the restriction to c-max-tolerance graphs yields a better runtime of O(n2 log n + out). Furthermore, we present another algorithm which is much easier to implement, and though theoretically slower than the first one, is still running in polynomial time. We then experimentally analyze the number and structure of all maximal cliques in a c-max-tolerance graph, depending on the chosen c-value. We apply our simple algorithm to artificial and biological data and we show that this implementation is much faster than the well-known application Cliquer. By introducing a new heuristic that uses the set of all maximal cliques to partition S, we finally show that the computed partition gives a reasonable clustering for biological data sets.

Journal Article↗

PubMed2006

Hybrid graphs as a framework for the small-world effect.

In this paper we formalize the small-world effect which describes the surprising fact that a hybrid graph composed of a local graph component and a very sparse random graph has a diameter of O(ln n) whereby the diameter of both components alone is much higher. We show that a large family of these hybrid graphs shows this effect and that this generalized family also includes classic small-world models proposed by various authors although not all of them are captured by the small-world definition given by Watts and Strogatz. Furthermore, we give a detailed upper bound of the hybrid's graph diameter for different choices of the expected number of random edges by applying a new kind of proof pattern that is applicable to a large number of hybrid graphs. The focus in this paper is on presenting a flexible family of hybrid graphs showing the small-world effect that can be tuned closely to real-world systems.

Journal Article↗

PubMed2004

Chronological aging leads to apoptosis in yeast.

During the past years, yeast has been successfully established as a model to study mechanisms of apoptotic regulation. However, the beneficial effects of such a cell suicide program for a unicellular organism remained obscure. Here, we demonstrate that chronologically aged yeast cultures die exhibiting typical markers of apoptosis, accumulate oxygen radicals, and show caspase activation. Age-induced cell death is strongly delayed by overexpressing YAP1, a key transcriptional regulator in oxygen stress response. Disruption of apoptosis through deletion of yeast caspase YCA1 initially results in better survival of aged cultures. However, surviving cells lose the ability of regrowth, indicating that predamaged cells accumulate in the absence of apoptotic cell removal. Moreover, wild-type cells outlast yca1 disruptants in direct competition assays during long-term aging. We suggest that apoptosis in yeast confers a selective advantage for this unicellular organism, and demonstrate that old yeast cells release substances into the medium that stimulate survival of the clone.

Aging↗