Markov chains: Computing limit existence and approximations with DNA.
Biosystems 2005;
81:261-6. [PMID:
15982800 DOI:
10.1016/j.biosystems.2005.05.003]
[Citation(s) in RCA: 8] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/17/2004] [Revised: 05/10/2005] [Accepted: 05/10/2005] [Indexed: 11/25/2022]
Abstract
We present two algorithms to perform computations over Markov chains. The first one determines whether the sequence of powers of the transition matrix of a Markov chain converges or not to a limit matrix. If it does converge, the second algorithm enables us to estimate this limit. The combination of these algorithms allows the computation of a limit using DNA computing. In this sense, we have encoded the states and the transition probabilities using strands of DNA for generating paths of the Markov chain.
Collapse