199 research outputs found
Inferring Temporally Consistent Migration Histories
No full textNot only do many biological populations undergo evolution, but population members may also migrate from one location to another. For example, tumor cells may migrate from the primary tumor and seed a new metastasis, and pathogens may migrate from one host to another. One may represent a population’s migration history by labeling the vertices of a given phylogeny T with locations such that an edge incident to vertices with distinct locations represents a migration. Additionally, in some biological populations, taxa from distinct lineages may comigrate from one location to another in a single event, a phenomenon known as a comigration. Here, we show that a previous problem statement for inferring migration histories that are parsimonious in terms of migrations and comigrations may lead to temporally inconsistent solutions. To remedy this deficiency, we introduce precise definitions of temporal consistency of comigrations in a phylogeny, leading to three successive problems. First, we formulate the Temporally Consistent Comigrations (TCC) problem to check if a set of comigrations is temporally consistent and provide a linear time algorithm for solving this problem. Second, we formulate the Parsimonious Consistent Comigration (PCC) problem, which aims to find comigrations given a location labeling of a phylogeny. We show that PCC is NP-hard. Third, we formulate the Parsimonious Consistent Comigration History (PCCH) problem, which infers the migration history given a phylogeny and locations of its extant vertices only. We show that PCCH is NP-hard as well. On the positive side, we propose integer linear programming models to solve the PCC and PCCH problems. We apply our approach to real and simulated data
‘Multi-SpaM’: a maximum-likelihood approach to phylogeny reconstruction using multiple spaced-word matches and quartet trees
No full textWord-based or ‘alignment-free’ methods for phylogeny inference have become popular in recent years. These methods are much faster than traditional, alignment-based approaches, but they are generally less accurate. Most alignment-free methods calculate ‘pairwise’ distances between nucleicacid or protein sequences; these distance values can then be used as input for tree-reconstruction programs such as neighbor-joining. In this paper, we propose the first word-based phylogeny approach that is based on ‘multiple’ sequence comparison and ‘maximum likelihood’. Our algorithm first samples small, gap-free alignments involving four taxa each. For each of these alignments, it then calculates a quartet tree and, finally, the program ‘Quartet MaxCut’ is used to infer a super tree for the full set of input taxa from the calculated quartet trees. Experimental results show that trees produced with our approach are of high quality
Efficient approximation of convex recolorings
No full textAbstractA coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring of trees arises in areas such as phylogenetics, linguistics, etc., e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree. Research on perfect phylogeny is usually focused on finding a tree so that few predetermined partial colorings of its vertices are convex.When a coloring of a tree is not convex, it is desirable to know “how far” it is from a convex one. In [S. Moran, S. Snir, Convex recoloring of strings and trees: Definitions, hardness results and algorithms, in: WADS, 2005, pp. 218–232; J. Comput. System Sci., submitted for publication], a natural measure for this distance, called the recoloring distance was defined: the minimal number of color changes at the vertices needed to make the coloring convex. This can be viewed as minimizing the number of “exceptional vertices” w.r.t. a closest convex coloring. The problem was proved to be NP-hard even for colored strings.In this paper we continue the work of [S. Moran, S. Snir, Convex recoloring of strings and trees: Definitions, hardness results and algorithms, in: WADS, 2005, pp. 218–232; J. Comput. System Sci., submitted for publication], and present a 2-approximation algorithm of convex recoloring of strings whose running time O(cn), where c is the number of colors and n is the size of the input, and an O(cn2) 3-approximation algorithm for convex recoloring of trees
Restricting SBH ambiguity via restriction enzymes
No full textAbstractSequencing by hybridization (SBH) is a proposed approach to DNA sequencing. The SBH-spectrum of the target sequence is a list of all k-mers occurring at least once in the sequence. Sequencing is successful if the SBH-spectrum is a result of only that sequence and ambiguous otherwise. Unfortunately, the expected number of sequences consistent with a given spectrum increases exponentially with the target sequence length.In this paper, we extend previous work of [S. Snir, E. Yeger-Lotem, B. Chor, Z. Yakhini, SBH+RE—restriction enzymes dramatically enhance SBH, Technical Report, Department of Computer Science, The Technion, Haifa, Israel, 2002] to increase the resolving power of SBH by including information from enzymatic digestion assays. In addition to the hybridization assay, we conduct a small number of complete digestion assays using different restriction enzymes. The computational phase of identifying consistent sequences then combines the hybridization and digestion information. This combination of SBH and digestion assays significantly increases the length of sequences that can be uniquely determined. We give procedures for selecting the best enzymes for the job, prove that a variant of the reconstruction problem which includes an extra free parameter is hard, and give effective heuristics to improve search-based reconstruction algorithms. We also give a lower bound on the number of restriction enzymes required for unique reconstruction
Multi-SpaM: A Maximum-Likelihood Approach to Phylogeny Reconstruction Using Multiple Spaced-Word Matches and Quartet Trees
No full textHorizontal Gene Transfer Phylogenetics: A Random Walk Approach
No full textSevillya G, Dörr D, Lerner Y, Stoye J, Steel M, Snir S. Horizontal Gene Transfer Phylogenetics: A Random Walk Approach. Molecular Biology and Evolution. 2020;37(5):1470–1479
Referencias intertextuales sobre el cuerpo en la poesía de ana maría martínez sagi
No full textThe work proposes an exploration of the poetic production of Ana María Martínez Sagi (Barcelona, 1907 - Moià, Barcelona, 2000), with an emphasis on some of the intertextual references related to the body that are detected in her work. Through her writing, the author constructs an identity that transcends the imposed generic cultural construction, which we will analyze here from intertextuality conceived as a semiotic category and used as a hermeneutic paradigm. Without revisiting the theme of the creation of a personal and carnal pagan religion in Martínez Sagi’s poems, already analyzed in “‘De mi cuerpo a tu cuerpo’: el ímpetu del amor oscuro en la poesía de Ana María Martínez Sagi”, we delve into how her texts establish relationships with those of her contemporaries and other authors, which also allows us to reflect on the different stages of her creative trajectory.El trabajo propone un recorrido por la producción poética de Ana María Martínez Sagi (Barcelona, 1907 - Moià, Barcelona, 2000), haciendo hincapié en algunas de las referencias intertextuales acerca del cuerpo que en ella se detectan. Por medio de su escritura, la autora construye una identidad que supere la construcción cultural genérica impuesta, lo que analizaremos aquí desde la intertextualidad concebida como categoría semiótica y usada como paradigma hermenéutico. Sin volver al tema de la creación de una religión pagana, personal y carnal en la producción en verso de Martínez Sagi, ya analizado en “‘De mi cuerpo a tu cuerpo’ el ímpetu del amor oscuro en la poesía de Ana María Martínez Sagi”, nos queda ahondar en cómo los textos de la poeta establecen relaciones con los de sus contemporáneos y otros autores, lo que, además, permite reflexionar sobre las diferentes etapas de su trayectoria creativa
Referencias intertextuales sobre el cuerpo en la poesía de Ana María Martínez Sagi
No full textThe work proposes an exploration of the poetic production of Ana María Martínez Sagi (Barcelona, 1907 - Moià, Barcelona, 2000), with an emphasis on some of the intertextual references related to the body that are detected in her work. Through her writing, the author constructs an identity that transcends the imposed generic cultural construction, which we will analyze here from intertextuality conceived as a semiotic category and used as a hermeneutic paradigm. Without revisiting the theme of the creation of a personal and carnal pagan religion in Martínez Sagi’s poems, already analyzed in “‘De mi cuerpo a tu cuerpo’: el ímpetu del amor oscuro en la poesía de Ana María Martínez Sagi”, we delve into how her texts establish relationships with those of her contemporaries and other authors, which also allows us to reflect on the different stages of her creative trajectory.El trabajo propone un recorrido por la producción poética de Ana María Martínez Sagi (Barcelona, 1907 - Moià, Barcelona, 2000), haciendo hincapié en algunas de las referencias intertextuales acerca del cuerpo que en ella se detectan. Por medio de su escritura, la autora construye una identidad que supere la construcción cultural genérica impuesta, lo que analizaremos aquí desde la intertextualidad concebida como categoría semiótica y usada como paradigma hermenéutico. Sin volver al tema de la creación de una religión pagana, personal y carnal en la producción en verso de Martínez Sagi, ya analizado en “‘De mi cuerpo a tu cuerpo’ el ímpetu del amor oscuro en la poesía de Ana María Martínez Sagi”, nos queda ahondar en cómo los textos de la poeta establecen relaciones con los de sus contemporáneos y otros autores, lo que, además, permite reflexionar sobre las diferentes etapas de su trayectoria creativa
Connected coloring completion for general graphs: Algorithms and complexity
No full textAn r-component connected coloring of a graph is a coloring of the vertices so that each color class induces a subgraph having at most r connected components. The concept has been well-studied for r = 1, in the case of trees, under the rubric of convex coloring, used in modeling perfect phylogenies. Several applications in bioinformatics of connected coloring problems on general graphs are discussed, including analysis of protein-protein interaction networks and protein structure graphs, and of phylogenetic relationships modeled by splits trees. We investigate the r-Component Connected Coloring Completion (r-CCC) problem, that takes as input a partially colored graph, having k uncolored vertices, and asks whether the partial coloring can be completed to an r-component connected coloring. For r = 1 this problem is shown to be NP-hard, but fixed-parameter tractable when parameterized by the number of uncolored vertices, solvable in time O *(8 k ). We also show that the 1-CCC problem, parameterized (only) by the treewidth t of the graph, is fixed-parameter tractable; we show this by a method that is of independent interest. The r-CCC problem is shown to be W[1]-hard, when parameterized by the treewidth bound t, for any r ≥ 2. Our proof also shows that the problem is NP-complete for r = 2, for general graphs
- …
