A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks Algoritmos exatos para encontrar um corte mínimo de reação sob um modelo booleano de redes metabólicas

Takeyuki TAMURA, Tatsuya AKUTSU

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Um corte de reação é um conjunto de reações químicas cuja exclusão bloqueia a operação de determinadas reações ou a produção de determinados compostos químicos. Neste artigo, estudamos dois problemas ReactionCut e MD-ReactionCut para cálculo do corte mínimo de reação de uma rede metabólica sob um modelo booleano. Esses problemas são baseados no modelo de equilíbrio de fluxo e no modelo de dano mínimo, respectivamente. Mostramos que ReactionCut e MD-ReactionCut são NP-difíceis mesmo se o grau máximo de nós de reação (KFora) é um. Apresentamos também O(1.822n), O(1.959n) e o(2n) algoritmos de tempo para MD-ReactionCut com KFora=2, 3, k respectivamente onde n é o número de nós de reação e k é uma constante. Os mesmos algoritmos também funcionam para ReactionCut se não houver ciclo direcionado. Além disso, apresentamos um 2O((registro n)) algoritmo de tempo, que é mais rápido que O((1+ε)n) para qualquer constante positiva ε, para o caso planar de MD-ReactionCut sob uma restrição razoável utilizando o algoritmo separador de Lipton e Tarjan.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.8 pp.1497-1507
Data de publicação
2010/08/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.E93.A.1497
Tipo de Manuscrito
PAPER
Categoria
Algoritmos e estruturas de dados

autores

Palavra-chave