Wyniki wyszukiwania - BazTech

1

New models and algorithms for RNA pseudoknot order assignment

Zok Tomasz, Badura Jan, Swat Sylwester, Figurski Kacper, Popenda Mariusz, Antczak Maciej

International Journal of Applied Mathematics and Computer Science

|

2020

|

Vol. 30, no. 2

315--324

EN

The pseudoknot is a specific motif of the RNA structure that highly influences the overall shape and stability of a molecule. It occurs when nucleotides of two disjoint single-stranded fragments of the same chain, separated by a helical fragment, interact with each other and form base pairs. Pseudoknots are characterized by great topological diversity, and their systematic description is still a challenge. In our previous work, we have introduced the pseudoknot order: a new coefficient representing the topological complexity of the pseudoknotted RNA structure. It is defined as the minimum number of base pair set decompositions, aimed to obtain the unknotted RNA structure. We have suggested how it can be useful in the interpretation and understanding of a hierarchy of RNA folding. However, it is not trivial to unambiguously identify pseudoknots and determine their orders in an RNA structure. Therefore, since the introduction of this coefficient, we have worked on the method to reliably assign pseudoknot orders in correspondence to the mechanisms that control the biological process leading to their formation in the molecule. Here, we introduce a novel graph coloring-based model for the problem of pseudoknot order assignment. We show a specialized heuristic operating on the proposed model and an alternative integer programming algorithm. The performance of both approaches is compared with that of state-of-the-art algorithms which so far have been most efficient in solving the problem in question. We summarize the results of computational experiments that evaluate our new methods in terms of classification quality on a representative data set originating from the non-redundant RNA 3D structure repository.

2

A survey of graph coloring : its types, methods and applications

Formanowicz P., Tanaś K.

Foundations of Computing and Decision Sciences

|

2012

|

Vol. 37, No. 3

223--238

EN

Graph coloring is one of the best known, popular and extensively researched subject in the field of graph theory, having many applications and conjectures, which are still open and studied by various mathematicians and computer scientists along the world. In this paper we present a survey of graph coloring as an important subfield of graph theory, describing various methods of the coloring, and a list of problems and conjectures associated with them. Lastly, we turn our attention to cubic graphs, a class of graphs, which has been found to be very interesting to study and color. A brief review of graph coloring methods (in Polish) was given by Kubale and a more detailed one in a book by the same author. We extend this review and explore the field of graph coloring further, describing various results obtained by other authors and show some interesting applications of this field of graph theory.

3

Rainbow Induced Subgraphs in Proper Vertex Colorings

Kisielewicz A., Szykuła M.

Fundamenta Informaticae

|

2011

|

Vol. 111, nr 4

437-451

EN

Given a graph H we define p(H) to be the minimum order of a graph G such that every proper vertex coloring of G contains a rainbow induced subgraph isomorphic to H. We give upper and lower bounds for p(H), compute the exact value for some classes of graphs, and consider an interesting combinatorial problem connected with computation of (H) for paths. A part of this research has been guided by a computer search and, accordingly, some computational results are presented. A special motivation comes from research in on-line coloring.

4

On Efficient coloring of chordless graphs

Janczewski R., Małafiejski M.

Decision Making in Manufacturing and Services

|

2009

|

Vol. 3, no. 1-2

5-14

EN

We are given a simple graph G = (V,E). Any edge e ∈ E is a chord in a path P ⊆ G (cycle C ⊆ G) iff a graph obtained by joining e to path P (cycle C) has exactly two vertices of degree 3. A class of graphs without any chord in paths (cycles) we call pathchordless (cycle-chordless). We will prove that recognizing and coloring of these graphs can be done in O(n2) and O(n) time, respectively. Our study was motivated by a wide range of applications of the graph coloring problem in coding theory, time tabling and scheduling, frequency assignment, register allocation and many other areas.

5

Zastosowanie algorytmów rojowych do kolorowania grafów

Obszarski P., Piwakowski K.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2006

|

z. 143

107-113

PL

Przedstawiamy sposób adaptacji heurystycznej metody przeszukiwania PSO (ang. Particle Swarm Optimization) do znajdowania suboptymalnych pokolorowań wierzchołkowych grafów prostych. Prezentujemy sposób przeprowadzenia eksperymentów obliczeniowych oraz ich wyniki.

EN

Adaptation of the Particle Swarm Optimization method for obtaining suboptimal vertex colorings of graphs is proposed. We present details of performed computational experiments and their results.

6

Kolorowanie hipergrafów

Kubale M., Obszarski P., Piwakowski K.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2006

|

z. 143

83-90

PL

Hipergraf to struktura stanowiąca pewne uogólnienie grafa. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności, złożoności oraz wskażemy zastosowania.

EN

A hypergraph is a generalization of a graph in which the edges may contain any number of vertices. In this paper we discuss a few models of hypergraph coloring, namely: edge coloring, vertex coloring and mixed coloring. We present some basic properties of these models, complexity and their possible applications.

7

A survey of hard-to-color graphs for off-line and on-line model of vertex coloring

Borowiecki P., Kubale M.

Journal of Applied Computer Science

|

2001

|

Vol. 9, nr 2

7-17

EN

In the paper we review the most popular on-line and off-line graph coloring algorithms. For each algorithm we give: short description. performance guarantee, the smallest HC and slightly HC graphs, positive cases and negative cases. Finally, we give the smallest benchmark for off-line sequential algorithms and the smallest weak benchmark for on-line algorithms.