Thesis.lof

\addvspace {10\p@ }
\contentsline {figure}{\numberline {1.1}{\ignorespaces Mouse and human X chromosomes represented as 11 colored, directed segments (synteny blocks).\relax }}{3}{figure.caption.12}
\contentsline {figure}{\numberline {1.2}{\ignorespaces Transforming the mouse X chromosome into the human X chromosome with 7 reversals. Each synteny block is uniquely colored and labeled with an integer between 1 and 11; the positive or negative sign of each integer indicates the synteny block's direction (pointing right or left, respectively). Two short vertical segments delineate the endpoints of the inverted interval in each reversal. Suppose that this evolutionary scenario is correct and that, say, the 5th synteny block arrangement from the top presents the true ancestral arrangement. Then the first 4 reversals happened on the evolutionary path from mice to the human-mouse common ancestor (traveling backward in time), and the final 3 reversals happened on the evolutionary path from the common ancestor to humans (traveling forward in time). In this chapter, we are not interested in reconstructing the ancestral genome and thus are not concerned with whether a certain reversal travels backward or forward in time.\relax }}{6}{figure.caption.14}
\contentsline {figure}{\numberline {1.3}{\ignorespaces (Top) A histogram showing the number of blocks of each size (for a simulated genome with 25,000 genes after 320 randomly chosen reversals). Blocks having more than 100 genes are not shown. (Bottom) An average histogram of synteny block lengths for 100 simulations, fitted by the exponential distribution.\relax }}{9}{figure.caption.17}
\contentsline {figure}{\numberline {1.4}{\ignorespaces Histogram of human-mouse synteny block lengths (only synteny blocks longer than 1 million nucleotides are shown). The histogram is fitted by an exponential distribution.\relax }}{10}{figure.caption.18}
\contentsline {figure}{\numberline {1.5}{\ignorespaces A cartoon illustrating how a reversal breaks a chromosome in two places and inverts the segment between the two breakpoints. Note that the reversal changes the sign of each element within the permutation's inverted segment.\relax }}{12}{figure.caption.20}
\contentsline {figure}{\numberline {1.6}{\ignorespaces Encoding the mouse X chromosome as the identity permutation implies encoding the human X chromosome as $(+1$ $+7$ $-9$ $+11$ $+10$ $+3$ $-2$ $-6$ $+5$ $-4$ $-8)$.\relax }}{14}{figure.caption.21}
\contentsline {figure}{\numberline {1.7}{\ignorespaces A sorting by reversals. The inverted interval of each reversal is shown in red, while breakpoints in each permutation are marked by vertical segments.\relax }}{18}{figure.caption.26}
\contentsline {figure}{\numberline {1.8}{\ignorespaces The Philadelphia chromosome is formed by a translocation affecting chromosomes 9 and 22. It fuses together the ABL and BCR genes, forming a chimeric gene that can trigger CML.\relax }}{24}{figure.caption.31}
\contentsline {figure}{\numberline {1.9}{\ignorespaces A genome with two circular chromosomes, $(+a$ $-b$ $-c$ $+d)$ and $(+e$ $+f$ $+g$ $+h$ $+i$ $+j)$. Black directed edges represent synteny blocks, and red undirected edges connect adjacent synteny blocks. A circular chromosome with $n$ elements can be written in $2n$ different ways; the chromosome on the left can be written as $(+a$ $-b$ $-c$ $+d)$, $(-b$ $-c$ $+d$ $+a)$, $(-c$ $+d$ $+a$ $-b)$, $(+d$ $+a$ $-b$ $-c)$, $(-a$ $-d$ $+c$ $+b)$ $(-d$ $+c$ $+b$ $-a)$, $(+c$ $+b$ $-a$ $-d)$, and $(+b$ $-a$ $-d$ $+c)$.\relax }}{26}{figure.caption.35}
\contentsline {figure}{\numberline {1.10}{\ignorespaces Two equivalent drawings of the circular permutation $Q=(+a$ $-b$ $-d$ $+c)$.\relax }}{27}{figure.caption.37}
\contentsline {figure}{\numberline {1.11}{\ignorespaces A reversal transforms $P=(+a$ $-b$ $-c$ $+d)$ into $Q=(+a$ $-b$ $-d$ $+c)$. We have arranged the black edges of $Q$ so that they have the same orientation and position as the black edges in the natural representation of $P$. The reversal can be viewed as deleting the two red edges labeled by stars and replacing them with two new red edges on the same four nodes.\relax }}{28}{figure.caption.38}
\contentsline {figure}{\numberline {1.12}{\ignorespaces A fission of the single chromosome $P = (+a$ $-b$ $-c$ $+d)$ into the genome $Q = (+a$ $-b)(-c$ $+d)$. We have again arranged the black edges of $Q$ so that they have the same position and orientation as in the natural representation of $P$. The inverse operation is a fusion, transforming the two chromosomes of $Q$ into a single chromosome by breaking two red edges of $Q$ and replacing them with two other edges.\relax }}{29}{figure.caption.39}
\contentsline {figure}{\numberline {1.13}{\ignorespaces A translocation of linear chromosomes $(\leavevmode {\color {RoyalBlue}\boldsymbol {-a}}$ $\leavevmode {\color {ForestGreen}\boldsymbol {+b}}$ $\leavevmode {\color {ForestGreen}\boldsymbol {+c}}$ $\leavevmode {\color {ForestGreen}\boldsymbol {-d}})$ and $(\leavevmode {\color {ForestGreen}\boldsymbol {+e}}$ $\leavevmode {\color {RoyalBlue}\boldsymbol {+f}}$ $\leavevmode {\color {RoyalBlue}\boldsymbol {-g}}$ $\leavevmode {\color {RoyalBlue}\boldsymbol {+h}})$ transforms them into linear chromosomes $(\leavevmode {\color {RoyalBlue}\boldsymbol {-a}}$ $\leavevmode {\color {RoyalBlue}\boldsymbol {+f}}$ $\leavevmode {\color {RoyalBlue}\boldsymbol {-g}}$ $\leavevmode {\color {RoyalBlue}\boldsymbol {+h}})$ and $(\leavevmode {\color {ForestGreen}\boldsymbol {+e}}$ $\leavevmode {\color {ForestGreen}\boldsymbol {+b}}$ $\leavevmode {\color {ForestGreen}\boldsymbol {+c}}$ $\leavevmode {\color {ForestGreen}\boldsymbol {-d}})$. This translocation can also be accomplished by first circularizing the chromosomes, then applying a 2-break to the new chromosomes, and finally converting the resulting circular chromosomes into two linear chromosomes.\relax }}{30}{figure.caption.40}
\contentsline {figure}{\numberline {1.14}{\ignorespaces (Left) A red-black genome $\leavevmode {\color {Red}P} = (+a \nobreakspace {}{-b} \nobreakspace {} {-c} \nobreakspace {} +d)$ and a blue-black genome $\leavevmode {\color {RoyalBlue}Q} = (+a \nobreakspace {} +c \nobreakspace {} +b \nobreakspace {} {-d})$. (Middle) Rearranging the black edges of $\leavevmode {\color {RoyalBlue}Q}$ so that they are arranged the same as in $\leavevmode {\color {Red}P}$. (Right) The breakpoint graph $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}P}, \leavevmode {\color {RoyalBlue}Q})$, formed by superimposing the graphs of $\leavevmode {\color {Red}P}$ and $\leavevmode {\color {RoyalBlue}Q}$.\relax }}{31}{figure.caption.42}
\contentsline {figure}{\numberline {1.15}{\ignorespaces (Left) The red-blue alternating cycles in $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}P}, \leavevmode {\color {RoyalBlue}Q})$ for $\leavevmode {\color {Red}P}=(+a$ $-b$ $-c$ $+d)$ and $\leavevmode {\color {RoyalBlue}Q} = (+a$ $+c$ $+b$ $-d)$. (Right) The trivial breakpoint graph $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}P}, \leavevmode {\color {RoyalBlue}P})$, formed by two copies of the genome $P = (+a$ $-b$ $-c$ $+d)$. The breakpoint graph of \emph {any} genome with itself consists only of trivial (i.e., length 2) alternating cycles.\relax }}{32}{figure.caption.43}
\contentsline {figure}{\numberline {1.16}{\ignorespaces The construction of $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}P}, \leavevmode {\color {RoyalBlue}Q})$ for the unichromosomal genome $\leavevmode {\color {Red}P} = (+a$ $+b$ $+c$ $+d$ $+e$ $+f)$ and the two-chromosome genome $\leavevmode {\color {RoyalBlue}Q} = (+a$ $-c$ $-f$ $-e)(+b$ $-d)$. At the bottom, to illustrate the construction of the breakpoint graph, we first rearrange the black edges of $\leavevmode {\color {RoyalBlue}Q}$ so that they are drawn the same as in $\leavevmode {\color {Red}P}$.\relax }}{33}{figure.caption.44}
\contentsline {figure}{\numberline {1.17}{\ignorespaces A 2-break transforming genome $\leavevmode {\color {Red}P}$ into genome $\leavevmode {\color {Red}P'}$ also transforms $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}P}, \leavevmode {\color {RoyalBlue}Q})$ into $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}P'}\hspace {-0.1em}, \leavevmode {\color {RoyalBlue}Q})$ for any permutation $\leavevmode {\color {RoyalBlue}Q}$.\relax }}{34}{figure.caption.45}
\contentsline {figure}{\numberline {1.18}{\ignorespaces Every 2-break transformation of $\leavevmode {\color {Red}P}$ into $\leavevmode {\color {RoyalBlue}Q}$ corresponds to a transformation of $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}P}, \leavevmode {\color {RoyalBlue}Q})$ into $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}Q}, \leavevmode {\color {RoyalBlue}Q})$. In the example shown, the number of red-blue cycles in the graph increases from $\text {\scshape Cycles}(\leavevmode {\color {Red}P}, \leavevmode {\color {RoyalBlue}Q}) = 2$ to $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}Q}, \leavevmode {\color {RoyalBlue}Q}) = \text {\scshape Blocks}(\leavevmode {\color {Red}Q}, \leavevmode {\color {RoyalBlue}Q}) = 4$.\relax }}{34}{figure.caption.46}
\contentsline {figure}{\numberline {1.19}{\ignorespaces The transformation $\leavevmode {\color {Red}P} \rightarrow \leavevmode {\color {Red}P'} \rightarrow \leavevmode {\color {Red}Q}$ induces a transformation of the breakpoint graph $\text {\scshape BreakpointGraph}(\leavevmode {\color {Red}P}, \leavevmode {\color {RoyalBlue}Q})$ with 2 alternating cycles into the trivial breakpoint graph. Stars indicate red edges that are replaced in a 2-break.\relax }}{34}{figure.caption.47}
\contentsline {figure}{\numberline {1.20}{\ignorespaces Three cases illustrating how a 2-break can affect the breakpoint graph.\relax }}{35}{figure.caption.49}
\contentsline {figure}{\numberline {1.21}{\ignorespaces A visualization of repeated $k$-mers within the string {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {AGCAGGTTATCTCCCTGT}} for $k=3$ (top left) and $k=2$ (top right). (Bottom left) We add blue points to the plot shown in in the upper left corner to indicate reverse complementary $k$-mers. For example, {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {CCT}} and {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {AGG}} are reverse complementary 3-mers in {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {AGCAGGTTATCTTCCTGT}}. (Bottom right): Genomic dot-plot showing shared 3-mers between {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {\leavevmode {\color {Black}AGCAGG}\leavevmode {\color {RoyalBlue}\textbf {TTATCT}}\leavevmode {\color {Black}CCCTGT}}} and {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {\leavevmode {\color {Black}AGCAGG}\leavevmode {\color {Orange}\textbf {AGATAA}}\leavevmode {\color {Black}CCCTGT}}}. The latter sequence resulted from the former sequence by a reversal of the segment {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {\leavevmode {\color {RoyalBlue}\textbf {TTATCT}}}}. Each point $(x, y)$ corresponds to a $k$-mer shared by the two genomes. Red points indicate identical shared $k$-mers, whereas blue points indicate reverse complementary $k$-mers. Note that the dot-plot has four ``noisy'' blue points in the diagram: two in the upper left corner, and two in the bottom right corner. You will also notice that red dots can be connected into line segments with slope 1 and blue dots can be connected into line segments with slope -1. The resulting three synteny blocks ({\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {\leavevmode {\color {Red}\textbf {AGCAGG}}}}, {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {\leavevmode {\color {RoyalBlue}\textbf {TTATCT}}}}, and {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {\leavevmode {\color {Red}\textbf {CCCTGT}}}}) correspond to three diagonals (each formed by four points) in the dot-plot.\relax }}{42}{figure.caption.57}
\contentsline {figure}{\numberline {1.22}{\ignorespaces Genomic dot-plot of \textit {E. coli} (horizontal axis) and \textit {S. enterica} (vertical axis) for $k = 30$. Each point $(x, y)$ corresponds to a $k$-mer shared by the two genomes. Red points indicate identical shared $k$-mers, whereas blue points indicate reverse complementary $k$-mers. Each axis is measured in kilobases (thousands of base pairs).\relax }}{44}{figure.caption.59}
\contentsline {figure}{\numberline {1.23}{\ignorespaces From local similarities to synteny blocks. (Top left) The genomic dot-plot for the human and mouse X chromosomes, representing all positions $(x,y)$ where they share significant similarities. In contrast with \autoref {fig:e-coli_dot-plot}, we do not distinguish between red and blue dots. (Top right) Clusters (connected components) of points in the genomic dot-plot are formed by constructing the synteny graph. (Bottom left) Rectified clusters from the synteny graph transform each cluster into an exact diagonal of slope $\pm 1$. (Bottom right) Aggregated synteny blocks. Projection of the synteny blocks to the $x$-and $y$-axes results in the arrangements of synteny blocks in the respective human and mouse genomes $(+1$ $+2$ $+3$ $+4$ $+5$ $+6$ $+7$ $+8$ $+9$ $+10$ $+11)$ and $(+1$ $-7$ $+6$ $-10$ $+9$ $-8$ $+2$ $-11$ $-3$ $+5$ $+4)$.\relax }}{47}{figure.caption.61}
\contentsline {figure}{\numberline {1.24}{\ignorespaces The graph $\text {\scshape SyntenyGraph}(\textit {DotPlot}, 4)$ constructed from the genomic dot-plot of {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {\leavevmode {\color {Black}AGCAGG}\leavevmode {\color {RoyalBlue}\textbf {TTATCT}}\leavevmode {\color {Black}CCCTGT}}} and {\fontfamily {pcr}\fontsize {1.04em}{1.04em}\selectfont \text {\leavevmode {\color {Black}AGCAGG}\leavevmode {\color {Orange}\textbf {AGATAA}}\leavevmode {\color {Black}CCCTGT}}} for $k = 3$. Note that the three synteny blocks (all of which have four nodes) correspond to diagonals in the genomic dot-plot. We ignore the two smaller, noisy synteny blocks.\relax }}{48}{figure.caption.63}
\contentsline {figure}{\numberline {1.25}{\ignorespaces The probability density functions of the geometric (left) and exponential (right) distributions, each provided for three different parameter values. Courtesy Skbkekas (Wikipedia user).\relax }}{55}{figure.caption.72}
\contentsline {figure}{\numberline {1.26}{\ignorespaces (1st panel) An alternating path of red and black edges representing the human X chromosome $(+1$ $+2$ $+3$ $+4$ $+5$ $+6$ $+7$ $+8$ $+9$ $+10$ $+11)$. (2nd panel) An alternating path of blue and black edges representing the mouse X chromosome $(+1$ $-7$ $+6$ $-10$ $+9$ $-8$ $+2$ $-11$ $-3$ $+5$ $+4)$. (3rd panel) The breakpoint graph of the mouse and human X chromosomes is obtained by superimposing red-black and blue-black paths from the first two panels. (4th panel) To highlight the five alternating red-blue cycles in the breakpoint graph, black edges are removed.\relax }}{58}{figure.caption.77}
\addvspace {10\p@ }
\addvspace {10\p@ }
\contentsline {figure}{\numberline {3.1}{\ignorespaces (Top) DCJs replace two adjacencies of a genome and incorporate three operations on circular chromosomes: reversals, fissions, and fusions. Genes are shown in black, and adjacencies are shown in red. (Bottom) The construction of the breakpoint graph of genomes $\Pi $ and $\Gamma $ having the same genes. First, the nodes of $\Gamma $ are rearranged so that they have the same position in $\Pi $. Then, the adjacency graph is formed as the disjoint union of adjacencies of $\Pi $ (red) and $\Gamma $ (blue).\relax }}{98}{figure.caption.106}
\addvspace {10\p@ }