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

Inflation algorithms for Positive and Principal Edge-bipartite Graphs and Unit Quadratic Forms

FUNDAMENTA INFORMATICAE 2012年第2期119卷 149-162页

作者： Kosakowska, Justyna Nicolaus Copernicus Univ Fac Math & Comp Sci PL-87100 Torun Poland

We describe combinatorial algorithms that compute the Dynkin type (resp. Euclidean type) of any positive (resp. principal) unit quadratic form q : Z(n) -> Z and of any positive ( resp. principal) edge-bipartite connected graph Delta. The study of the problem is inspired by applications of the algorithms in the representation theory, in solving a class of Diophantine equations, in the study of mesh geometries of roots, in the spectral analysis of graphs, and in the Coxeter-Gram classification of edge-bipartite graphs.

关键词： edge-bipartite graphs Dynkin graphs Euclidean graphs quadratic forms equivalence of quadratic forms combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Sorting Linear Genomes with Rearrangements and Indels

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2015年第3期12卷 500-506页

作者： Braga, Marilia D. V. Stoye, Jens Inmetro Inst Nacl Metrol Qualidade & Tecnol Rio De Janeiro Brazil Univ Bielefeld Fac Technol Bielefeld Germany Univ Bielefeld Ctr Biotechnol Bielefeld Germany

Rearrangements are mutations that can change the organization of a genome, but not its content. Examples are inversions of DNA segments, translocations of chromosome ends, fusions and fissions of chromosomes. All mentioned rearrangements can be represented by the generic Double Cut and Join (DCJ) operation. However, the DCJ operation also allows circular chromosomes to be created at intermediate steps, even if the compared genomes are linear. In this case it is more plausible to consider a restriction in which the reincorporation of a circular chromosome has to be done immediately after its creation. We call these two consecutive operations an ER composition. It has been shown that an ER composition mimics either an internal block interchange (when two segments in the same chromosome exchange their positions), or an internal transposition (the special case of a block interchange when the two segments are adjacent). The DCJ distance of two genomes is the same, regardless of this restriction, and can be computed in linear time. For comparing two genomes with unequal contents, in addition to rearrangements we have to allow insertions and deletions of DNA segments-named indels. It is already known that the distance in the model combining DCJ and indel operations can be exactly computed. Again, for linear genomes it would be more plausible to adopt a restricted version with ER compositions. This model was studied recently by da Silva et al. (BMC Bioinformatics 13, Suppl. 19, S14, 2012), but only an upper bound for the restricted DCJ-indel distance was provided. Here we first solve an open problem posed in that paper and present a very simple proof showing that the distance, which can be computed in linear time, is the same for both the unrestricted and the restricted DCJ-indel models. We then give a simpler algorithm for computing an optimal restricted DCJ-indel sorting scenario in O(n log n) time. We also relate the DCJ-indel distance to the restricted DCJ-substitution

关键词： combinatorial algorithms bioinformatics comparative genomics genome rearrangement double cut and join

来源：评论

学校读者我要写书评

暂无评论

Rank aggregation: New bounds for MCx

引用

DISCRETE APPLIED MATHEMATICS 2019年 252卷 28-36页

作者： Freund, Daniel Williamson, David P. Cornell Univ Ctr Appl Math Ithaca NY 14853 USA Cornell Univ Sch Operat Res & Informat Engn Ithaca NY USA

The rank aggregation problem has received significant recent attention within the computer science community. Its applications today range far beyond the original aim of building metasearch engines to problems in machine learning, recommendation systems and more. Several algorithms have been proposed for these problems, and in many cases approximation guarantees have been proven for them. However, it is also known that some Markov chain based algorithms (MC1, MC2, MC3, MC4) perform extremely well in practice, yet had no known performance guarantees. We prove supra-constant lower bounds on approximation guarantees for all of them. Nevertheless, we show that in particular ways, MC4 can be seen as a generalization of Copeland score. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Rank aggregation Computations on discrete structures combinatorial algorithms Approximation guarantees

来源：评论

学校读者我要写书评

暂无评论

A quorum-based protocol for searching objects in peer-to-peer networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2006年第1期17卷 25-37页

作者： Miura, K Tagawa, T Kakugawa, H Oki Data Corp Minato Ku Tokyo 1088551 Japan Hiroshima Univ Dept Informat Engn Hiroshima 7398527 Japan Osaka Univ Grad Sch Informat Sci & Technol Dept Comp Sci Osaka 5608531 Japan

Peer-to-peer (P2P) system is an overlay network of peer computers without centralized servers, and many applications have been developed for such networks such as file sharing systems. Because a set of peers dynamically changes, design and verification of efficient protocols is a challenging task. In this paper, we consider an object searching problem under a resource model such that there are some replicas in a system and the lower bound of the ratio rho = n'/n is known in advance, where n' is a lower bound of the number of peers that hold original or replica for any object type and n is the total number of peers. In addition, we consider object searching with probabilistic success, i.e., for each object search, object must be found with at least probability 0 < sigma < 1. To solve such a problem efficiently, we propose a new communication structure, named probabilistic weak quorum systems (PWQS), which is an extension of coterie. Then, we propose a fault-tolerant protocol for searching for objects in a P2P system. In our method, each peer does not maintain global information such as the set of all peers and a logical topology with global consistency. In our protocol, each peer communicates only a small part of a peer set and, thus, our protocol is adaptive for huge scale P2P network.

关键词： distributed systems distributed data structures reliability and robustness combinatorial algorithms distributed file systems

来源：评论

学校读者我要写书评

暂无评论

Searching of gapped repeats and subrepetitions in a word

引用

JOURNAL OF DISCRETE algorithms 2017年 46-47卷 1-15页

作者： Kolpakov, Roman Podolskiy, Mikhail Posypkin, Mikhail Khrapov, Nickolay Lomonosov Moscow State Univ Moscow 119992 Russia FRC CSC RAS Dorodnicyn Comp Ctr Vavilov St Moscow 119333 Russia Inst Informat Transmiss Problems Moscow 127994 Russia

A gapped repeat is a factor of the form uvu where u and v are nonempty words. The period of the gapped repeat is defined as vertical bar u vertical bar + vertical bar v vertical bar. The gapped repeat is maximal if it cannot be extended to the left or to the right by at least one letter with preserving its period. The gapped repeat is called alpha-gapped if its period is not greater than alpha vertical bar u vertical bar. A delta-subrepetition is a factor whose exponent is less than 2 but is not less than 1 + delta (the exponent of the factor is the quotient of the length and the minimal period of the factor). The delta-subrepetition is maximal if it cannot be extended to the left or to the right by at least one letter with preserving its minimal period. We reveal a close relation between maximal gapped repeats and maximal subrepetitions. Moreover, we show that in a word of length n the number of maximal alpha-gapped repeats is bounded by O(alpha(2)n) and the number of maximal delta-subrepetitions is bounded by O(n/delta(2)). Using the obtained upper bounds, we propose algorithms for finding all maximal alpha-gapped repeats and all maximal delta-subrepetitions in a word of length n(in assumption that the alphabet of the word is integer). The algorithm for finding all maximal a-gapped repeats has O(alpha(2)n) time complexity. For finding all maximal delta-subrepetitions we propose two algorithms. The first algorithm has O(n log log n/delta(2)) time complexity. The second algorithm has O(n log n + n/delta(2) log 1/delta) expected time complexity. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Combinatorics on words combinatorial algorithms Time complexity Repetitions

来源：评论

学校读者我要写书评

暂无评论

Generating m-Ary Gray Codes and Related algorithms

引用

algorithms 2024年第7期17卷 311页

作者： Bouyuklieva, Stefka Bouyukliev, Iliya Bakoev, Valentin Pashinska-Gadzheva, Maria St Cyril & St Methodius Univ Veliko Tarnovo Fac Math & Informat Veliko Tarnovo 5000 Bulgaria Bulgarian Acad Sci Inst Math & Informat Veliko Tarnovo 5000 Bulgaria

In this work, we systematize several implementations of the Gray code over an alphabet with m >= 2 elements, which we present in C code so that they can be used directly after copying from the text. We consider two variants-reflected and modular (or shifted) m-ary Gray codes. For both variants, we present the ranking and unranking functions, as well as algorithms for generating only a part of the code, more precisely the codewords between two given vectors. Finally, we give algorithms that generate a maximal set of non-proportional vectors of length n over the given alphabet in a Gray code.

关键词： Gray code m-ary Gray code combinatorial algorithms combinatorial generation ranking unranking

来源：评论

学校读者我要写书评

暂无评论

Ontological discovery environment: A system for integrating gene-phenotype associations

引用

GENOMICS 2009年第6期94卷 377-387页

作者： Baker, Erich J. Jay, Jeremy J. Philip, Vivek M. Zhang, Yun Li, Zuopan Kirova, Roumyana Langston, Michael A. Chesler, Elissa J. Baylor Univ Dept Comp Sci Waco TX 76798 USA Univ Tennessee Dept Elect Engn & Comp Sci Knoxville TN USA Univ Tennessee Grad Sch Genome Sci & Technol Knoxville TN USA Oak Ridge Natl Lab Div Life Sci Oak Ridge TN 37831 USA

The wealth of genomic technologies has enabled biologists to rapidly ascribe phenotypic characters to biological substrates. Central to effective biological investigation is the operational definition of the process under investigation. We propose an elucidation of categories of biological characters, including disease relevant traits, based on natural enclogenous processes and experimentally observed biological networks, pathways and systems rather than on externally manifested constructs and current semantics such as disease names and processes. The Ontological Discovery Environment (ODE) is an Internet accessible resource for the storage, sharing, retrieval and analysis of phenotype-centered genomic data sets across species and experimental model systems. Any type of data set representing gene-phenotype relationships, such quantitative trait loci (QTL) positional candidates, literature reviews, microarray experiments, ontological or even meta-data, may serve as inputs. To demonstrate a use case leveraging the homology capabilities of ODE and its ability to synthesize diverse data sets, we conducted an analysis of genomic studies related to alcoholism. The core of ODE's gene set similarity, distance and hierarchical analysis is the creation of a bipartite network of gene-phenotype relations, a unique discrete graph approach to analysis that enables set-set matching of non-referential data. Gene sets are annotated with several levels of metadata, including community ontologies, while gene set translations compare models across species. Computationally derived gene sets are integrated into hierarchical trees based on gene-derived phenotype interdependencies. Automated set identifications are augmented by statistical tools which enable users to interpret the confidence of modeled results. This approach allows data integration and hypothesis discovery across multiple experimental contexts, regardless of the face similarity and semantic annotation of the experimental s

关键词： Homology combinatorial algorithms Microarray Ontology

来源：评论

学校读者我要写书评

暂无评论

Multinomial goodness-of-fit: Large-sample tests with survey design correction and exact tests for small samples

引用

STATA JOURNAL 2008年第2期8卷 147-169页

作者： Jann, Ben ETH Zurich Switzerland

I introduce the new mgof command to compute distributional tests for discrete (categorical, multinomial) variables. The command supports large-sample tests for complex survey designs and exact tests for small samples as well as classic large-sample chi(2)-approximation tests based on Pearson's X-2, the likelihood ratio, or any other statistic from the power-divergence family (Cressie and Read, 1984, Journal of the Royal Statistical Society, Series B (Methodological) 46: 440-464). The complex survey correction is based on the approach by Rao and Scott (1981, Journal of the American Statistical Association 76: 221-230) and parallels the survey design correction used for independence tests in svy: tabulate. mgof computes the exact tests by using Monte Carlo methods or exhaustive enumeration. mgof also provides an exact one-sample Kolmogorov-Smirnov test for discrete data.

关键词： st0142 mgof mgofi multinomial goodness-of-fit chi-squared categorical data exact tests Monte Carlo exhaustive enumeration combinatorial algorithms complex survey correction power-divergence statistic Kolmogorov-Smirnov Benford's law

来源：评论

学校读者我要写书评

暂无评论

Bicriteria network design problems

引用

JOURNAL OF algorithms 1998年第1期28卷 142-171页

作者： Marathe, MV Ravi, R Sundaram, R Ravi, SS Rosenkrantz, DJ Hunt, HB Univ Calif Los Alamos Natl Lab Los Alamos NM 87545 USA Carnegie Mellon Univ GSIA Pittsburgh PA 15213 USA Delta Trading Co Cambridge MA USA SUNY Albany Dept Comp Sci Albany NY 12222 USA Princeton Univ DIMACS Princeton NJ 08544 USA MIT LCS Cambridge MA 02139 USA

We study a general class of bicriteria network design problems. A generic problem in this class is as follows: Given an undirected graph and two minimization objectives (under different cost functions), with a budget specified on the first objective, find a subgraph from a given subgraph-class that minimizes the second objective subject to the budget on the first objective. We consider three different criteria - the total edge cost, the diameter, and the maximum degree of the network. Here, we present the first polynomial-time approximation algorithms for a large class of bicriteria network design problems for the previously mentioned criteria. The following general types of results are presented. First, we develop a framework for bicriteria problems and their approximations. Second, when the two criteria are the same we present a "black box" parametric search technique. This black box takes in as input an (approximation) algorithm for the unicriterion situation and generates an approximation algorithm for the bicriteria case with only a constant factor loss in the performance guarantee. Third, when the two criteria are the diameter and the total edge costs we use a cluster-based approach to devise a approximation algorithms - the solutions output violate both the criteria by a logarithmic factor. Finally, for the class of treewidth-bounded graphs, we provide pseudo-polynomial-time algorithms for a number of bicriteria problems using dynamic programming. We show how these pseudo-polynomial-time algorithms can be converted to fully polynomial-time approximation schemes using a scaling technique. (C) 1998 Academic Press.

关键词： approximation algorithms bicriteria problems spanning trees network design combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

PLACEMENT algorithms FOR CUSTOM VLSI

引用

COMPUTER-AIDED DESIGN 1984年第1期16卷 45-50页

作者： SUPOWIT, KJ SLUTZ, EA Hewlett-Packard Laboratories Palo Alto CA 93404 USA

algorithms are presented for placement and for modifying existing placements to be used in channel routing solutions for custom VLSI layout. The placements are produced so as not to have channel routing order constraint cycles, which constitute a familiar problem for custom VLSI. The algorithms are based on mathematical results characterizing the structure of channel routing order constraints.

关键词： custom VLSI placement channel routing combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：