Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 5

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  algorithms
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

The EM algorithm and its implementation for the estimation of frequencies of SNP-haplotypes

100%
Polańska J.
International Journal of Applied Mathematics and Computer Science
|
2003
|
tom 13
|
nr 3
419-429
EN
A haplotype analysis is becoming increasingly important in studying complex genetic diseases. Various algorithms and specialized computer software have been developed to statistically estimate haplotype frequencies from marker phenotypes in unrelated individuals. However, currently there are very few empirical reports on the performance of the methods for the recovery of haplotype frequencies. One of the most widely used methods of haplotype reconstruction is the Maximum Likelihood method, employing the Expectation-Maximization (EM) algorithm. The aim of this study is to explore the variability of the EM estimates of the haplotype frequency for real data. We analyzed haplotypes at the BLM, WRN, RECQL and ATM genes with 8-14 biallelic markers per gene in 300 individuals. We also re-analyzed the data presented by Mano et al. (2002). We studied the convergence speed, the shape of the loglikelihood hypersurface, and the existence of local maxima, as well as their relations with heterozygosity, the linkage disequilibrium and departures from the Hardy-Weinberg equilibrium. Our study contributes to determining practical values for algorithm sensitivities.
2
Content available remote

Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms

88%
Dutta K., Subramanian C. R.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
467-495
EN
Given a simple directed graph D = (V,A), let the size of the largest induced acyclic tournament be denoted by mat(D). Let D ∈ D(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from Ϟ(n, 2p). We show that mat(D) is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either b*or b* + 1, where b* = ⌊2(logrn) + 0.5⌋ and r = p−1. It is also shown that if, asymptotically, 2(logrn) + 1 is not within a distance of w(n)/(ln n) (for any sufficiently slow w(n) → ∞) from an integer, then mat(D) is ⌊2(logrn) + 1⌋ a.a.s. As a consequence, it is shown that mat(D) is 1-point concentrated for all n belonging to a subset of positive integers of density 1 if p is independent of n. It is also shown that there are functions p = p(n) for which mat(D) is provably not concentrated in a single value. We also establish thresholds (on p) for the existence of induced acyclic tournaments of size i which are sharp for i = i(n) → ∞. We also analyze a polynomial time heuristic and show that it produces a solution whose size is at least logrn + Θ(√logrn). Our results are valid as long as p ≥ 1/n. All of these results also carry over (with some slight changes) to a related model which allows 2-cycles
3
Content available remote

Internet shopping optimization problem

88%
Błażewicz J., Kovalyov M., Musiał J., Urbański A., Wojciechowski A.
International Journal of Applied Mathematics and Computer Science
|
2010
|
tom 20
|
nr 2
385-390
EN
A high number of Internet shops makes it difficult for a customer to review manually all the available offers and select optimal outlets for shopping. A partial solution to the problem is brought by price comparators which produce price rankings from collected offers. However, their possibilities are limited to a comparison of offers for a single product requested by the customer. The issue we investigate in this paper is a multiple-item multiple-shop optimization problem, in which total expenses of a customer to buy a given set of items should be minimized over all available offers. In this paper, the Internet Shopping Optimization Problem (ISOP) is defined in a formal way and a proof of its strong NP-hardness is provided. We also describe polynomial time algorithms for special cases of the problem.
4
Content available remote

Pentadiagonal Companion Matrices

75%
Eastman B., Vander Meulen K. N.
Special Matrices
|
2016
|
tom 4
|
nr 1
13-30
EN
The class of sparse companion matrices was recently characterized in terms of unit Hessenberg matrices. We determine which sparse companion matrices have the lowest bandwidth, that is, we characterize which sparse companion matrices are permutationally similar to a pentadiagonal matrix and describe how to find the permutation involved. In the process, we determine which of the Fiedler companion matrices are permutationally similar to a pentadiagonal matrix. We also describe how to find a Fiedler factorization, up to transpose, given only its corner entries.
5
Content available remote

Error autocorrection in rational approximation and interval estimates. [A survey of results.]

75%
Litvinov G.
Open Mathematics
|
2003
|
tom 1
|
nr 1
36-60
EN
The error autocorrection effect means that in a calculation all the intermediate errors compensate each other, so the final result is much more accurate than the intermediate results. In this case standard interval estimates (in the framework of interval analysis including the so-called a posteriori interval analysis of Yu. Matijasevich) are too pessimistic. We shall discuss a very strong form of the effect which appears in rational approximations to functions. The error autocorrection effect occurs in all efficient methods of rational approximation (e.g., best approxmations, Padé approximations, multipoint Padé approximations, linear and nonlinear Padé-Chebyshev approximations, etc.), where very significant errors in the approximant coefficients do not affect the accuracy of this approximant. The reason is that the errors in the coefficients of the rational approximant are not distributed in an arbitrary way, but form a collection of coefficients for a new rational approximant to the same approximated function. The understanding of this mechanism allows to decrease the approximation error by varying the approximation procedure depending on the form of the approximant. Results of computer experiments are presented. The effect of error autocorrection indicates that variations of an approximated function under some deformations of rather a general type may have little effect on the corresponding rational approximant viewed as a function (whereas the coefficients of the approximant can have very significant changes). Accordingly, while deforming a function for which good rational approximation is possible, the corresponding approximant’s error can rapidly increase, so the property of having good rational approximation is not stable under small deformations of the approximated functions. This property is “individual”, in the sense that it holds for specific functions.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.