Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Complexity Measures for Gene A...

Complexity Measures for Gene Assembly

Tero Harju, Chang Li, Ion Petre, Grzegorz Rozenberg, Complexity Measures for Gene Assembly. In: Proceedings of the Knowledge Discovery and Emergent Complexity in Bioninformatics workshop, Lecture Notes in Bioinformatics 4366, 42-60, 2007.

Abstract:

The process of gene assembly in ciliates is a fascinating example of programmed DNA manipulations in living cells. Macronuclear genes are split into coding blocks (called MDSs), shuffled and separated by non-coding sequences to form micronuclear genes. Assembling the coding blocks from micronuclear genes to form functional macronuclear genes is facilitated by an impressive in-vivo implementation of the linked list data structure of computer science. Complexity measures for genes may be defined in many ways, including the number of MDSs, the number of loci, etc. We take a different approach in this paper and propose four complexity measures for genes in ciliates, based on the `effort\' required to assemble the gene. We consider: (a) the types of operations used in the assembly, (b) the number of operations used in the assembly, (c) the length of the molecular folds involved, and (d) the length of the shortest possible parallel assembly for that gene.

BibTeX entry:

@INPROCEEDINGS{inpHaLiPeRo07a,
  title = {Complexity Measures for Gene Assembly},
  booktitle = {Proceedings of the Knowledge Discovery and Emergent Complexity in Bioninformatics workshop},
  author = {Harju, Tero and Li, Chang and Petre, Ion and Rozenberg, Grzegorz},
  volume = {4366},
  series = {Lecture Notes in Bioinformatics},
  pages = {42-60},
  year = {2007},
  keywords = {Gene assembly, Complexity measures},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics, Computational Biomodeling Laboratory (Combio Lab)

Edit publication