The embedding problem for Markov matrices

Abstract

The goal of this thesis is to solve the embedding problem for Markov matrices, posed by Gustav Elfving in1937. A Markov matrix is non-negative square matrix whose rows sum to 1. We say that such a matrix M is embeddable if it can be written as the exponential of a rate matrix, that is a real square matrix with rows summing to zero and non-negative off-diagonal entries. In this case, we say that the rate matrix is a Markov generator for M. The embedding problem consists deciding whether a given Markov matrix is embeddable or not, thus solving the embedding problem results in giving a characterization of embeddablem matrices. This problem is motivated by Markov processes, which are used to model the change of state of a random variable over time. under the assumption that future is independent from past given the present, that is, the assumption that the substitution probabilities do not depend on previous changes of state. In this framework, the entries of Markov matrices represent the substitution probabilities along a fixed time interval. When these probabilities ar considered to be continuous (and differentiable) functions depending on time, the Markov process is ruled by the instantaneous rates of substitution between states. In order to keep continuous-time Markov processes tractable, the substitution rates are usually assumed to be constant over time. In this case, we say that the process is a homogeneous continuous-time process and one displays all the rates together in a matrix called rate matrix Q. Moreover, the Markov matrix encoding the substitution probabilities after time t can be written as M(t) = exp(Qt) for all t=0. Thus, M(t) is embeddable and Qt is a Markov generator for it. Therefore, in the context of substitution processes, the embedding problem consists on deciding whether a given transicion matrix can be obtained from a homogeneous Markov process in continuous-time. The embedding problem is solved for 2x2 and 3x3 Markov matrices and also for some particular cases such as matrices close to the identity or matrices with dferent real eigenvaleus. In this thesis we present a method to decide wheter a Markov matrix with different eigenvalues (real or not) is embeddable. This solves the embedding problem for a dense subset of nxn Markov matrices for any size n. We also study the rate identifiability problem, which is concerned about the unicity of Markov generators for a given embeddable matrix. Moreover, we give an explicit solution for the embedding problem for 4x4 Markov matrices. Not only this case was the smaller unsolved case, but it has practical consequences in phylogenetics as the embedding problem appears related to fundamental questions concerning the consistency of nucleotide substitution models. These models generally use a Markov process to describe the substitution of nucleotides over time in a given DNA sequence. We give the solution of the embedding problem restricted to some commonly used nucleotide substitution models such as Kimura models and the strand-symmetric model. For each of these models, one can define two different versions related by the embedding problem, a homogeneous continuous-time version and a more general version that avoids the time consideration. We shall see that the proportion of embeddale matrices (i.e. in the continuous-time version of the model) within the general version of the model decreases as the model hypothesis are relaxed. Indeed, we shall see that the proportion of embeddable matrix lies in the range between the 0.05% and the 75% depending on the complexity of the model. This shows that the time-continuous versions of these models are much more restrictive.

L'objectiu d'aquesta tesi és resoldre el problema d'embedding per a matrius de Markov, proposat per Gustav Elfving el 1937. Una matriu de Markov és una matriu quadrada, no negativa i amb files que sumen 1. Diem que una matriu de Markov M és embeddable si es pot expressar com l’exponencial d'una matriu de taxes, és a dir una matriu real, amb files que sumen 0 i amb entrades no negatives fora de la diagonal. En aquest cas, diem que la matriu de taxes és un generador de Markov de M. Tal i com el seu nom indica, el problema d'embedding consisteix en caracteritzar les matrius de Markov que són embeddable. La motivació del problema ve dels processos de Markov, els quals s'utilitzen per a modelar els canvis d'estat d'una variable aleatòria al llarg del temps sota la hipòtesi que el futur és independent del passat, és a dir, que les probabilitats de substitució no depenen dels canvis que hagin ocorregut en anteriorment. En aquest context, les entrades de les matrius de Markov representen les probabilitats de substitució després d'un període de temps fixat. Quan es considera que aquestes probabilitats són funcions contínues (i derivables) que depenen del temps, el procés de Markov es pot descriure en termes de les taxes instantànies de substitució entre estats. Per tal de mantenir el processos en temps continu tractables, sovint es considera que les taxes de substitució són constants. Sota aquesta hipòtesi d’homogeneïtat respecte el temps, les taxes de substitució es representen mitjançant les entrades d’una matriu de taxes Q i les matrius de Markov M(t) es poden escriure com l'exponencial de Qt per a tot t=0. En aquest cas, M(t) és embeddable i Qt n’és un generador de Markov. Per tant, el problema d’embedding consisteix en decidir si una matriu de transició pot sorgir d’un procés de Markov homogeni en temps continu. El problema d'embedding està resolt per a matrius 2x2 i 3x3 així com per a alguns casos particulars, com ara matrius properes a la identitat i matrius amb valors propis reals i diferents. En aquesta tesi presentem un mètode per determinar si una matriu de Markov amb valors propis diferents (reals o no) és embeddable, la qual cosa resol el problema per a un conjunt dens de matrius de Markov de qualsevol mida. També estudiem el problema d¿ identificabilitat de taxes, que consisteix en decidir si una matriu embeddable admet un únic generador de Markov. A més a més, resolem explícitament el problema d'embedding pel cas 4x4. Aquest cas és especialment rellevant, no només perquè era el cas més petit sense resoldre, sinó també per les seves implicacions en filogenètica, on el problema d'embedding està relacionat amb qüestions fonamentals respecte la definició i consistència dels models de substitució de nucleòtids utilitzats per modelar l¿ ' evolució de cadenes d'ADN. Per aquest motiu, també presentem la solució del problema d'embedding restringit a alguns dels models de substitució de nucleòtids més utilitzats, com per exemple, els models de Kimura o el model strand-symmetric. Per a cada un dels models considerats podem definir-ne dues versions relacionades pel problema d'embedding, una en temps continu i l'altra sense cap consideració respecte el temps. Observarem que la proporció de matrius embeddable (i.e. en temps continu) dins de la versió general del model disminueix a mesura que es relaxen les hipòtesis del model. De fet, veurem que aquesta proporció oscil·la entre el 75% i el 0,05% segons la complexitat del model i que per tant les versions en temps continu són molt més restrictives.