Author name cluster

Miika Langille

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2012 Journal Article

Simple gene assembly as a rewriting of directed overlap-inclusion graphs

Sepinoud Azimi
Tero Harju
Miika Langille
Ion Petre

The simple intramolecular model for gene assembly in ciliates consists of three molecular operations, simple ld, simple hi and simple dlad. Mathematical models in terms of signed permutations and signed strings proved limited in capturing some of the combinatorial details of the simple gene assembly process. Brijder and Hoogeboom introduced a new model in terms of overlap-inclusion graphs which could describe two of the three operations of the model and their combinatorial properties. To capture the third operation, we extended their framework to directed overlap-inclusion (DOI) graphs in Azimi et al. (2011) [1]. In this paper we introduce DOI graph-based rewriting rules that capture all three operations of the simple gene assembly model and prove that they are equivalent to the string-based formalization of the model.

Details DOI

TCS Journal 2010 Journal Article

Extended strings and graphs for simple gene assembly

Robert Brijder
Miika Langille
Ion Petre

The simple intramolecular model for gene assembly in ciliates is particularly interesting because it can predict the correct assembly of all available experimental data, although it is not universal. The simple model also has a confluence property that is not shared by the general model. A previous formalization of the simple model through sorting of signed permutations is unsatisfactory because it effectively ignores one operation of the model and thus, it cannot be used to answer questions about parallelism in the model, or about measures of complexity. We propose in this paper a string-based model in which a gene is represented through its sequence of pointers and markers and its assembly is represented as a string rewriting process. We prove that this string-based model is equivalent to the permutation-based model as far as gene assembly is concerned, while it tracks all operations of the simple model. We also consider overlap graphs for these strings and prove the results with respect to the overlap of markers.

Details DOI

TCS Journal 2008 Journal Article

Sequential vs. parallel complexity in simple gene assembly

Miika Langille
Ion Petre

We investigate some differences between the general intramolecular model for gene assembly and its restricted simple model. Although both models satisfactorily sort all current experimental data, we show that the general model offers assembly strategies for a given string that vary in both assembly length and the operations used, while the simple model will always use the same number of each type of operation to sort a gene. When simple operations are applied in parallel this is given a new twist. We prove that for any n ≥ 1, there exists a string having maximally parallel assemblies of any length between n and 2 n.

Details DOI