On the scalability of biocomputing algorithms: The case of the maximum clique problem
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F11%3A%230003708" target="_blank" >RIV/47813059:19240/11:#0003708 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1016/j.tcs.2011.09.004" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2011.09.004</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2011.09.004" target="_blank" >10.1016/j.tcs.2011.09.004</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On the scalability of biocomputing algorithms: The case of the maximum clique problem
Popis výsledku v původním jazyce
The paper aims at demonstrating and confirming that breadth first search or pruning techniques can substantially improve the effectiveness of biomolecular algorithms. A breadth first search-based DNA algorithm solving the maximum clique problem for a graph is presented, and its complexity and scalability parameters are studied. The analysis shows that parameters like the number of steps, the length and volume of DNA strands, the number of enzymes and the concentration of the molecules encoding solutionsare dramatically improved in comparison with previous approaches to the same problem and, theoretically, they would allow to process graphs with thousands of vertices.
Název v anglickém jazyce
On the scalability of biocomputing algorithms: The case of the maximum clique problem
Popis výsledku anglicky
The paper aims at demonstrating and confirming that breadth first search or pruning techniques can substantially improve the effectiveness of biomolecular algorithms. A breadth first search-based DNA algorithm solving the maximum clique problem for a graph is presented, and its complexity and scalability parameters are studied. The analysis shows that parameters like the number of steps, the length and volume of DNA strands, the number of enzymes and the concentration of the molecules encoding solutionsare dramatically improved in comparison with previous approaches to the same problem and, theoretically, they would allow to process graphs with thousands of vertices.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
O - Projekt operacniho programu
Ostatní
Rok uplatnění
2011
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
THEORETICAL COMPUTER SCIENCE
ISSN
0304-3975
e-ISSN
—
Svazek periodika
412
Číslo periodika v rámci svazku
51
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
12
Strana od-do
7075-7086
Kód UT WoS článku
000297777900003
EID výsledku v databázi Scopus
—