Let $ \{ X_i \}_{i=1}^{T}$ be a path of the markov chain and let $P_{\theta}(X_1, ..., X_T)$ be the probability of observing the path when $\theta$ is the true parameter value (a.k.a. the likelihood function for $\theta$). Using the definition of conditional probability, we know
$$ P_{\theta}(X_1, ..., X_T) = P_{\theta}(X_T | X_{T-1}, ..., X_1) \cdot P_{\theta}(X_1, ..., X_{T-1})$$
Since this is a markov chain, we know that $P_{\theta}(X_T | X_{T-1}, ..., X_1) = P_{\theta}(X_T | X_{T-1} )$, so this simplifies this to
$$ P_{\theta}(X_1, ..., X_T) = P_{\theta}(X_T | X_{T-1}) \cdot P_{\theta}(X_1, ..., X_{T-1})$$
Now if you repeat this same logic $T$ times, you get
$$ P_{\theta}(X_1, ..., X_T) = \prod_{i=1}^{T} P_{\theta}(X_i | X_{i-1} ) $$
where $X_0$ is to be interpreted as the initial state of the process. The terms on the right hand side are just elements of the transition matrix. Since it was the log-likelihood you requested, the final answer is:
$$ {\bf L}(\theta) = \sum_{i=1}^{T} \log \Big( P_{\theta}(X_i | X_{i-1} ) \Big) $$
This is the likelihood of a single markov chain - if your data set includes several (independent) markov chains then the full likelihood will be a sum of terms of this form.
Just to summarize, if you substitute your 0 values with some very small value such as 1e-17, your impossible states will still be the furthers apart. As you are trying to derive some sort of ordering of your data, it doesn't matter whether your smallest value is -Inf or -39, as either number will be the smallest value in the dataset.
Best Answer
Since the two chains are assumed to be comparable, they should have the same state space. That leaves the transition matrices, comparing which can be done by a divergence-based hypothesis test, as explained on pg. 139 of Statistical inference based on divergence measures By Leandro Pardo Llorente