检索结果-内蒙古大学图书馆

A Local Prime Factor Decomposition Algorithm for Strong Product Graphs

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Hellmuth, Marc Dpt. of Mathematics and Computer Science University of Greifswald Walther-Rathenau-Strasse 47 GreifswaldD-17487 Germany Saarland University Center for Bioinformatics Building E 2.1 P.O. Box 151150 SaarbrückenD-66041 Germany Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany

This work is concerned with the prime factor decomposition (PFD) of strong product graphs. A new quasi-linear time algorithm for the PFD with respect to the strong product for arbitrary, finite, connected, undirected graphs is derived. Moreover, since most graphs are prime although they can have a product-like structure, also known as approximate graph products, the practical application of the well-known"classical" prime factorization algorithm is strictly limited. This new PFD algorithm is based on a local approach that covers a graph by small factorizable subgraphs and then utilizes this information to derive the global factors. Therefore, we can take advantage of this approach and derive in addition a method for the recognition of approximate graph products. Copyright © 2017, The Authors. All rights reserved.

关键词： Graphic methods

学校读者我要写书评

暂无评论

Best match graphs

arXiv 2018年

作者： Geiß, Manuela Chávez, Edgar González, Marcos López, Alitzel Valdivia, Dulce Rosales, Maribel Hernández Stadler, Bärbel M.R. Hellmuth, Marc Stadler, Peter F. Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Germany Saarland University Center for Bioinformatics Building E 2.1 P.O. Box 151150 SaarbrückenD-66041 Germany Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Inst. f. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States CONACYT-Instituto de Matemáticas UNAM Juriquilla Blvd. Juriquilla 3001 Juriquilla Querétaro QRO76230 Mexico Universidad Autónoma de Aguascalientes Centro de Ciencias Básicas Av. Universidad 940 Aguascalientes AGS20131 Mexico Instituto de Matemáticas UNAM Juriquilla Blvd. Juriquilla 3001 Juriquilla Querétaro QRO76230 Mexico

Best match graphs arise naturally as the first processing intermediate in algorithms for orthology detection. Let T be a phylogenetic (gene) tree T and σ an assignment of leaves of T to species. The best match graph (G, σ) is a digraph that contains an arc from x to y if the genes x and y reside in different species and y is one of possibly many (evolutionary) closest relatives of x compared to all other genes contained in the species σ(y). Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether (G, σ) derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains (G, σ), which can also be constructed in cubic time. Copyright © 2018, The Authors. All rights reserved.

关键词： Phylogenetic

Horizons: Nuclear Astrophysics in the 2020s and Beyond

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Schatz, Hendrik Becerril Reyes, A.D. Best, A. Brown, E.F. Chatziioannou, K. Chipps, K.A. Deibel, C.M. Ezzeddine, R. Galloway, D.K. Hansen, C.J. Herwig, F. Ji, A.P. Lugaro, M. Meisel, Z. Norman, D. Read, J.S. Roberts, L.F. Spyrou, A. Tews, I. Timmes, F.X. Travaglio, C. Vassh, N. Abia, C. Adsley, P. Agarwal, S. Aliotta, M. Aoki, W. Arcones, A. Aryan, A. Bandyopadhyay, A. Banu, A. Bardayan, D.W. Barnes, J. Bauswein, A. Beers, T.C. Bishop, J. Boztepe, T. Côté, B. Caplan, M.E. Champagne, A.E. Clark, J.A. Couder, M. Couture, A. de Mink, S.E. Debnath, S. deBoer, R.J. den Hartogh, J. Denissenkov, P. Dexheimer, V. Dillmann, I. Escher, J.E. Famiano, M.A. Farmer, R. Fisher, R. Fröhlich, C. Frebel, A. Fryer, C. Fuller, G. Ganguly, A.K. Ghosh, S. Gibson, B.K. Gorda, T. Gourgouliatos, K.N. Graber, V. Gupta, M. Haxton, W. Heger, A. Hix, W.R. Ho, W.C.G. Holmbeck, E.M. Hood, A.A. Huth, S. Imbriani, G. Izzard, R.G. Jain, R. Jayatissa, H. Johnston, Z. Kajino, T. Kankainen, A. Kiss, G.G. Kwiatkowski, A. La Cognata, M. Laird, A.M. Lamia, L. Landry, P. Laplace, E. Launey, K.D. Leahy, D. Leckenby, G. Lennarz, A. Longfellow, B. Lovell, A.E. Lynch, W.G. Lyons, S.M. Maeda, K. Masha, E. Matei, C. Merc, J. Messer, B. Montes, F. Mukherjee, A. Mumpower, M. Neto, D. Nevins, B. Newton, W.G. Nguyen, L.Q. Nishikawa, K. Nishimura, N. Nunes, F.M. O’Connor, E. O’Shea, B.W. Ong, W.-J. Pain, S.D. Pajkos, M.A. Pignatari, M. Pizzone, R.G. Placco, V.M. Plewa, T. Pritychenko, B. Psaltis, A. Puentes, D. Qian, Y.-Z. Radice, D. Rapagnani, D. Rebeiro, B.M. Reifarth, R. Richard, A.L. Rijal, N. Roederer, I.U. Rojo, J.S. Sk, J. Saito, Y. Schwenk, A. Sergi, M.L. Sidhu, R.S. Simon, A. Sivarani, T. Skúladóttir, Á. Smith, M.S. Spiridon, A. Sprouse, T.M. Starrfield, S. Steiner, A.W. Strieder, F. Sultana, I. Surman, R. Szücs, T. Tawfik, A. Thielemann, F. Trache, L. Trappitsch, R. Department of Physics and Astronomy Michigan State University East LansingMI48824 United States Facility for Rare Isotope Beams Michigan State University East LansingMI48824 United States United States Department of Physics University of Naples"Federico II" Napoli80126 Italy INFN - Sezione di Napoli Napoli80126 Italy Department of Computational Mathematics Science and Engineering MichiganState University East LansingMI48824 United States Department of Physics California Institute of Technology PasadenaCA91125 United States LIGO Laboratory California Institute of Technology PasadenaCA91125 United States Physics Division Oak Ridge National Laboratory Oak RidgeTN37831 United States Department of Physics and Astronomy University of Tennessee Knoxville KnoxvilleTN37996 United States Department of Physics and Astronomy Louisiana State University Baton RougeLA70803 United States Department of Astronomy University of Florida GainesvilleFL32601 United States School of Physics and Astronomy Monash University VIC3800 Australia OzGRav-Monash School of Physics & Astronomy Monash University VIC3800 Australia Goethe University Frankfurt Institute for Applied Physics Max-von-Laue-Str. 12 Frankfurt am Main60438 Germany Technical University of Darmstadt Institute for Nuclear Physics Germany Max Planck Institute for Astronomy Heidelberg Germany Department of Physics and Astronomy University of Victoria VictoriaBCV8P 5C2 Canada Department of Astronomy & Astrophysics University of Chicago 5640 S Ellis Avenue ChicagoIL60637 United States Kavli Institute for Cosmological Physics University of Chicago ChicagoIL60637 United States Excellence Centre of the Hungarian Academy of Sciences Konkoly-Thege Miklós út 15-17 BudapestH-1121 Hungary ELTE Eötvös Loránd University Institute of Physics Pázmány Péter sétány 1/A Budapest1117 Hungary Institute of Nuclear & Particle Physics Department of Physics & Astronomy Ohio University AthensOH45701

Nuclear Astrophysics is a field at the intersection of nuclear physics and astrophysics, which seeks to understand the nuclear engines of astronomical objects and the origin of the chemical elements. This white paper summarizes progress and status of the field, the new open questions that have emerged, and the tremendous scientific opportunities that have opened up with major advances in capabilities across an ever growing number of disciplines and subfields that need to be integrated. We take a holistic view of the field discussing the unique challenges and opportunities in nuclear astrophysics in regards to science, diversity, education, and the interdisciplinarity and breadth of the field. Clearly nuclear astrophysics is a dynamic field with a bright future that is entering a new era of discovery opportunities. © 2022, CC BY-NC-SA.

关键词： Astrophysics

Forbidden time travel: Characterization of time-consistent tree reconciliation maps

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Nøjgaard, Nikolai Geiß, Manuela Stadler, Peter F. Merkle, Daniel Wieseke, Nicolas Hellmuth, Marc Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Department of Mathematics and Computer Science University of Southern Denmark Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Motivation: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to eventlabeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. Results: We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V(T)|log(|V (S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. Significance: The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with horizontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems. Copyright © 2017, The Authors. All rights reserved.

关键词： Genes

Model for the organization, storage and processing of large data banks of physiological variables

学校读者我要写书评

暂无评论

Model for the organization, storage and processing of large ...

International Conference on computers Communications and Control (ICCCC)

作者： Fredi E. Palominos Hernán Diaz Felisa M. Córdova A. Lucio Canete Claudia A. Durán Dpt. Mathematics and Computer Science University of Santiago de Chile Santiago Chile Dpt. Chemistry and Biology University of Santiago de Chile Santiago Chile School of Industrial Engineering University Finis Terrae Santiago Chile Universidad de Santiago de Chile Santiago de Chile CL Dpt. of Industrial Engineering University of Santiago de Chile Santiago Chile

ISBN: (纸本)9781509017362

The proliferation and popularization of new instruments for measuring different types of electrophysiological variables, has generated the need to store huge volumes of information, corresponding to the records obtained by applying this instruments on experimental subjects. Together with this must be added the data derived from the analysis and purification processes. Moreover, several stages involved in the processing of data, is associated with one or more specific methods related to the area of research and to the treatment at which the base information (RAW) is subjected. As a result of this and with the passage of time, various problems occur, which are the most obvious consequence of that data and metadata derived from the treatment processes and analysis, and can end up accumulating and requiring more storage space than the base data. In addition, the enormous amount of information, as it increases over time, can lead to the loss of the link between the processed data, the methods of treatment used, and the analysis performed, so that eventually all becomes simply a huge repository of biometric data, devoid of meaning and sense. Current approaches around the concept of big data, while take over the storage and other aspects such as information search mechanisms, are far from incorporating metadata about the neurophysiological and emotional records. This type of information requires the construction of chronologies of events, including the methods of processing and analysis. In addition, it is required to maintain an adequate link between those responsible for the data (those who recorded and analyzed) and subjects that are under investigation, without breaking confidentiality to which they are entitled. This paper presents an approach founded in a data model that can adequately handle different types of chronologies of physiological and emotional information, ensuring confidentiality of information according to the experimental protocols and relevant ethical

关键词： Electroencephalography Big data Instruments Metadata computers Cleaning

Submap bathymetric SLAM using structured light in underwater environments

学校读者我要写书评

暂无评论

Submap bathymetric SLAM using structured light in underwater...

Symposium on Autonomous Underwater Vehicle Technology (AUV)

作者： Miquel Massot-Campos Gabriel Oliver Adrian Bodenmann Blair Thornton Dpt. of Mathematics and Computer Science University of the Balearic Islands Palma de Mallorca Spain Institute of Industrial Science University of Tokyo Tokyo Japan Southampton Marine and Maritime Institute University of Southampton Southampton UK

ISBN: (纸本)9781509024438

This article presents a bathymetric SLAM (simultaneous localization and mapping) solution for underwater vehicles by addressing the registration of point clouds gathered from single line laser-based structured light systems. While structured light can be applied to generate millimetre resolution seafloor bathymetry, the accuracy of the maps generated is typically constrained by the localization accuracy of the vehicles used. In this work, relative uncertainties in vehicle localisation are reduced by implementing bathymetric SLAM using temporally constrained submaps. We demonstrate that the method described can overcome misalignments by correcting errors in localisation and can be used to generate self-consistent high-resolution seafloor bathymetric maps.

关键词： Lasers Vehicles Uncertainty Simultaneous localization and mapping Three-dimensional displays Cameras Feature extraction

Reconstructing gene trees from Fitch's xenology relation

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Geiß, Manuela Anders, John Stadler, Peter F. Wieseke, Nicolas Hellmuth, Marc Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Germany Saarland University Center for Bioinformatics Building E 2.1 P.O. Box 151150 SaarbrückenD-66041 Germany Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. f. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Two genes are xenologs in the sense of Fitch if they are separated by at least one horizontal gene transfer event. Horizonal gene transfer is asymmetric in the sense that the transferred copy is distinguished from the one that remains within the ancestral lineage. Hence xenology is more precisely thought of as a non-symmetric relation: y is xenologous to x if y has been horizontally transferred at least once since it diverged from the least common ancestor of x and y. We show that xenology relations are characterized by a small set of forbidden induced subgraphs on three vertices. Furthermore, each xenology relation can be derived from a unique least-resolved edge-labeled phylogenetic tree. We provide a linear-time algorithm for the recognition of xenology relations and for the construction of its least-resolved edge-labeled phylogenetic tree. The fact that being a xenology relation is a heritable graph property, finally has far-reaching consequences on approximation problems associated with xenology relations. Copyright © 2017, The Authors. All rights reserved.

关键词： Clustering algorithms

From event labeled gene trees to species trees

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Hernandez-Rosales, Maribel Hellmuth, Marc Wieseke, Nicolas Huber, Katharina T. Moulton, Vincent Stadler, Peter F. Dpt. of Mathematics and Computer Science University of Greifswald Walther- Rathenau-Strasse 47 GreifswaldD-17487 Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany School of Computing Sciences University of East Anglia NorwichNR4 7TJ United Kingdom Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa Fe United States Parallel Computing and Complex Systems Group Department of Computer Science Leipzig University Augustusplatz 10 Leipzig04109 Germany

Background: Tree reconciliation problems have long been studied in phylogenetics. A particular variant of the reconciliation problem for a gene tree T and a species tree S assumes that for each interior vertex x of T it is known whether x represents a speciation or a duplication. This problem appears in the context of analyzing orthology data. Results: We show that S is a species tree for T if and only if S displays all rooted triples of T that have three distinct species as their leaves and are rooted in a speciation vertex. A valid reconciliation map can then be found in polynomial time. Simulated data shows that the event-labeled gene trees convey a large amount of information on underlying species trees, even for a large percentage of losses. Conclusions: The knowledge of event labels in a gene tree strongly constrains the possible species tree and, for a given species tree, also the possible reconciliation maps. Nevertheless, many degrees of freedom remain in the space of feasible solutions. In order to disambiguate the alternative solutions additional external constraints as well as optimization criteria could be employed. Copyright © 2017, The Authors. All rights reserved.

关键词： Polynomial approximation

Cograph editing: Merging modules is equivalent to editing P4s

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Fritz, Adrian Hellmuth, Marc Wieseke, Nicolas Stadler, Peter F. Computational Biology of Infection Research Helmholtz Centre for Infection Research Inhoffenstraße 7 BraunschweigD-38124 Germany University of Greifswald Dpt. of Mathematics and Computer Science Walther- Rathenau-Strasse 47 GreifswaldD-17487 Germany Saarland University Center for Bioinformatics Building e 2.1 P.O. Box 151150 SaarbrückenD-66041 Germany Parallel Computing and Complex Systems Group Department of Computer Science University of Leipzig Augustusplatz 10 LeipzigD-04109 Germany Bioinformatics Group Department of Computer Science Interdisciplinary Center of Bioinformatics University of Leipzig Härtelstraße 16-18 LeipzigD-04107 Germany Max-Planck-Institute for Mathematics in the Sciences Inselstraße 22 LeipzigD-04103 Germany Inst. F. Theoretical Chemistry University of Vienna Währingerstraße 17 WienA-1090 Austria Santa Fe Institute 1399 Hyde Park Rd. Santa FeNM87501 United States

The modular decomposition of a graph G = (V;E) does not contain prime modules if and only if G is a cograph, that is, if no quadruple of vertices induces a simple connected path P4. The cograph editing problem consists in inserting into and deleting from G a set F of edges so that H = (V,EΔF) is a cograph and |F| is minimum. This NP-hard combinatorial optimization problem has recently found applications, e.g., in the context of phylogenetics. Efficient heuristics are hence of practical importance. The simple characterization of cographs in terms of their modular decomposition suggests that instead of editing G one could operate directly on the modular decomposition. We show here that editing the induced P4s is equivalent to resolving prime modules by means of a suitable defined merge operation on the submodules. Moreover, we characterize so-called module-preserving edit sets and demonstrate that optimal pairwise sequences of module-preserving edit sets exist for every non-cograph. This eventually leads to an exact algorithm for the cograph editing problem. In addition, we provide two heuristics with time complexity O(|V|3), resp., O(|V|2). Copyright © 2017, The Authors. All rights reserved.

关键词： Graph theory