Tribal sources said four tribesmen and eight soldiers were killed, but security officials in Marib province, 100 miles east of the capital, San'a, said the five suspects apparently were able to hide or escape the barrage and special troops who moved in for a search.
Security officials would not comment on casualties. The tribal sources also said 22 people were wounded, some of them soldiers, and that several small homes used by tribesmen to fire on the government troops were destroyed in the exchange.
After two hours of bombardment against the Abida tribe in the morning, special forces successfully entered the al-Halsun region some of them dropped from helicopters but did not find the suspects, the security officials in Marib said.
However, government forces arrested a number of tribesmen suspected of hiding the wanted men, an Interior Ministry official said. He did not say how many. All the officials and tribal sources spoke on condition of anonymity.
In Washington, Deputy Defense Secretary Paul Wolfowitz said the United States has been "urging the Yemenis to do more" about suspected al-Qaeda members in the country. But he said he had no information on the special forces' operation.
The administration has long been concerned about "pockets where we believe al-Qaeda people have sheltered and may be there now" in Yemen, particularly along the remote Saudi border.
The Yemeni Interior Ministry official said special forces were conducting a wide search operation in Marib and adjacent Shabwa provinces, and that security has also been tightened in the provinces of Hadramout, Abyan, and Lahj, three strongholds of Islamic militants in eastern Yemen.
Bin Laden, whose father was born in the Hadramout region, is the prime suspect in the Sept. 11 terror attacks. His al-Qaeda network is believed to exist in dozens of countries.
The United States believes al-Qaeda was also behind the October 2000 attack on the destroyer USS Cole in Yemen's southern port of Aden, which killed 17 American sailors.
Although no U.S. operatives participated in Tuesday's operation, Yemeni authorities are apprising American officials of the ongoing search for the suspects, another Interior Ministry official said, also on condition of anonymity.
The special forces unit was the first to graduate from a U.S.-funded program to train and equip Yemen's security forces.
Tuesday's battle marked the first time since Sept. 11 that door-to-door search operations in Yemen have been conducted with military support and erupted into fighting. It was also is the first time Yemen has said publicly it is pursuing members of al-Qaeda in the country.
Sources in the Marib region familiar with the special forces' operation said the bombardment came after the Abida tribe refused in two days of negotiations to hand over at least five men suspected of belonging to al-Qaeda.
Those sources said one of the men was among three names of suspected al-Qaeda operatives in Yemen that U.S. officials gave Yemeni President Ali Abdullah Saleh during his visit last month to Washington. At least one of the men being sought was a non-Yemeni Arab who previously was in Afghanistan, they said.
The Abida tribe, which numbers some 5,000, is the largest in Marib province, which has earned a reputation for lawlessness. Since 1990, about 100 foreigners have been kidnapped in Marib, usually used as bargaining chips with the government to press for aid and better living conditions.
Copyright 2001 The Associated Press. All rights reserved. This material may not be published, broadcast, rewritten or redistributed.