(Recasts, adds analyst's comments, background)

By Tiemoko Diallo

BAMAKO, Sept 10 (Reuters) - Mali's government and Tuareg rebels have freed prisoners in a move that raised hopes on Wednesday for a relaunch of formal negotiations to end the rebellion in the desert north of the West African state.

The release of soldiers being held hostage was a key condition posed by President Amadou Toumani Toure's government to Tuareg insurgent chief Ibrahima Bahanga and other rebel leaders for a definitive solution to the conflict.

For more than a year, Tuareg fighters in Mali's Saharan region bordering Algeria have attacked army posts and convoys to press demands for greater rights for their people in the largely desert country, Africa's third biggest gold producer.

In a parallel revolt in uranium-producing neighbour Niger, Tuareg-led nomadic insurgents are also battling the government to demand a greater share of their nation's wealth.

But whereas Mali's government has opened a dialogue with the rebels, Niger's leaders have ruled out peace talks unless the insurgent Niger Justice Movement (MNJ) first lays down its arms.

Mali's government said in a statement on Wednesday that 44 of its soldiers who were being held by Tuareg rebels in the northeast Kidal region were freed on Tuesday in an operation facilitated by Libyan leader Muammar Gaddafi.

"We're relieved about this release of hostages, which was a pre-condition of any dialogue with the rebels," an official in Mali's Territorial Administration Ministry told Reuters.

The Malian government statement said: "In the same spirit of peace, all of the combatants arrested and held by the nation's military authorities have been handed over to Tuareg leaders".

Although Malian military sources said four military prisoners were still in the hands of the rebels, government officials in Bamako said the releases opened the way for a relaunch of peace negotiations next Monday.

These would bring together the Malian government, a broad Malian Tuareg rebel alliance called the May 23 Democratic Alliance for Change, and Algerian mediators who are trying to reconstitute an earlier peace accord signed in 2006 in Algiers.

DEADLOCK IN NIGER

In July, Algeria, which like Libya seeks to extend its influence into the vast Saharan regions to its south, brokered a ceasefire deal between Mali's government and the Tuareg rebels.

But doubts have remained about the participation of Bahanga, a veteran rebel chieftain seen as something of rogue element in the Malian Tuareg insurgency.

Analysts said that while the situation in Niger appeared to remain deadlocked, the prisoner release looked like an advance in Mali's efforts to end its own Tuareg rebellion.

"All the signs are pointing there ... it may flare up again, but it is sort of exhausting itself," said Jeremy Keenan, a Sahara expert who has researched and written about the Tuaregs.

"The situation in Niger is different and getting nastier all the time," he added, saying that Niger President Mamadou Tandja's government maintained a hard line against Tuareg fighters it dismissed as bandits and drug-traffickers.

Fiercely proud of their independence from outsiders, the nomadic desert Tuaregs staged revolts in Mali in the 1960s and 1990s and in Niger in the 1990s for more autonomy from black African-dominated governments in faraway capitals.

Peace agreements after the 1990s rebellions aimed to grant Tuareg communities more autonomy while integrating former fighters into the national army and promoting Tuareg politicians.

But since last year, Tuaregs in Niger and Mali have taken up arms again, motivated by resentment against unsolved grievances and what they see as unwarranted interference in their traditional lands by government armies and foreign companies. (For full Reuters Africa coverage and to have your say on the top issues, visit: http://africa.reuters.com/) (Additional reporting and writing by Pascal Fletcher; editing by Alistair Thomson)

AlertNet news is provided by