Search PubMed⌕ Search

Biomedical subjects

Isaac Elias

Publications and source records attributed to Isaac Elias.

3 recordsLinked to original sources

Settling the intractability of multiple alignment.

Multiple alignment is a core problem in computational biology that has received much attention over the years, both in the line of heuristics and hardness results. In most expositions of the problem it is referred to as NP-hard and references are given to one of the available hardness results. However, previous to this paper not even the most elementary variation of the problem, multiple alignment under the unit metric, had been proved hard. The aim of this paper is to settle the NP-hardness of the most common variations of multiple alignment. The following variations are shown NP-hard for all metrics over binary or larger alphabets: MULTIPLE ALIGNMENT WITH SP-SCORE, STAR ALIGNMENT, and TREE ALIGNMENT (for a given phylogeny). In addition, NP-hardness results are provided for CONSENSUS PATTERNS and SUBSTRING PARSIMONY.

Base Sequence↗

Agents of non-gonococcal urethritis in males attending an Israeli clinic for sexually transmitted diseases.

BACKGROUND: Non-gonococcal urethritis is the most common clinical diagnosis in men seeking care at clinics for sexually transmitted diseases. OBJECTIVE: To identify the pathogens involved in NGU among males attending an Israeli STD clinic. METHODS: During 19 months spanning September 1996 to July 1998 we investigated a cohort of 238 male patients attending the Bnai Zion Medical Center STD clinic with a clinical presentation of urethritis. Intraurethral swab specimens were tested for Neisseria gonorrhea, Ureaplasma urealyticum, Mycoplasma hominis, and Trichomonas vaginalis by culture and for herpes simplex virus by antigen detection. First voiding urine for C. trachomatis was done by polymerase chain reaction. The specific seropositivities of HSV types 1 and 2 were tested by enzyme-linked immunosorbent assay. RESULTS: From among 238 males with dysuria or urethral discharge an etiology for urethritis was found for 71 (29.8%). N. gonorrhea was recovered in only three men (4.2%). In the remaining 68 NGU patients Chlamydia trachomatis (35/68, 51.5%) and U. urealyticum (31/68, 45.6%) were the most common infecting and co-infecting pathogens (P < 0.0001). M. hominis and T. vaginalis were found in 9/68 (13.2%), and 1 patient, respectively. HSV was recovered from the urethra in 7/68 males (10.3%)--3 with HSV-1, 2 with HSV-2, and 2 were seronegative for HSV. None of these males had genital lesions. Although a single etiologic agent was identified in 45/68 infected men (66.2%), co-infection was common: 2 organisms in 15 (22%) and 3 organisms in 8 (11.8%). CONCLUSION: C. trachomatis and U. urealyticum were the most common infecting and co-infecting pathogens in this cohort of men with NGU. Unrecognized genital HSV infections are common in males attending our STD clinic, and symptomatic shedding of HSV occurs without genital lesions. Still, the microbial etiology in this group remains unclear in many patients despite careful microbiologic evaluation.

Adult↗

A 1.375-approximation algorithm for sorting by transpositions.

Sorting permutations by transpositions is an important problem in genome rearrangements. A transposition is a rearrangement operation in which a segment is cut out of the permutation and pasted in a different location. The complexity of this problem is still open and it has been a 10-year-old open problem to improve the best known 1.5-approximation algorithm. In this paper, we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on a new upper bound on the diameter of 3-permutations. In addition, we present some new results regarding the transposition diameter: we improve the lower bound for the transposition diameter of the symmetric group and determine the exact transposition diameter of simple permutations.

Algorithms↗